https://www.luogu.org/problemnew/show/P4146
3种操作： 1.将[L,R]这个区间内的所有数加上V。 2.将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3.求[L,R]这个区间中的最大值。
由于交换两个子树必定会改变BST的性质 所以不能用key值做find 只能用size表示数组元素下标 查询下标为k的元素用find_Kth
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> //for swap(); using namespace std; int fa[50005],ch[50005][2],size[50005]; bool reversed[50005]; int tag[50005],mx[50005],val[50005];//特别注意0点初始化的值，而且所有操作不能修改它 int num,root; int n,m; inline void update(int x) { int lson=ch[x][0],rson=ch[x][1]; size[x]=size[lson]+size[rson]+1; mx[x]=max(val[x],max(mx[lson],mx[rson])); } inline void pushdown(int x) { if (reversed[x]) { if (ch[x][0]) reversed[ch[x][0]]^=1; if (ch[x][1]) reversed[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]);//#include<algorithm> reversed[x]=0; } if (tag[x]) { int lson=ch[x][0],rson=ch[x][1]; if (lson) { tag[lson]+=tag[x]; val[lson]+=tag[x]; mx[lson]+=tag[x]; } if (rson) { tag[rson]+=tag[x]; val[rson]+=tag[x]; mx[rson]+=tag[x]; } tag[x]=0; } } inline void rotate(int x) { int fa1=fa[x],fa2=fa[fa1],side=(ch[fa[x]][1]==x); pushdown(fa1);pushdown(x); ch[fa1][side]=ch[x][side^1];fa[ch[fa1][side]]=fa1; fa[fa1]=x;ch[x][side^1]=fa1; fa[x]=fa2; if (fa2) ch[fa2][ch[fa2][1]==fa1]=x; update(fa1);update(x); } inline void splay(int x,int goal) {//由于Kth里面做了pushdown，这里可以不做 while (fa[x]!=goal) { int fa1=fa[x],fa2=fa[fa1]; if (fa2!=goal) { if ((ch[fa2][0]==fa1)^(ch[fa1][0]==x)) rotate(x); else rotate(fa1); } rotate(x); } if (goal==0) root=x; } inline int Kth(int k) { int p=root; while (666233) { pushdown(p); if (size[ch[p][0]]>=k) p=ch[p][0]; else if (size[ch[p][0]]+1==k) return p; else k-=size[ch[p][0]]+1,p=ch[p][1]; } } void build(int &p,int l,int r,int ff) { if (l>r) {p=0;return;} p=++num; fa[p]=ff; if (l==r) { size[p]=1; ch[p][0]=ch[p][1]=0; if (l==0 || l==n+1) mx[p]=val[p]=-1e9; return; } int mid=(l+r)>>1; if (mid==0 || mid==n+1) mx[p]=val[p]=-1e9; build(ch[p][0],l,mid-1,p); build(ch[p][1],mid+1,r,p); update(p); } int main() { cin >> n >> m; build(root,0,n+1,0);mx[0]=-1e9; for (int i=1;i<=m;i++) { int op,x,y,v=0; scanf("%d%d%d",&op,&x,&y); if (op==1) scanf("%d",&v); int la=Kth(x);splay(la,0);//x+1-1 int ne=Kth(y+2);splay(ne,la);//y+1+1 int p=ch[ne][0]; if (op==1) tag[p]+=v,mx[p]+=v,val[p]+=v; else if (op==2) reversed[p]^=1; else printf("%d\n",mx[p]); } return 0; }其他操作
inline void ins(int c) { int p=root,ff=0; while (p && key[p]!=c) { ff=p; p=ch[p][c>key[p]]; } if (p) cnt[p]++; else { p=++num; if (ff) ch[ff][c>key[ff]]=p;//如果父节点非0 else root=p; ch[p][0]=ch[p][1]=0; fa[p]=ff; key[p]=c; cnt[p]=size[p]=1; } splay(p,0); } inline void find(int c) { //查找c的位置，并将其旋转到根节点 int p=root; while (ch[p][c>key[p]] && c!=key[p]) p=ch[p][c>key[p]]; splay(p,0); } inline int pre_nxt(int c,int op) { //查找c的前驱(0)或者后继(1) find(c); int p=root; if (key[p]!=c) { //c不存在需要特判 if (key[p]>c && op) return p; if (key[p]<c && !op) return p; } p=ch[p][op]; while (ch[p][op^1]) p=ch[p][op^1]; return p; } inline void del(int c) { find(c); if (key[root]!=c) return; if (cnt[root]>1) {cnt[root]--;size[root]--;return;} if (!ch[root][0] && !ch[root][1]) {root=0;return;} if (!ch[root][0]) {root=ch[root][1];fa[root]=0;return;} if (!ch[root][1]) {root=ch[root][0];fa[root]=0;return;} int p=pre_nxt(c,0),oldroot=root; splay(p,0); fa[ch[oldroot][1]]=root; ch[root][1]=ch[oldroot][1]; update(root); }还有合并，拆分等操作未写出
