用splay做了一遍。
建树时是按照数列序号从小到大排好的，每个节点左子树的序号小于右子树的序号及这个节点本身。
由于查询[l,r]要伸展l-1,r+1所以我们要多加2个结点，保证边界处理时不出问题。由于这样每次查找l-1时，
要找的应该是l（r+1也是找r+2）。
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define ll __int64 #define key_value ch[ch[root][1]][0] using namespace std; const int MAXN=100010; int pre[MAXN],ch[MAXN][2],key[MAXN],tot1,root; int siz[MAXN],tot2,a[MAXN],n,s[MAXN]; ll lazy[MAXN],sum[MAXN]; void Treavel(int x) { if(x) { Treavel(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d add=%2d sum=%I64d ",x,ch[x][0],ch[x][1],pre[x],siz[x],key[x],lazy[x],sum[x]); Treavel(ch[x][1]); } } void debug() { printf("root:%d ",root); Treavel(root); } void Newnode(int &rt,int father,int k) { if(tot2) rt = s[--tot2]; else rt = ++tot1; pre[rt] = father; key[rt] = k; siz[rt] = 1; lazy[rt] = 0; ch[rt][0] = ch[rt][1] = 0; } void pushup(int rt) { siz[rt] = siz[ch[rt][0]] + siz[ch[rt][1]] + 1; sum[rt] = sum[ch[rt][0]] + sum[ch[rt][1]] + key[rt]; } void pushdown(int rt) { if(lazy[rt]){ lazy[ch[rt][0]] += lazy[rt]; lazy[ch[rt][1]] += lazy[rt]; key[ch[rt][0]] += lazy[rt]; key[ch[rt][1]] += lazy[rt]; sum[ch[rt][0]] += (ll)siz[ch[rt][0]]*lazy[rt]; sum[ch[rt][1]] += (ll)siz[ch[rt][1]]*lazy[rt]; lazy[rt] = 0; } } void build(int &rt,int l,int r,int father) { if(l > r) return ; int m = (l+r)/2; Newnode(rt,father,a[m]); build(ch[rt][0],l,m-1,rt); build(ch[rt][1],m+1,r,rt); pushup(rt); } void Init() { int i,j; for(i=1; i<=n; i++){ scanf("%d",&a[i]); } root = tot1 = tot2 = 0; ch[root][0] = ch[root][1] = key[root] = siz[root] = lazy[root] = pre[root] = sum[root] = 0; Newnode(root,0,-1); Newnode(ch[root][1],root,-1);//头尾各加入一个点 build(key_value,1,n,ch[root][1]);//让所有数据夹在这两个点之间 由于树的结构 所以在ch[ch[root][1]][0] pushup(ch[root][1]); pushup(root); } void Rotate(int rt,int kind) { int y = pre[rt]; pushdown(y); pushdown(rt); ch[y][!kind] = ch[rt][kind]; pre[ch[rt][kind]] = y; if(pre[y]){ ch[pre[y]][ch[pre[y]][1]==y] = rt; } pre[rt] = pre[y]; ch[rt][kind] = y; pre[y] = rt; pushup(y); } void splay(int rt,int goal) { pushdown(rt); while(pre[rt] != goal) { if(pre[pre[rt]] == goal){ Rotate(rt,ch[pre[rt]][0]==rt); } else { int y = pre[rt]; int kind = ch[pre[y]][0]==y; if(ch[y][kind] == rt){ Rotate(rt,!kind); Rotate(rt,kind); } else { Rotate(y,kind); Rotate(rt,kind); } } } pushup(rt); if(goal == 0) root = rt; } int Get_kth(int rt,int k) { pushdown(rt); int t = siz[ch[rt][0]] + 1; if(t == k){ return rt; } else if(t > k){ return Get_kth(ch[rt][0],k); } else return Get_kth(ch[rt][1],k-t); } void updata(int l,int r,int v) { splay(Get_kth(root,l),0); splay(Get_kth(root,r+2),root); key[key_value] += v; lazy[key_value] += v; sum[key_value] += (ll)v*siz[key_value]; } ll query(int l,int r) { splay(Get_kth(root,l),0);//由于开始的时候多添加了2个结点，所以编号都是在这2个结点之间的 所以查询的时候都要大1 splay(Get_kth(root,r+2),root); return sum[key_value]; } int main() { int i,j,q; while(~scanf("%d%d",&n,&q)) { Init(); //debug(); char s[10]; while(q--) { scanf("%s",s); if(s[0] == 'C'){ int x,y,z; scanf("%d%d%d",&x,&y,&z); updata(x,y,z); } else { int x,y; scanf("%d%d",&x,&y); printf("%I64d ",query(x,y)); } } } }