线段树/树状数组裸题，用splay写
splay也是基本操作pushup pushdown
话说我就是找不到全一点的模板，我自己写又全是bug，导致代码风格一直变来变去= =
关键是建树和区间操作（区间和，区间翻转，区间合并这几个写法都很难统一）
#include<map> #include<set> #include<list> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define fi first #define se second #define mp make_pair #define pb push_back #define pii pair<int,int> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 using namespace std; using namespace __gnu_cxx; const double g=10.0,eps=1e-7; const int N=100000+10,maxn=100000+10,inf=0x3f3f3f; struct Node{ Node *ch[2],*fa; int id,s,v,add; ll sum; void pushdown() { if(add) { if(ch[0]) { ch[0]->v += add; ch[0]->add += add; ch[0]->sum += (ll)add*ch[0]->s; } if(ch[1]) { ch[1]->v += add; ch[1]->add += add; ch[1]->sum += (ll)add*ch[1]->s; } add=0; } } void pushup() { s = ch[0]->s + ch[1]->s + 1; sum = v + ch[0]->sum + ch[1]->sum; } }; Node *root,NODE[N],*null=&NODE[0]; int num[N],n,top; struct SplayTree{ void Rotate(Node *x,int f) { Node* y= x->fa; y->pushdown();x->pushdown(); y->ch[!f] = x->ch[f]; x->ch[f]->fa = y; x->fa = y->fa; if(x->fa!=null)y->fa->ch[y->fa->ch[1]==y]=x; x->ch[f] = y; y->fa=x; y->pushup(); } void splay(Node* x,Node* goal)//把x splay到goal下面 { x->pushdown(); while(x->fa!=goal) { if(x->fa->fa == goal)Rotate(x,x->fa->ch[0]==x); else { Node *y=x->fa,*z=y->fa; int f=(z->ch[0]==y); y->ch[f]==x ? Rotate(x,!f):Rotate(y,f); Rotate(x,f); } } x->pushup(); if(goal==null)root=x; } void RTO(int k,Node *goal)//把排名为k的节点splay到goal下面 { Node *x=root; x->pushdown(); while(x->ch[0]->s+1!=k) { if(k < x->ch[0]->s+1)x=x->ch[0]; else { k -= x->ch[0]->s+1; x = x->ch[1]; } x->pushdown(); } splay(x,goal); } Node* newnode(Node* fa,int v) { Node *x=&NODE[++top]; x->id=top; x->ch[0]=x->ch[1]=null; x->s=1; x->v=x->sum=v; x->add=0; x->fa=fa; return x; } void build(Node* &x,int l,int r,Node* fa) { if(l>r)return ; int m=(l+r)>>1; x=newnode(fa,num[m]); build(x->ch[0],l,m-1,x); build(x->ch[1],m+1,r,x); x->pushup(); } void debug(Node* x) { if(x!=null) { debug(x->ch[0]); cout<<x->v<<" "<<x->sum<<endl; debug(x->ch[1]); } } void init(int n) { top=0; null->id=0; null->fa = null->ch[0] = null->ch[1] = NULL; null->s = null->add = null->v = null->sum = 0; root = newnode(null,-1); root->ch[1] = newnode(root,-1); root->s=2; for(int i=1;i<=n;i++)scanf("%d",&num[i]); build(root->ch[1]->ch[0],1,n,root->ch[1]); root->ch[1]->pushup();root->pushup(); } void update() { int l,r,c; scanf("%d%d%d",&l,&r,&c); RTO(l,null); RTO(r+2,root); root->ch[1]->ch[0]->add += c; root->ch[1]->ch[0]->v += c; root->ch[1]->ch[0]->sum += (ll)c*root->ch[1]->ch[0]->s; } void query() { int l,r; scanf("%d%d",&l,&r); RTO(l,null); RTO(r+2,root); printf("%lld ",root->ch[1]->ch[0]->sum); } }spt; int main() { int n,q; scanf("%d%d",&n,&q); spt.init(n); while(q--) { char s[2]; scanf("%s",s); if(s[0]=='Q')spt.query(); else spt.update(); } return 0; } /************ 10 5 1 5 64 8 2 47 6 4 6 7 ************/