SPOJ-TTM - To the moon(主席树,经典)

题目链接

TTM - To the moon

Background

To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.

The PRemise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.

Description

You‘ve been given N integers A[1], A[2],..., A[N]. On these integers, you need to implement the following Operations:

 .. N, M ≤ 10^5, |A[i]| ≤ 10^9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10^4 .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state. 

Input

n mA1 A2 ... An... (here following the m operations. )
Output
... (for each query, simply print the result. )
Example
Input 1:10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4Output 1:455915Input 2:2 40 0C 1 1 1C 2 2 -1Q 1 2H 1 2 1Output 2:01 Submit solution!
题意：
一个长度为n的数组，4种操作 ：
（1）C l r d：区间[l,r]中的数都加1，同时当前的时间戳加1 。
（2）Q l r：查询当前时间戳区间[l,r]中所有数的和 。
（3）H l r t：查询时间戳t区间[l,r]的和 。
（4）B t：将当前时间戳置为t 。时间倒转后就不能再回去。
所有操作均合法 。
题解：
以前写的那几个主席树的题都是属于主席树的应用-查询第k大之类的。
这个题就是主席树的最初用途了。
发现以前写的用于查询第k大的主席树模版写这种题似乎不太合适==
于是换了一种大众一点的写法，可以当作板子。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int maxn=1e6+100;struct node{    int l,r,mark;    ll sum,tag;}T[maxn*40];int root[maxn];int cnt;//void pushup(int x){    T[x].sum=T[T[x].l].sum+T[T[x].r].sum;}int build(int l,int r){    int root=++cnt;    T[root].sum=T[root].tag=T[root].mark=0;    if(l==r)    {        scanf("%lld",&T[root].sum);        T[root].l=T[root].r=0;        return root;    }    int m=(l+r)/2;    T[root].l=build(l,m);    T[root].r=build(m+1,r);    pushup(root);    return root;}void copy(int x,int y){    T[x].sum=T[y].sum;    T[x].tag=T[y].tag;    T[x].l=T[y].l;    T[x].r=T[y].r;}void pushdown(int x,int l,int r){    if(T[x].mark)//    {        int now=++cnt;        copy(now,T[x].l);        T[x].l=now;        now=++cnt;        copy(now,T[x].r);        T[x].r=now;        T[T[x].l].mark=T[T[x].r].mark=1; //        T[x].mark=0;    }    if(T[x].tag)    {        int m=(l+r)/2;        T[T[x].l].tag+=T[x].tag;        T[T[x].r].tag+=T[x].tag;        T[T[x].l].sum+=1ll*T[x].tag*(m-l+1);        T[T[x].r].sum+=1ll*T[x].tag*(r-m);        T[x].tag=0;    }}int update(int root,int L,int R,int l,int r,int v){    int now=++cnt;    if(l==L&&r==R)    {        T[now].l=T[root].l;        T[now].r=T[root].r;  //        T[now].sum=T[root].sum+1ll*(r-l+1)*v;        T[now].tag=T[root].tag+v;        T[now].mark=l==r?0:1;        return now;    }    int m=(L+R)/2;    T[now].mark=T[now].sum=T[now].tag=0;//    pushdown(root,L,R);    if(r<=m)    {        T[now].l=update(T[root].l,L,m,l,r,v);        T[now].r=T[root].r;    }    else if(l>m)    {        T[now].l=T[root].l;        T[now].r=update(T[root].r,m+1,R,l,r,v);    }    else    {        T[now].l=update(T[root].l,L,m,l,m,v);        T[now].r=update(T[root].r,m+1,R,m+1,r,v);    }    pushup(now);    return now;}ll query(int root,int L,int R,int l,int r){    if(L==l&&R==r)        return T[root].sum;    pushdown(root,L,R); //    int m=(L+R)/2;    if(r<=m) return query(T[root].l,L,m,l,r);    else if(l>m) return query(T[root].r,m+1,R,l,r);    else return query(T[root].l,L,m,l,m)+query(T[root].r,m+1,R,m+1,r);}int main(){    int n,m;    while(~scanf("%d%d",&n,&m))    {        int now=0;        cnt=0;        root[now]=build(1,n);        char op[5];        while(m--)        {            scanf("%s",op);            int l,r,v;            if(op[0]=='Q')            {                scanf("%d%d",&l,&r);                printf("%lld/n",query(root[now],1,n,l,r));            }            else if(op[0]=='C')            {                scanf("%d%d%d",&l,&r,&v);                now++;                root[now]=update(root[now-1],1,n,l,r,v);            }            else if(op[0]=='H')            {                scanf("%d%d%d",&l,&r,&v);                printf("%lld/n",query(root[v],1,n,l,r));            }            else if(op[0]=='B')                scanf("%d",&v),now=v;        }        puts("");    }    return 0;}