1333 : 平衡樹(shù)·Splay2
時(shí)間限制:10000ms 單點(diǎn)時(shí)限:1000ms 內(nèi)存限制:256MB 描述 小Ho：好麻煩啊~ 小Hi：小Ho你在干嘛呢？ 小Ho：我在干活啊！前幾天老師讓我?guī)兔芾硪幌聢F(tuán)隊(duì)的人員，但是感覺(jué)好難啊。 小Hi：說(shuō)來(lái)聽(tīng)聽(tīng)？ 小Ho：事情是這樣的。我們有一個(gè)運(yùn)動(dòng)同好會(huì)，每天都有人加入或者退出，所以老師讓我?guī)兔芾硪幌氯藛T。每個(gè)成員有一個(gè)互不相同的id和他對(duì)我們同好會(huì)的興趣值val，每隔一段時(shí)間一些成員的興趣值就會(huì)發(fā)生變化。老師有時(shí)候也會(huì)問(wèn)我一些成員的興趣值。 小Hi：所以你就需要一個(gè)表格來(lái)管理信息咯？ 小Ho：是啊，但是我們同好會(huì)的成員實(shí)在是太多了！我感覺(jué)完全搞不定啊。 小Hi：這樣啊，那不如讓我來(lái)幫幫你吧！ 小Ho：真的嗎？ 小Hi：當(dāng)然是真的啦，小Ho，你先告訴我有多少種需要完成的事情？ 小Ho：一共有4種情況： 1. 加入：一個(gè)新的成員加入同好會(huì)，我會(huì)分配給他一個(gè)沒(méi)有使用的id，并且詢(xún)問(wèn)他的興趣值val。 2. 修改：id在區(qū)間[a,b]內(nèi)的成員，興趣值同時(shí)改變k，k有可能是負(fù)數(shù)，表示他們失去了對(duì)同好會(huì)的興趣。 3. 退出：id在區(qū)間[a,b]內(nèi)的成員要退出同好會(huì)，雖說(shuō)是區(qū)間，也有可能只有1個(gè)人。 4. 詢(xún)問(wèn)：老師會(huì)問(wèn)我在區(qū)間[a,b]內(nèi)的成員總的興趣值。 小Hi：我明白了，讓我想一想該如何解決。 輸入 第1行：1個(gè)正整數(shù)n，表示操作數(shù)量，100≤n≤200,000 第2..n+1行：可能包含下面4種規(guī)則： 1個(gè)字母’I’，緊接著2個(gè)數(shù)字id,val，表示一個(gè)編號(hào)為id的新成員加入，其興趣值為val，1≤id≤100,000,000，1≤val≤10,000,000，保證在團(tuán)隊(duì)中的每個(gè)人id都不相同。 1個(gè)字母’Q’，緊接著2個(gè)數(shù)字a,b。表示詢(xún)問(wèn)團(tuán)隊(duì)中id在區(qū)間[a,b]的所有成員總興趣值，保證區(qū)間內(nèi)至少有一個(gè)成員，結(jié)果有可能超過(guò)int的范圍。 1個(gè)字母’M’，緊接著3個(gè)數(shù)字a,b,d，表示將團(tuán)隊(duì)中id在區(qū)間[a,b]的成員興趣值都改變d，其中d有可能為負(fù)數(shù)。保證操作之后每個(gè)成員的興趣值仍然在0~10,000,000。 1個(gè)字母’D’，緊接著2個(gè)數(shù)字a,b，表示將團(tuán)隊(duì)中id在區(qū)間[a,b]的成員除去。 注意有可能出現(xiàn)一個(gè)id為1的成員加入團(tuán)隊(duì)，被除去之后，又有一個(gè)新的id為1的成員加入團(tuán)隊(duì)的情況。 輸出 若干行：每行1個(gè)整數(shù)，表示針對(duì)詢(xún)問(wèn)的回答，保證一定有合法的解 樣例輸入 9 I 1 1 I 2 2 I 3 3 Q 1 3 M 1 2 2 Q 1 3 D 2 3 I 4 2 Q 1 4 樣例輸出 6 10 5
/*splay 值域區(qū)間修改+區(qū)間刪除+區(qū)間查詢(xún)+tagpush.*/#include<iostream>#include<cstdio>#define MAXN 200011#define LL long long#define INF 1e9using namespace std;int n,m,tot,size[MAXN],s[MAXN],id[MAXN],fa[MAXN],tree[MAXN][2],root,tag[MAXN],t1,t2;LL sum[MAXN];int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f;}void push(int k){ if(tree[k][0]) s[tree[k][0]]+=tag[k]; if(tree[k][1]) s[tree[k][1]]+=tag[k]; if(tree[k][0]) tag[tree[k][0]]+=tag[k]; if(tree[k][1]) tag[tree[k][1]]+=tag[k]; if(tree[k][0]) sum[tree[k][0]]+=tag[k]*size[tree[k][0]]; if(tree[k][1]) sum[tree[k][1]]+=tag[k]*size[tree[k][1]]; tag[k]=0;return ;}void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(tree[y][0]==x) l=0;else l=1;r=l^1; if(tag[z]) push(z); if(tag[y]) push(y); if(tag[x]) push(x); if(y==k) k=x; else{ if(tree[z][0]==y) tree[z][0]=x; else tree[z][1]=x; } fa[x]=z;fa[y]=x;fa[tree[x][r]]=y; tree[y][l]=tree[x][r],tree[x][r]=y; size[y]=size[tree[y][0]]+size[tree[y][1]]+1; size[x]=size[tree[x][0]]+size[tree[x][1]]+1; sum[y]=sum[tree[y][0]]+sum[tree[y][1]]+s[y]; sum[x]=sum[tree[x][0]]+sum[tree[x][1]]+s[x]; return ;}void splay(int x,int &k){ int y,z; while(x!=k) { y=fa[x],z=fa[y]; if(y!=k) { if((tree[z][0]==y)^(tree[y][0]==x)) rotate(x,k); else rotate(y,k); } rotate(x,k); } return ;}void add(int &k,int f,int x,int y){ if(!k){k=++tot;s[tot]=y;id[tot]=x;size[tot]=1;sum[k]=y;fa[tot]=f;splay(k,root);return ;} if(tag[k]) push(k); if(x<=id[k]) add(tree[k][0],k,x,y); else add(tree[k][1],k,x,y); return ;}void before(int k,int x){ if(!k) return ; if(tag[k]) push(k); if(x>=id[k]){t1=k;before(tree[k][1],x);return ;} else before(tree[k][0],x); return ;}void after(int k,int x){ if(!k) return ; if(tag[k]) push(k); if(x<=id[k]){t2=k;after(tree[k][0],x);return ;} else after(tree[k][1],x); return ;}void slovequery(int x,int y){ before(root,x-1); after(root,y+1); splay(t1,root),splay(t2,tree[t1][1]);
