本文共 2594 字，大约阅读时间需要 8 分钟。
直接上板子，这个要好好体会
操作是最经典的。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 using namespace std; 12 #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout) 13 inline void read(int &ans) { 14 ans=0;char x=getchar();bool f=0; 15 while(x<'0'||x>'9') { if(x=='-')f=1;x=getchar();} 16 while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar(); 17 f?ans=-ans:0; 18 } 19 const int MAXN=1e5+10; 20 const int INF=2e9; 21 struct splay_tree{ 22 struct node{ 23 int val,max,add,size,son[2]; 24 bool rev;//区间是否翻转 25 void init(int _val){ 26 val=max=_val ,size=1; 27 add=rev=son[0]=son[1]=0; 28 } 29 }T[MAXN]; 30 int fa[MAXN],root; 31 32 void pushup(int x){ 33 T[x].max=T[x].val ,T[x].size=1; 34 for(int k=0;k<2;k++) 35 if(T[x].son[k]){ 36 T[x].max=max(T[x].max,T[T[x].son[k]].max); 37 T[x].size+=T[T[x].son[k]].size; 38 } 39 } 40 41 void pushdown(int x){ 42 if(x==0)return; 43 if(T[x].add){ 44 for(int k=0;k<2;k++) 45 if(T[x].son[k]){ 46 T[T[x].son[k]].val+=T[x].add; 47 T[T[x].son[k]].max+=T[x].add; 48 T[T[x].son[k]].add+=T[x].add; 49 } 50 T[x].add=0; 51 } 52 if(T[x].rev){ 53 for(int k=0;k<2;k++) 54 if(T[x].son[k]) T[T[x].son[k]].rev^=1; 55 swap(T[x].son[0],T[x].son[1]); 56 T[x].rev=0; 57 } 58 } 59 60 void rotate(int x,int k){ 61 int y=fa[x] ,z=fa[y]; 62 T[y].son[!k]=T[x].son[k] ,fa[T[x].son[k]]=y; 63 T[x].son[k]=y ,fa[y]=x; 64 T[z].son[T[z].son[1]==y]=x ,fa[x]=z; 65 pushup(y); 66 } 67 68 void splay(int x,int goal){ 69 if(x==goal)return; 70 while(fa[x]!=goal){ 71 int y=fa[x] ,z=fa[y]; 72 pushdown(z) ,pushdown(y) ,pushdown(x); 73 int rx=T[y].son[0]==x ,ry=T[z].son[0]==y; 74 if(z==goal)rotate(x,rx); 75 else{ 76 if(rx==ry)rotate(y,ry); 77 else rotate(x,rx); 78 rotate(x,ry); 79 } 80 } 81 pushup(x); 82 if(goal==0)root=x; 83 } 84 85 int select(int p){ 86 int u=root; 87 pushdown(u); 88 while(p!=T[T[u].son[0]].size){ 89 if(p r) return 0;124 if(l==r) return l;125 int mid=(l+r)>>1 ,ls, rs;126 ls=T[mid].son[0]=build(l,mid-1);127 rs=T[mid].son[1]=build(mid+1,r);128 fa[ls]=fa[rs]=mid;129 pushup(mid);130 return mid;131 }132 133 void init(int n){134 T[0].init(-INF) ,T[1].init(-INF) ,T[n+2].init(-INF);135 for(int i=2;i<=n+1;i++)T[i].init(0);136 root=build(1,n+2) ,fa[root]=0;137 fa[0]=0 ,T[0].son[1]=root ,T[0].size=0;138 }139 };140 141 splay_tree bzoj1251;142 int n,m,a,b,c,d;143 int main() {144 read(n),read(m);145 bzoj1251.init(n);146 for(int i=0;i
转载于:https://www.cnblogs.com/JasonCow/p/6483949.html