happy children’s day(rmq线段树成段更新).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
    int l,r;
    node * pl, * pr;
    int imax;
    int add;
    int mmax;
}mem[300000];
int mem_pos;

node *
new_node()
{
    node * pt = &mem[mem_pos ++];
    memset(pt,0,sizeof(node));
    return pt;
}

node *
make_tree(int il, int ir)
{
    node * root = new_node();
    root ->l = il;
    root ->r = ir;
    root ->imax = il;
    if(ir > il) {
        int mid = (il+ir)/2;
        root ->pl = make_tree(il, mid);
        root ->pr = make_tree(mid+1, ir);
    }
    return root;
}

int
update(node * root,int l, int r, int v)
{
    if(root ->l == l && root ->r == r) {
        root ->add += v;
        return root ->mmax + root ->add;
    }
    int mid = (root ->l + root ->r)/2;

    if(l <= mid) {
        if(r <= mid) {
            int t = update(root ->pl, l, r, v);
            if(t >= root ->pr ->add + root ->pr ->mmax) {
                root ->mmax = t;
                root ->imax = root ->pl ->imax;
            }
            else {
                root ->mmax = root ->pr ->add + root ->pr ->mmax;
                root ->imax = root ->pr ->imax;
            }
        }
        else {
            root ->mmax = update(root ->pl, l, mid, v);
            root ->imax = root ->pl ->imax;
            int t = update(root ->pr, mid+1, r, v);
            if(t > root ->mmax) {
                root ->mmax = t;
                root ->imax = root ->pr ->imax;
            }
        }
    }
    else {
        int t = update(root ->pr, l, r, v);
        if(t > root ->pl ->add + root ->pl ->mmax) {
            root ->mmax = t;
            root ->imax = root ->pr ->imax;
        }
        else {
            root ->mmax = root ->pl ->add + root ->pl ->mmax;
            root ->imax = root ->pl ->imax;
        }
    }

    return root ->mmax + root ->add;
}

int
get(node * root,int l, int r,int &imax)
{
    if(root ->l == l && root ->r == r) {
        imax = root ->imax;
        return root ->mmax + root ->add;
    }
    int mid = (root ->l + root ->r)/2;
    int t1,t2;
    if(l <= mid) {
        if(r <= mid) {
            t1 = get(root ->pl, l,r,imax);
        }
        else {
            int imax2;
            t1 = get(root ->pl, l,mid,imax);
            t2 = get(root ->pr, mid+1,r,imax2);
            if(t2 > t1) {
                t1 = t2;
                imax = imax2;
            }
        }
    }
    else {
        t1 = get(root ->pr, l,r,imax);
    }
    return t1 + root ->add;
}


int main()
{
    int t,n,m,i,j;
    int a,b,c;
    char cmd[5];
    
    int imax;
    //freopen("1779.in","r",stdin);
    //freopen("my1719.txt","w",stdout);
    while(scanf("%d %d", &n,&m)==2) {
        if(n==0 && m==0) {
            break;
        }
        mem_pos = 0;
        node * root = make_tree(1, n);
        getchar();
        while(m --) {
            scanf("%s",cmd);
            if(cmd[0] == 'I') {
                scanf("%d %d %d",&a,&b,&c);
                update(root, a,b,c);
            }
            else {
                int cand;
                scanf("%d %d",&a,&b);
                imax = 0;
                printf("%d\n",cand = get(root, a,b,imax));
                if(imax != 0) {
                    update(root, imax, imax, -cand);
                }
                //printf("get pile = %d, num = %d\n", imax,cand);
            }
        }
    }
}