题目大意：
从
1～106
有
106
个基底，一开始上面都没有积木，高度为
0
，连续的一段高度大于
0
的基底算作一个
tower
，显然一开始
tower
数为
0
。
接下来有两个操作：
1.put x c
将
c
个积木放在第
x
个基底上。
2.tput t x c
将
c
个积木放在第
t
个
tower
中的第
x
个基底上
(
tower
从左到右排列并且保证存在这个基底
)
。
然后有四个询问：
1.towers
问当前有多少个
tower
。
2.cubes t
问第
t
个
tower
一共有多少个积木。
3.length t
问第
t
个
tower
包含了多少个基底，即宽度是多少。
4.tcube t x
问第
t
个
tower
的第
x
个基底上有多少个积木。
解题思路：
平衡树的裸题
(
好像有线段树的做法，但是我不会啊
QAQ)
。
我们建一个平衡树维护
tower
，记录一下左端点、右端点、和一共有多少个积木，每次增加积木时，如果当前的基底上没有积木，那么就考虑是否会新增一个
tower
，或者扩大一个
tower
，或者是合并两个
tower
。总的来说还是很简单的。
AC代码:
#include
#include
#include
#include
#include
#include
using namespace std; int QAQ; struct tree_ { int son[2],fa,Size,left,right,cubes; inline void clear() {son[0]=son[1]=fa=Size=left=right=cubes=0;} }tower[1000010]; int tower_end=0; int root; int height[1000010]={0}; inline void read_(int &x) { x=0; char ch=getchar(); for(;ch=='\n' || ch=='\r' || ch==' ';ch=getchar()); for(;ch>='0' && ch<='9';ch=getchar()) x=x*10+ch-'0'; return; } void rotate(int k) { int Fa=tower[k].fa; int g=(tower[Fa].son[1]==k); tower[k].fa=tower[Fa].fa; tower[k].Size=tower[Fa].Size; if(tower[k].son[g^1]!=0) tower[tower[k].son[g^1]].fa=Fa; tower[Fa].Size=tower[tower[Fa].son[g^1]].Size+tower[tower[k].son[g^1]].Size+1; tower[Fa].son[g]=tower[k].son[g^1]; tower[Fa].fa=k; tower[k].son[g^1]=Fa; if(tower[k].fa!=0) { g=(tower[tower[k].fa].son[1]==tower[k].son[g^1]); tower[tower[k].fa].son[g]=k; } return; } inline void splay(int k) { for(;tower[k].fa!=0;) { if(tower[k].fa==root) rotate(k); else { int Fa=tower[k].fa; int g1=(tower[tower[k].fa].son[1]==k); int g2=(tower[tower[Fa].fa].son[1]==Fa); if(g1==g2) { rotate(Fa); rotate(k); } else { rotate(k); rotate(k); } } } root=k; return; } inline int Findtower(int k,int now) { int l=tower[now].son[0]; int r=tower[now].son[1]; if(tower[l].Size>=k) return Findtower(k,l); if(tower[l].Size+1
k) return Findtower2(k,tower[now].son[0]); if(tower[now].right
0;QAQ--) { char ch[10]="\0"; scanf("%s",ch); if(strcmp("put",ch)==0) { int x,c; read_(x),read_(c); if(height[x]!=0) { int tt=Findtower2(x,root); tower[tt].cubes+=c; } else { if(height[x-1]==0 && height[x+1]==0) { int tt; if(root==0) { tt=++tower_end; tower[tt].left=tower[tt].right=x; tower[tt].Size=1; root=tt; } else { tt=Add(x,root); splay(tt); } tower[tt].cubes+=c; } else if((height[x-1]>0)+(height[x+1]>0)==1) { int xx=height[x-1]>0?x-1:x+1; int tt=Findtower2(xx,root); tower[tt].cubes+=c; if(xx==x-1) tower[tt].right=x; else tower[tt].left=x; splay(tt); } else { int tt1=Findtower2(x-1,root); int tt2=Findtower2(x+1,root); splay(tt2);splay(tt1); tower[tt1].cubes+=tower[tt2].cubes+c; tower[tt1].right=tower[tt2].right; tower[tt1].son[1]=tower[tt2].son[1]; tower[tt1].Size--; if(tower[tt2].son[1]!=0) tower[tower[tt2].son[1]].fa=tt1; tower[tt2].clear(); } } height[x]+=c; } else if(strcmp("tput",ch)==0) { int t,x,c; read_(t); //scanf("%d",&t); t=Findtower(t,root); read_(x),read_(c); // scanf("%d%d",&x,&c); height[tower[t].left+x-1]+=c; tower[t].cubes+=c; splay(t); } else if(strcmp("towers",ch)==0) printf("%d towers\n",tower[root].Size); else if(strcmp("cubes",ch)==0) { int t; read_(t); //scanf("%d",&t); int tt=Findtower(t,root); splay(tt); printf("%d cubes in %dth tower \n",tower[tt].cubes,t); } else if(strcmp("length",ch)==0) { int t; read_(t); //scanf("%d",&t); int tt=Findtower(t,root); splay(tt); printf("length of %dth tower is %d\n",t,tower[tt].right-tower[tt].left+1); } else if(strcmp("tcubes",ch)==0) { int t,x; read_(t),read_(x); //scanf("%d%d",&t,&x); int tt=Findtower(t,root); splay(tt); printf("%d cubes in %dth column of %dth tower\n",height[tower[tt].left+x-1],x,t); } } return 0; }