本文共 3097 字，大约阅读时间需要 10 分钟。
线段树/树状数组裸题，用splay写
splay也是基本操作pushup pushdown
话说我就是找不到全一点的模板，我自己写又全是bug，导致代码风格一直变来变去= =
关键是建树和区间操作（区间和，区间翻转，区间合并这几个写法都很难统一）
#include#include #include #include #include #include #include #include #include #include #include #define fi first#define se second#define mp make_pair#define pb push_back#define pii pair #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|1using 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< v<<" "< sum< 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\n",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 51 5 64 8 2 47 6 4 6 7************/
转载于:https://www.cnblogs.com/acjiumeng/p/7760407.html
