uva 12436 Rip Van Winkle's Code 区间更新区间查询

题意：
就是给4段代码，说这四段代码重复执行很多次，现在要求你实现这段代码。

long long data[250001];
void A( int st, int nd ) {
	for( int i = st; i <= nd; i++ ) data[i] = data[i] + (i - st + 1);
}
void B( int st, int nd ) {
	for( int i = st; i <= nd; i++ ) data[i] = data[i] + (nd - i + 1);
}
void C( int st, int nd, int x ) {
	for( int i = st; i <= nd; i++ ) data[i] = x;
}
long long S( int st, int nd ) {
	long long res = 0;
	for( int i = st; i <= nd; i++ ) res += data[i];
	return res;
}

当然不能直接用这个代码了，复杂度很高。
当然正常想法肯定是线段树
这道题真是。。。怎么说。。就是细节要考虑很多。一不注意就写错。
要注意的几个地方

• 两个公差d>0的等差数列相加也是等差数列，并且相加后公差会变化
• 两个公差d<0的等差数列相加也是等差数列，并且相加后公差会变化
• C操作和A/B操作不兼容
  • 本节点若执行C操作，那么其子节点的A/B操作直接被覆盖取消
  • 本节点若执行A/B操作，先判断是否有C操作，有C操作先压到子节点再说(pushdown)
  • 区间更新要用到lazy操作

• 注意long long在uva中要输出%lld

//author: CHC
//First Edit Time:	2015-07-14 15:39
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=250000+100000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
struct Tree {
    LL sum;
    int flag;
    LL l,r;
    LL l1,r1;
    LL val;
}tr[MAXN<<2];
void pushup(int rt){
    tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}
void pushdownB(int L,int R,int rt);
void pushdownA(int L,int R,int rt);
void pushdownA(int L,int R,int rt){
    if(L==R)return;
    int mid=(L+R)>>1;
    if((tr[rt].flag&1)==1){
        LL d=(tr[rt].r-tr[rt].l)/(R-L);
        LL xl=tr[rt].l,xmid=tr[rt].l+(mid-L)*d,xr=tr[rt].r;
        if((tr[rt<<1].flag&4)==4){
            pushdownB(lson);
        }
        if((tr[rt<<1|1].flag&4)==4){
            pushdownB(rson);
        }
        tr[rt<<1].flag|=1;
        tr[rt<<1|1].flag|=1;

        tr[rt<<1].l+=xl;
        tr[rt<<1].r+=xmid;

        tr[rt<<1|1].l+=xmid+d;
        tr[rt<<1|1].r+=xr;

        tr[rt<<1].sum+=(xl+xmid)*(mid-L+1)/2;
        tr[rt<<1|1].sum+=(xmid+d+xr)*(R-(mid+1)+1)/2;
        tr[rt].l=tr[rt].r=0;
        tr[rt].flag^=1;
    }
    if((tr[rt].flag&2)==2){
        LL d=(tr[rt].r1-tr[rt].l1)/(R-L);
        LL xl=tr[rt].l1,xmid=tr[rt].l1+(mid-L)*d,xr=tr[rt].r1;
        //printf("%I64d %I64d %I64d d:%I64d\n",xl,xmid,xr,d);
        if((tr[rt<<1].flag&4)==4){
            pushdownB(lson);
        }
        if((tr[rt<<1|1].flag&4)==4){
            pushdownB(rson);
        }
        tr[rt<<1].flag|=2;
        tr[rt<<1|1].flag|=2;

        tr[rt<<1].l1+=xl;
        tr[rt<<1].r1+=xmid;

        tr[rt<<1|1].l1+=xmid+d;
        tr[rt<<1|1].r1+=xr;
        tr[rt<<1].sum+=(xl+xmid)*(mid-L+1)/2;
        tr[rt<<1|1].sum+=(xmid+d+xr)*(R-(mid+1)+1)/2;
        tr[rt].l1=tr[rt].r1=0;
        tr[rt].flag^=2;
    }
    pushdownB(L,R,rt);
}
void pushdownB(int L,int R,int rt){
    if(L==R)return ;
    int mid=(L+R)>>1;
    if((tr[rt].flag&4)==4){
        tr[rt<<1].l=tr[rt<<1].r=tr[rt<<1|1].l=tr[rt<<1|1].r=0;
        tr[rt<<1].l1=tr[rt<<1].r1=tr[rt<<1|1].l1=tr[rt<<1|1].r1=0;
        tr[rt<<1].sum=tr[rt<<1|1].sum=0;
        tr[rt<<1].flag=4;
        tr[rt<<1|1].flag=4;
        tr[rt<<1].val=tr[rt<<1|1].val=tr[rt].val;
        tr[rt<<1].sum=(mid-L+1)*tr[rt].val;
        tr[rt<<1|1].sum=(R-(mid+1)+1)*tr[rt].val;
        tr[rt].val=0;
        tr[rt].l=tr[rt].r=tr[rt].l1=tr[rt].r1=0;
        tr[rt].flag^=4;
    }
}
void build(int L,int R,int rt){
    tr[rt].sum=0;
    tr[rt].flag=0;
    tr[rt].l=tr[rt].r=0;
    tr[rt].l1=tr[rt].r1=0;
    tr[rt].val=0;
    if(L==R)return; 
    int mid=(L+R)>>1;
    build(lson); build(rson);
}
LL TL;
void update(int L,int R,int rt,int l,int r,LL v,int flag){
    if(l<=L&&R<=r){
        if(flag==1){
            if((tr[rt].flag&4)==4){
                pushdownB(L,R,rt);
            }
            tr[rt].flag|=flag;
            tr[rt].l+=TL;
            tr[rt].r+=TL+(R-L+1)-1;
            tr[rt].sum+=(TL+TL+(R-L+1)-1)*(R-L+1)/2;
            //printf("L:%d R:%d %I64d %I64d %I64d TL:%I64d\n",L,R,tr[rt].l,tr[rt].r,tr[rt].sum,TL);
            TL=TL+(R-L+1);
        }
        if(flag==2){
            if((tr[rt].flag&4)==4){
                pushdownB(L,R,rt);
            }
            tr[rt].flag|=flag;
            tr[rt].l1+=TL;
            tr[rt].r1+=TL-(R-L+1)+1;
            tr[rt].sum+=(TL+TL-(R-L+1)+1)*(R-L+1)/2;
            //printf("L:%d R:%d %I64d %I64d %I64d TL:%I64d\n",L,R,tr[rt].l1,tr[rt].r1,tr[rt].sum,TL);
            TL=TL-(R-L+1);
        }
        if(flag==4){
            tr[rt].flag|=flag;
            tr[rt].l=tr[rt].r=0;
            tr[rt].l1=tr[rt].r1=0;
            tr[rt].flag=flag;
            tr[rt].val=v;
            tr[rt].sum=v*(R-L+1);
        }
        return;
    }
    pushdownA(L,R,rt);
    int mid=(L+R)>>1;
    if(l<=mid)update(lson,l,r,v,flag);
    if(r>mid)update(rson,l,r,v,flag);
    pushup(rt);
}
LL query(int L,int R,int rt,int l,int r){
    if(l<=L&&R<=r){
        //printf("query:%d %d %I64d flag:%d\n",L,R,tr[rt].sum,tr[rt].flag);
        return tr[rt].sum;
    }
    pushdownA(L,R,rt);
    int mid=(L+R)>>1;
    LL ans=0;
    if(l<=mid)ans+=query(lson,l,r);
    if(r>mid)ans+=query(rson,l,r);
    pushup(rt);
    return ans;
}
int main()
{
    int T;
    const int tn=250001;
    while(~scanf("%d",&T)){
        //scanf("%d",&T);
        char ch;
        int tl,tr,v;
        build(1,tn,1);
        while(T--){
            scanf(" %c",&ch);
            if(ch=='A'){
                TL=1;
                scanf("%d%d",&tl,&tr);
                update(1,tn,1,tl,tr,(LL)0,1);
            }
            if(ch=='B'){
                scanf("%d%d",&tl,&tr);
                TL=tr-tl+1;
                update(1,tn,1,tl,tr,(LL)0,2);
            }
            if(ch=='C'){
                scanf("%d%d%d",&tl,&tr,&v);
                update(1,tn,1,tl,tr,(LL)v,4);
            }
            if(ch=='S'){
                scanf("%d%d",&tl,&tr);
                printf("%lld\n",query(1,tn,1,tl,tr));
            }
        }
    }
    return 0;
}
/*
   7
   A 1 4
   B 2 3
   S 1 3
   C 3 4 -2
   S 2 4
   B 1 3
   S 2 4
   */