树套树模板

题目链接

splay

#include <iostream>
#include <algorithm>
using namespace std;#define N 50005
#define INF 2147483647
#define ls(x) tr[x].s[0]
#define rs(x) tr[x].s[1]
struct node{int s[2], p;int v, siz;void init(int p1, int v1){p=p1; v=v1; siz=1;}
}tr[N*40];
int n, m, w[N], idx;inline void pushup(int x){tr[x].siz=tr[ls(x)].siz+tr[rs(x)].siz+1;
}
inline void rotate(int x){int y=tr[x].p,z=tr[y].p;int k=tr[y].s[1]==x;tr[z].s[tr[z].s[1]==y]=x, tr[x].p=z;tr[y].s[k]=tr[x].s[k^1], tr[tr[x].s[k^1]].p=y;tr[x].s[k^1]=y, tr[y].p=x;pushup(y), pushup(x);
}
inline void splay(int &root,int x,int k){while(tr[x].p != k){int y=tr[x].p,z=tr[y].p;if(z != k)if((rs(y)==x)^(rs(z)==y)) rotate(x);else rotate(y);rotate(x);}if(!k) root=x;
}
inline void insert(int &root,int v){int u=root,p=0;while(u) p=u,u=tr[u].s[v>tr[u].v];u = ++idx;tr[p].s[v>tr[p].v]=u;tr[u].init(p,v);splay(root,u,0);
}
inline void del(int &root,int v){int u=root;while(u){if(tr[u].v==v) break;if(tr[u].v<v) u=rs(u);else u=ls(u);}splay(root,u,0);int l=ls(u),r=rs(u);while(rs(l)) l=rs(l);while(ls(r)) r=ls(r);splay(root,l,0);splay(root,r,l);ls(r)=0;splay(root,r,0);
}
inline int getrank(int root,int v){int u=root,res=0;while(u){if(tr[u].v<v) res+=tr[ls(u)].siz+1,u=rs(u);else u=ls(u);}return res;
}
inline int getpre(int root,int v){int u=root,res=-INF;while(u){if(tr[u].v<v) res=tr[u].v,u=rs(u);else u=ls(u);}return res;
}
inline int getnxt(int root,int v){int u=root,res=INF;while(u){if(tr[u].v>v) res=tr[u].v,u=ls(u);else u=rs(u);}return res;
}//线段树
#define lc u<<1
#define rc u<<1|1
int root[N*4];void build(int u,int l,int r){insert(root[u],-INF), insert(root[u],INF);for(int i=l;i<=r;i++)insert(root[u],w[i]);if(l==r) return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
int queryrank(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getrank(root[u],v)-1;int mid=l+r>>1, res=0;if(x<=mid) res += queryrank(lc,l,mid,x,y,v);if(y>mid) res += queryrank(rc,mid+1,r,x,y,v);return res;
}
int queryval(int u,int x,int y,int k){int l=0, r=1e8, ans; //二分while(l<=r){int mid=l+r>>1;if(queryrank(1,1,n,x,y,mid)+1<=k) l=mid+1, ans=mid;else r=mid-1;}return ans;
}
void change(int u,int l,int r,int pos,int v){del(root[u],w[pos]);insert(root[u],v);if(l==r) return;int mid=l+r>>1;if(pos<=mid) change(lc,l,mid,pos,v);else change(rc,mid+1,r,pos,v);
}
int querypre(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getpre(root[u],v);int mid=l+r>>1, res=-INF;if(x<=mid) res=max(res,querypre(lc,l,mid,x,y,v));if(y>mid) res=max(res,querypre(rc,mid+1,r,x,y,v));return res;
}
int querynxt(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getnxt(root[u],v);int mid=l+r>>1, res=INF;if(x<=mid) res=min(res,querynxt(lc,l,mid,x,y,v));if(y>mid) res=min(res,querynxt(rc,mid+1,r,x,y,v));return res;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);while(m -- ){int op,x,y,v;scanf("%d",&op);if(op==3)scanf("%d%d",&x,&v);else scanf("%d%d%d",&x,&y,&v);if(op==1)printf("%d\n",queryrank(1,1,n,x,y,v)+1);if(op==2) printf("%d\n",queryval(1,x,y,v));if(op==3)change(1,1,n,x,v), w[x]=v;if(op==4)printf("%d\n",querypre(1,1,n,x,y,v));if(op==5)printf("%d\n",querynxt(1,1,n,x,y,v));}return 0;
}

fhq treap

#include <iostream>
#include <algorithm>
using namespace std;const int N=2000005;
const int INF=0x7fffffff;
int n,m,w[N],idx;
int l[N],r[N],val[N],rnd[N],siz[N];inline void newnode(int &x,int v){x=++idx;val[x]=v;rnd[x]=rand();siz[x]=1;
}   
inline void pushup(int x){siz[x]=siz[l[x]]+siz[r[x]]+1;
}
inline void split(int p,int v,int &x,int &y){if(!p){x=y=0; return;}if(val[p]<=v)x=p, split(r[p],v,r[p],y);elsey=p, split(l[p],v,x,l[p]);pushup(p);
}
inline int merge(int x,int y){if(!x || !y) return x+y;if(rnd[x] < rnd[y]){r[x]=merge(r[x],y);pushup(x); return x;}else{l[y]=merge(x,l[y]);pushup(y); return y;} 
}
inline void insert(int &root,int v){int x,y,z;split(root,v,x,y);newnode(z,v);root=merge(merge(x,z),y);
}
inline void del(int &root,int v){int x,y,z;split(root,v,x,z);split(x,v-1,x,y);y=merge(l[y],r[y]);root=merge(x,merge(y,z));
}
inline int getrank(int &root,int v){int x,y,z,ans;split(root,v-1,x,y);ans=siz[x]+1;root=merge(x,y);return ans;
}
inline int getval(int x,int k){if(k==siz[l[x]]+1) return val[x];  if(k<=siz[l[x]]) return getval(l[x],k);return getval(r[x],k-siz[l[x]]-1);
}
inline int getpre(int &root,int v){int x,y,z,ans;split(root,v-1,x,y);ans = siz[x]?getval(x,siz[x]):-INF;root = merge(x,y);return ans;
}
inline int getnxt(int &root,int v){int x,y,z,ans;split(root,v,x,y);ans = siz[y]?getval(y,1):INF;root = merge(x,y);return ans;
}// 线段树
#define lc (u<<1)
#define rc (u<<1|1)
int root[N];void build(int u,int l,int r){for(int i=l;i<=r;i++) insert(root[u],w[i]);if(l==r) return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
int queryrank(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getrank(root[u],v)-1;int mid=l+r>>1,res=0;if(x<=mid) res += queryrank(lc,l,mid,x,y,v);if(y>mid) res += queryrank(rc,mid+1,r,x,y,v);return res;
}
int queryval(int u,int x,int y,int v){int l=0,r=1e8,ans; //二分while(l<=r){int mid=l+r>>1;if(queryrank(1,1,n,x,y,mid)+1<=v) ans=mid, l=mid+1;else r=mid-1;}return ans;
}
void change(int u,int l,int r,int p,int v){del(root[u],w[p]);insert(root[u],v);if(l==r) return;int mid=l+r>>1;if(p<=mid) change(lc,l,mid,p,v);else change(rc,mid+1,r,p,v);
}
int querypre(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getpre(root[u],v);int mid=l+r>>1,res=-INF;if(x<=mid) res=max(res,querypre(lc,l,mid,x,y,v));if(y>mid) res=max(res,querypre(rc,mid+1,r,x,y,v));return res;
}
int querynxt(int u,int l,int r,int x,int y,int v){if(x<=l && r<=y) return getnxt(root[u],v);int mid=l+r>>1,res=INF;if(x<=mid) res=min(res,querynxt(lc,l,mid,x,y,v));if(y>mid) res=min(res,querynxt(rc,mid+1,r,x,y,v));return res;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);while(m -- ){int op,x,y,v;scanf("%d",&op);if(op==3)scanf("%d%d",&x,&v);else scanf("%d%d%d",&x,&y,&v);if(op==1)printf("%d\n",queryrank(1,1,n,x,y,v)+1);if(op==2) printf("%d\n",queryval(1,x,y,v));if(op==3)change(1,1,n,x,v), w[x]=v;if(op==4)printf("%d\n",querypre(1,1,n,x,y,v));if(op==5)printf("%d\n",querynxt(1,1,n,x,y,v));}return 0;
}