树套树——BZOJ3196/Luogu3380二逼平衡树

http://www.lydsy.com/JudgeOnline/problem.php?id&＃61;3196
https://www.luogu.org/problem/show?pid&＃61;3380
tyvj原题&＃xff1a;传送门
这么多乱七八糟的操作&＃xff0c;交给平衡树好了
再加上区间&＃xff0c;外面套个线段树好了
不过呢&＃xff0c;可能我写得太渣了吧&＃xff0c;splay一直TLE
没办法&＃xff0c;换了个非旋式Treap搞搞掉算了。。。

#include
using namespace std;
const int oo&＃61;2147483647;
struct tree{int l,r,v,w,s,nod;
}t[2000001];
int a[200001],root[200001];
int sum&＃61;0,n,m,ans;
inline void update(int x){t[x].s&＃61;t[t[x].l].s&＃43;t[t[x].r].s&＃43;t[x].w;}
inline void rturn(int &x){int tt&＃61;t[x].l;t[x].l&＃61;t[tt].r;t[tt].r&＃61;x;t[tt].s&＃61;t[x].s;update(x);x&＃61;tt;
}
inline void lturn(int &x){int tt&＃61;t[x].r;t[x].r&＃61;t[tt].l;t[tt].l&＃61;x;t[tt].s&＃61;t[x].s;update(x);x&＃61;tt;
}
inline void sinsert(int &x,int y){if(x&＃61;&＃61;0){sum&＃43;&＃43;;x&＃61;sum;t[x].s&＃61;t[x].w&＃61;1;t[x].v&＃61;y;t[x].nod&＃61;rand();return;}t[x].s&＃43;&＃43;;if(t[x].v&＃61;&＃61;y)t[x].w&＃43;&＃43;;else if(y>t[x].v){sinsert(t[x].r,y);if(t[t[x].r].nodelse{sinsert(t[x].l,y);if(t[t[x].l].nod}
inline void sshan(int &x,int y){if(x&＃61;&＃61;0)return;if(t[x].v&＃61;&＃61;y){if(t[x].w>1){t[x].w--;t[x].s--;return;}if(t[x].l*t[x].r&＃61;&＃61;0)x&＃61;t[x].l&＃43;t[x].r;else if(t[t[x].l].nodelse lturn(x),sshan(x,y);}else if(y>t[x].v)t[x].s--,sshan(t[x].r,y);else t[x].s--,sshan(t[x].l,y);
}
inline void srank(int x,int y){if(x&＃61;&＃61;0)return;if(t[x].v&＃61;&＃61;y){ans&＃43;&＃61;t[t[x].l].s;return;}else if(y>t[x].v){ans&＃43;&＃61;t[t[x].l].s&＃43;t[x].w;srank(t[x].r,y);}else srank(t[x].l,y);
}
inline void spre(int x,int y){if(x&＃61;&＃61;0)return;if(t[x].velse spre(t[x].l,y);
}
inline void ssucc(int x,int y){if(x&＃61;&＃61;0)return;if(t[x].v>y){ans&＃61;min(ans,t[x].v);ssucc(t[x].l,y);}else ssucc(t[x].r,y);
}
inline void winsert(int l,int r,int x,int v,int nod){sinsert(root[nod],v);if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;if(x<&＃61;mid)winsert(l,mid,x,v,nod*2);else winsert(mid&＃43;1,r,x,v,nod*2&＃43;1);
}
inline void wrank(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){srank(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wrank(l,mid,x,y,k,nod*2);else if(x>mid)wrank(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wrank(l,mid,x,mid,k,nod*2);wrank(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
inline int wnum(int x,int y,int k){int l&＃61;0,r&＃61;oo,cnt;while(l<&＃61;r){ans&＃61;1;int mid&＃61;(l&＃43;r)>>1;wrank(1,n,x,y,mid,1);if(ans<&＃61;k)cnt&＃61;mid,l&＃61;mid&＃43;1;else r&＃61;mid-1;}return cnt;
}
inline void whuan(int l,int r,int x,int y,int v,int nod){sshan(root[nod],y);sinsert(root[nod],v);if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;if(x<&＃61;mid)whuan(l,mid,x,y,v,nod*2);else whuan(mid&＃43;1,r,x,y,v,nod*2&＃43;1);
}
inline void wpre(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){spre(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wpre(l,mid,x,y,k,nod*2);else if(x>mid)wpre(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wpre(l,mid,x,mid,k,nod*2);wpre(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
inline void wsucc(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){ssucc(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wsucc(l,mid,x,y,k,nod*2);else if(x>mid)wsucc(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wsucc(l,mid,x,mid,k,nod*2);wsucc(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&a[i]);winsert(1,n,i,a[i],1);}int x,y,z,k;for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d%d",&z,&x,&y);if(z&＃61;&＃61;1)scanf("%d",&k),ans&＃61;1,wrank(1,n,x,y,k,1),printf("%d\n",ans);else if(z&＃61;&＃61;2)scanf("%d",&k),printf("%d\n",wnum(x,y,k));else if(z&＃61;&＃61;3)whuan(1,n,x,a[x],y,1),a[x]&＃61;y;else if(z&＃61;&＃61;4)scanf("%d",&k),ans&＃61;-oo,wpre(1,n,x,y,k,1),printf("%d\n",ans);else if(z&＃61;&＃61;5)scanf("%d",&k),ans&＃61;oo,wsucc(1,n,x,y,k,1),printf("%d\n",ans);}return 0;
}

贴一下我的splay代码吧&＃xff0c;欢迎大佬帮我找错&＃xff0c;谢谢辣>_<&＃xff01;

#include
using namespace std;
const int oo&＃61;2147483647;
int t[2000001][2],fa[2000001],v[2000001],val[2000001],s[2000001];
int a[200001],root[200001];
int tt&＃61;0,n,m,ans;
inline void pushup(int x){s[x]&＃61;s[t[x][0]]&＃43;s[t[x][1]]&＃43;v[x];}
inline void turn(int x,int &p){int y&＃61;fa[x],z&＃61;fa[y],l,r;if(t[y][0]&＃61;&＃61;x)l&＃61;0;else l&＃61;1;r&＃61;l^1;if(y&＃61;&＃61;p)p&＃61;x;else if(t[z][0]&＃61;&＃61;y)t[z][0]&＃61;x;else t[z][1]&＃61;x;fa[x]&＃61;z;fa[y]&＃61;x;fa[t[x][r]]&＃61;y;t[y][l]&＃61;t[x][r];t[x][r]&＃61;y;pushup(y);pushup(x);
}
inline void splay(int x,int &p){int y,z;while(x!&＃61;p){y&＃61;fa[x];z&＃61;fa[y];if(y!&＃61;p){if((t[y][0]&＃61;&＃61;x)^(t[z][0]&＃61;&＃61;y))turn(x,p);else turn(y,p);}turn(x,p);}
}
inline void sinsert(int& rt,int k){if(!rt){tt&＃43;&＃43;;rt&＃61;tt;val[tt]&＃61;k;s[tt]&＃61;v[tt]&＃61;1;return;}int p&＃61;rt,z;while(p){z&＃61;p;s[p]&＃43;&＃43;;if(k0];else if(k>val[p])p&＃61;t[p][1];else{v[p]&＃43;&＃43;;pushup(p);splay(p,rt);return;}}if(val[z]>k)t[z][0]&＃61;&＃43;&＃43;tt;else t[z][1]&＃61;&＃43;&＃43;tt;val[tt]&＃61;k;s[tt]&＃61;v[tt]&＃61;1;fa[tt]&＃61;z;splay(tt,rt);
}
inline void sshan(int& rt,int y){int x&＃61;rt;while(val[x]!&＃61;y){if(val[x]>y)x&＃61;t[x][0];else x&＃61;t[x][1];}splay(x,rt);if(v[x]>1){v[x]--;pushup(x);return;}if(t[x][0]*t[x][1]&＃61;&＃61;0)rt&＃61;t[x][0]&＃43;t[x][1];else{int y&＃61;t[x][1];while(t[y][0])y&＃61;t[y][0];t[y][0]&＃61;t[x][0];fa[t[x][0]]&＃61;y;s[t[y][0]]&＃61;s[t[x][0]];v[t[y][0]]&＃61;v[t[x][0]];pushup(y);rt&＃61;t[x][1];}fa[rt]&＃61;0;
}
inline void srank(int x,int y){if(x&＃61;&＃61;0)return;if(val[x]&＃61;&＃61;y){ans&＃43;&＃61;s[t[x][0]];return;}else if(y>val[x]){ans&＃43;&＃61;s[t[x][0]]&＃43;v[x];srank(t[x][1],y);}else srank(t[x][0],y);
}
inline void spre(int x,int y){if(x&＃61;&＃61;0)return;if(val[x]1],y);}else spre(t[x][0],y);
}
inline void ssucc(int x,int y){if(x&＃61;&＃61;0)return;if(val[x]>y){ans&＃61;min(ans,val[x]);ssucc(t[x][0],y);}else ssucc(t[x][1],y);
}
inline void winsert(int l,int r,int x,int v,int nod){sinsert(root[nod],v);if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;if(x<&＃61;mid)winsert(l,mid,x,v,nod*2);else winsert(mid&＃43;1,r,x,v,nod*2&＃43;1);
}
inline void wrank(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){srank(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wrank(l,mid,x,y,k,nod*2);else if(x>mid)wrank(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wrank(l,mid,x,mid,k,nod*2);wrank(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
inline void wnum(int x,int y,int k){int l&＃61;0,r&＃61;oo,cnt;while(l<&＃61;r){ans&＃61;1;int mid&＃61;(l&＃43;r)>>1;wrank(1,n,x,y,mid,1);if(ans<&＃61;k)cnt&＃61;mid,l&＃61;mid&＃43;1;else r&＃61;mid-1;}return cnt;
}
inline void whuan(int l,int r,int x,int y,int v,int nod){sshan(root[nod],y);sinsert(root[nod],v);if(l&＃61;&＃61;r)return;int mid&＃61;(l&＃43;r)>>1;if(x<&＃61;mid)whuan(l,mid,x,y,v,nod*2);else whuan(mid&＃43;1,r,x,y,v,nod*2&＃43;1);
}
inline void wpre(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){spre(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wpre(l,mid,x,y,k,nod*2);else if(x>mid)wpre(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wpre(l,mid,x,mid,k,nod*2);wpre(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
inline void wsucc(int l,int r,int x,int y,int k,int nod){if(l&＃61;&＃61;x&&r&＃61;&＃61;y){ssucc(root[nod],k);return;}int mid&＃61;(l&＃43;r)>>1;if(mid>&＃61;y)wsucc(l,mid,x,y,k,nod*2);else if(x>mid)wsucc(mid&＃43;1,r,x,y,k,nod*2&＃43;1);else{wsucc(l,mid,x,mid,k,nod*2);wsucc(mid&＃43;1,r,mid&＃43;1,y,k,nod*2&＃43;1);}
}
int main()
{scanf("%d%d",&n,&m);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&a[i]);winsert(1,n,i,a[i],1);}int x,y,z,k;for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;){scanf("%d%d%d",&z,&x,&y);if(z&＃61;&＃61;1)scanf("%d",&k),ans&＃61;1,wrank(1,n,x,y,k,1),printf("%d\n",ans);else if(z&＃61;&＃61;2)scanf("%d",&k),printf("%d\n",wnum(x,y,k));else if(z&＃61;&＃61;3)whuan(1,n,x,a[x],y,1),a[x]&＃61;y;else if(z&＃61;&＃61;4)scanf("%d",&k),ans&＃61;-oo,wpre(1,n,x,y,k,1),printf("%d\n",ans);else if(z&＃61;&＃61;5)scanf("%d",&k),ans&＃61;oo,wsucc(1,n,x,y,k,1),printf("%d\n",ans);}return 0;
}