CodeVS 1082 线段树练习3 【Splay模板】
学习了下Splay,发现原来学的都是错的(迷
(发完链接就贴代码系列)
#include <stdio.h> #include <iostream> using namespace std; #define Max 200010 #define B ch[ch[root][1]][0] int ch[Max][2],fa[Max],root,o[Max],sz[Max],n; long long sum[Max],tag[Max],val[Max],an; void pushdown(int x) { if (!x || !tag[x]) return; val[x]+=tag[x]; if(ch[x][0]) tag[ch[x][0]]+=tag[x],sum[ch[x][0]]+=tag[x]*sz[ch[x][0]]; if(ch[x][1]) tag[ch[x][1]]+=tag[x],sum[ch[x][1]]+=tag[x]*sz[ch[x][1]]; tag[x]=0; } void update(int x) { if(!x) return ; sz[x]=1+sz[ch[x][0]]+sz[ch[x][1]]; sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]]; } void rotate(int x) { if(!fa[x]) return; int y=fa[x],p=ch[y][0]==x; pushdown(y); pushdown(x); int b=ch[x][p];ch[y][p^1]=b; if(b) fa[b]=y; fa[x]=fa[y]; if(fa[y]) ch[fa[y]][ch[fa[y]][1]==y]=x; ch[x][p]=y;fa[y]=x; update(y); if(y==root) root=x; } void splayy(int x,int f) { pushdown(x); while(fa[x]!=f) { if(fa[fa[x]]!=f) { int y=fa[x]; if((ch[y][0]==x)^(ch[fa[y]][0]==y)) rotate(x); else rotate(y); } rotate(x); } update(x); if(!f) root=x; } void splayk(int k,int f) { int x=root;pushdown(x); while(sz[ch[x][0]]!=k-1) { if(sz[ch[x][0]]<k) { k-=sz[ch[x][0]]+1; x=ch[x][1]; } else x=ch[x][0]; pushdown(x); } splayy(x,f); } void addnode(int &ad,int f,int x) { ad=++an;sz[ad]=1,fa[ad]=f,val[ad]=sum[ad]=x; } void build(int &ad,int f,int l,int r) { if(l>r) {ad=0;return;} int mid=l+r>>1; addnode(ad,f,o[mid]); build(ch[ad][0],ad,l,mid-1); build(ch[ad][1],ad,mid+1,r); update(ad); } void init() { an=0; addnode(root,0,0); addnode(ch[root][1],root,0); update(root); build(B,ch[root][1],1,n); update(ch[root][1]); update(root); } void getlr(int l,int r) { splayk(l,0); splayk(r+2,root); } int main() { scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",&o[i]); init(); int Q;char buf[123];int a,b,c;scanf("%d",&Q); while(Q--) { scanf("%s",buf); if(buf[0]=='2') { scanf("%d%d",&a,&b); getlr(a,b); printf("%lld\n",sum[B]); } else { scanf("%d%d%d",&a,&b,&c); getlr(a,b); tag[B]+=c; sum[B]+=(long long)sz[B]*c; } } }