描述
小Ho：好麻烦啊~~~~~
小Hi：小Ho你在干嘛呢？
小Ho：我在干活啊！前几天老师让我帮忙管理一下团队的人员，但是感觉好难啊。
小Hi：说来听听？
小Ho：事情是这样的。我们有一个运动同好会，每天都有人加入或者退出，所以老师让我帮忙管理一下人员。每个成员有一个互不相同的id和他对我们同好会的兴趣值val，每隔一段时间一些成员的兴趣值就会发生变化。老师有时候也会问我一些成员的兴趣值。
小Hi：所以你就需要一个表格来管理信息咯？
小Ho：是啊，但是我们同好会的成员实在是太多了！我感觉完全搞不定啊。
小Hi：这样啊，那不如让我来帮帮你吧！
小Ho：真的吗？
小Hi：当然是真的啦，小Ho，你先告诉我有多少种需要完成的事情？
小Ho：一共有4种情况：
1. 加入：一个新的成员加入同好会，我会分配给他一个没有使用的id，并且询问他的兴趣值val。
2. 修改：id在区间[a,b]内的成员，兴趣值同时改变k，k有可能是负数，表示他们失去了对同好会的兴趣。
3. 退出：id在区间[a,b]内的成员要退出同好会，虽说是区间，也有可能只有1个人。
4. 询问：老师会问我在区间[a,b]内的成员总的兴趣值。
小Hi：我明白了，让我想一想该如何解决。
输入
第1行：1个正整数n，表示操作数量，100≤n≤200,000
第2..n+1行：可能包含下面4种规则：
1个字母'I'，紧接着2个数字id,val，表示一个编号为id的新成员加入，其兴趣值为val，1≤id≤100,000,000，1≤val≤10,000,000，保证在团队中的每个人id都不相同。
1个字母'Q'，紧接着2个数字a,b。表示询问团队中id在区间[a,b]的所有成员总兴趣值，保证区间内至少有一个成员，结果有可能超过int的范围。
1个字母'M'，紧接着3个数字a,b,d，表示将团队中id在区间[a,b]的成员兴趣值都改变d，其中d有可能为负数。保证操作之后每个成员的兴趣值仍然在0~10,000,000。
1个字母'D'，紧接着2个数字a,b，表示将团队中id在区间[a,b]的成员除去。
注意有可能出现一个id为1的成员加入团队，被除去之后，又有一个新的id为1的成员加入团队的情况。
输出
若干行：每行1个整数，表示针对询问的回答，保证一定有合法的解
样例输入
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
一代代码：按照hihocoder上面的模板打的：
ps： 如果没有新加入节点这一操作，就是线段树+laxy操作了...... 有新加入节点，splay+laxy...... 似乎明白了什么...... 正题： 和上一个代码比较，加了id，val，tot，lazy等变量，和一些函数。 注意：查询，修改，和删除函数依旧没有加边界两点。。。 因为此处的做法是找到最大的x<a,最小的y>b（不能等于！），然后查询，修改或者删去x，y之间的（不包括x和y），这样保证处理的区间一定在[a,b]上。 （insert如果用地址符的话，可以不单独处理root==0的情况，这里懒得改了，见下面几道题的写法。） #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long const int maxN=200101; const ll inf=0x3f3f3f3f; struct SplayData { int fa,ch[2],id,val,num; ll totVal,lazy; SplayData()//自动初始每一个新建data { totVal=val=lazy=0; ch[0]=ch[1]=0; num=fa=0; } }; struct SplayTree { int cnt; int root; SplayData S[maxN]; SplayTree()//自动初始树 { root=0; cnt=0; Insert(-inf,0);//插入极大极小值 Insert(inf,0); } void Find(int x) { if (root==0) return ;//树为空，肯定找不到 int now=root; while ((S[now].ch[x>S[now].id]!=0)&&(x!=S[now].id)) { now=S[now].ch[x>S[now].id]; } Splay(now,0); } void marking(int x,int delta) { S[x].lazy+=delta; S[x].totVal+=S[x].num*delta; S[x].val+=delta; } void update(int x)//对x { S[x].num=1; S[x].totVal=S[x].val; if(S[x].ch[0]){ S[x].num+=S[S[x].ch[0]].num; S[x].totVal+=S[S[x].ch[0]].totVal; } if(S[x].ch[1]){ S[x].num+=S[S[x].ch[1]].num; S[x].totVal+=S[S[x].ch[1]].totVal; } } void pushdown(int x)//对x的儿子 { if(S[x].ch[0]) marking(S[x].ch[0],S[x].lazy); if(S[x].ch[1]) marking(S[x].ch[1],S[x].lazy); S[x].lazy=0; update(x); } void Insert(int id,int val) { if(root==0){ root=++cnt; S[root].id=id; S[root].val=val; S[root].totVal=val; } else { int x=bst_insert(root,id,val); if(x) Splay(x,0); } } int bst_insert(int now,int id,int val) { pushdown(now); int tmp=0; if(S[now].id>id){ if(S[now].ch[0]) tmp=bst_insert(S[now].ch[0],id,val); else { S[++cnt].id=id; S[cnt].val=val; S[cnt].totVal=val; S[now].ch[0]=cnt; S[cnt].fa=now; tmp=cnt; } } else if(S[now].id<id){ if(S[now].ch[1]) tmp=bst_insert(S[now].ch[1],id,val); else { S[++cnt].id=id; S[cnt].val=val; S[cnt].totVal=val; S[now].ch[1]=cnt; S[cnt].fa=now; tmp=cnt; } } update(now); return tmp; } void Rotate(int x) { int y=S[x].fa; int z=S[y].fa; pushdown(y); pushdown(x); int k1=S[y].ch[1]==x; int k2=S[z].ch[1]==y; S[z].ch[k2]=x; S[x].fa=z; S[y].ch[k1]=S[x].ch[k1^1]; S[S[x].ch[k1^1]].fa=y; S[x].ch[k1^1]=y; S[y].fa=x; update(y); update(x); return; } void Splay(const int x,int goal) { if(!x) return ;//! while (S[x].fa!=goal) { int y=S[x].fa; int z=S[y].fa; if (z!=goal) ((S[z].ch[0]==y)^(S[y].ch[0]==x))?Rotate(x):Rotate(y);//异则x，同则y Rotate(x); } if (goal==0) root=x; return; } int Next(int x,int opt) { Find(x);//先移‘x’到根 int now=root; if ((S[now].id<x)&&(opt==0)) return now; //对根做处理,暂时没有发现这种情况。 if ((S[now].id>x)&&(opt==1)) return now; now=S[now].ch[opt]; while (S[now].ch[opt^1]!=0) now=S[now].ch[opt^1];//沿子树一直找 return now; } void DeleteRange(int l,int r) { Insert(l,0);//防止没有边界 Insert(r,0); int prep=Next(l,0);//移到根 int nex=Next(r,1);//移到根的右儿子 Splay(prep,0); Splay(nex,prep); S[nex].ch[0]=0;//删去根的右儿子的左儿子 update(nex); update(prep); } ll Query(int l,int r)//这两个没有删，不能加边界。 { int prep=Next(l,0);//移到根 int nex=Next(r,1);//移到根的右儿子 Splay(prep,0); Splay(nex,prep); return S[S[nex].ch[0]].totVal;//... } int Modify(int l,int r,int delta) { int prep=Next(l,0); int nex=Next(r,1); Splay(prep,0); Splay(nex,prep); marking(S[nex].ch[0],delta); } }; SplayTree SP; int main() { int k,l,r,n,id,val,a,b; scanf("%d",&n); for (int i=1;i<=n;i++){ char opt[2]; scanf("%s",opt); if (opt[0]=='I'){ scanf("%d%d",&id,&val); SP.Insert(id,val); } else if (opt[0]=='Q'){ scanf("%d%d",&a,&b); printf("%lld ",SP.Query(a,b)); } else if (opt[0]=='M'){ scanf("%d%d%d",&a,&b,&val); SP.Modify(a,b,val); } else { scanf("%d%d",&a,&b); SP.DeleteRange(a,b); } } return 0; }
----------------------------------------------------2018.1.2更新----------------------------------------------
由于之前splay每这么深入，现在从新打板子。
二代代码：快了很多。
#include<iostream> #include<cstdio> using namespace std; #define INF 0x3f3f3f3f typedef long long ll; #define maxn 200010 struct SplayTree { int son[maxn][2],fa[maxn],key[maxn],siz[maxn]; ll val[maxn],lazy[maxn],sum[maxn]; int cnt,root,n; void Pushup(int rt) { int ls=son[rt][0],rs=son[rt][1]; siz[rt]=1,sum[rt]=val[rt]; if(ls) siz[rt]+=siz[ls],sum[rt]+=sum[ls]; if(rs) siz[rt]+=siz[rs],sum[rt]+=sum[rs]; } void Pushdown(int rt) { if(lazy[rt]){ int ls=son[rt][0],rs=son[rt][1]; if(ls)lazy[ls]+=lazy[rt],sum[ls]+=siz[ls]*lazy[rt],val[ls]+=lazy[rt]; if(rs)lazy[rs]+=lazy[rt],sum[rs]+=siz[rs]*lazy[rt],val[rs]+=lazy[rt]; lazy[rt]=0; } } int New_nod(int f,int k,int v) { son[++cnt][0]=son[cnt][1]=0; fa[cnt]=f; siz[cnt]=1; key[cnt]=k; val[cnt]=v; sum[cnt]=v; return cnt; } void init() { cnt=0; root=New_nod(0,-INF,0);//先加了2个边界点 son[root][1]=New_nod(root,INF,0); Pushup(root); } void Rotate(int x,int c)//c==0代表右旋 { int f=fa[x],nxtf=fa[f]; Pushdown(f); Pushdown(x); if(nxtf!=0) son[nxtf][son[nxtf][0]!=f]=x; fa[x]=nxtf; son[f][c]=son[x][!c]; fa[son[x][!c]]=f; son[x][!c]=f; fa[f]=x; Pushup(f);//Pushup(x);这里没有更新是因为Splay函数最后要更新x。 } void Splay(int x,int y)//把x旋转为y的子节点，首先要确保y是x的祖先 { Pushdown(x); while(fa[x]!=y){ int f=fa[x]; int c1=(son[fa[f]][0]==f),c2=(son[f][0]==x); if(fa[f]==y) Rotate(x,!c2); else{ if(c1^c2) Rotate(x,!c2),Rotate(x,c2);//相异时两次提高x else Rotate(f,!c1),Rotate(x,!c1);// 相异时依此提高f，x } } Pushup(x); if(!y) root=x; } int Insert(int x,int val) { int now=root,f; while(now!=0){ Pushdown(now); siz[now]++; sum[now]+=val; f=now; now=son[now][x>=key[now]]; } int id=New_nod(f,x,val); son[f][x>=key[f]]=id; Splay(id,0); return id; } int Find(int x) { int now=root; while(now){ Pushdown(now); if(key[now]==x)return now; now=son[now][x>=key[now]]; } return now; } int Findpre(int x)//查询严格小于x的节点,可以和下面的函数合并。 { int now=root,ans; while(now){ Pushdown(now); if(key[now]<x)ans=now,now=son[now][1]; else now=son[now][0]; } return ans; } int Findnxt(int x)//查询严格大于x的节点，可以和上面的函数合并。 { int now=root,ans; while(now){ Pushdown(now); if(key[now]>x)ans=now,now=son[now][0]; else now=son[now][1]; } return ans; } void Delete(int l,int r) { int x=Findpre(l),y=Findnxt(r); Splay(x,0); Splay(y,x); son[y][0]=0;//内存不够时写内存池 Pushup(y); Pushup(x); } ll Query(int l,int r) { int x=Findpre(l),y=Findnxt(r); Splay(x,0); Splay(y,x); return sum[son[y][0]]; } void Update(int l,int r,int v) { int x=Findpre(l),y=Findnxt(r); Splay(x,0); Splay(y,x); int id=son[y][0]; sum[id]+=(ll)siz[id]*v; val[id]+=v; lazy[id]+=v; Pushup(y); Pushup(x); } } Tree; int main() { Tree.init();scanf("%d",&Tree.n); for(int i=1;i<=Tree.n;i++){ char s[10]; int x,y,d; scanf("%s",s); scanf("%d%d",&x,&y); if(s[0]=='I') Tree.Insert(x,y); else if(s[0]=='Q') printf("%lld ",Tree.Query(x,y)); else if(s[0]=='D') Tree.Delete(x,y); else scanf("%d",&d),Tree.Update(x,y,d); } return 0; }