视频链接：
// 需要开O2
#include <iostream> #include <algorithm> using namespace std; #define N 2000010 #define INF 2147483647 #define ls(x) tr[x].s[0] #define rs(x) tr[x].s[1] #define lc u<<1 #define rc u<<1|1 struct node{ int s[2],p,v; int size; void init(int v1,int p1){ v=v1,p=p1; size=1; } }tr[N];//splay int L[N],R[N],T[N];//线段树 int n,m,w[N],idx; //////////splay void pushup(int x){ tr[x].size=tr[ls(x)].size+tr[rs(x)].size+1; } 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); } 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; } 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; if(p) tr[p].s[v>tr[p].v]=u; tr[u].init(v,p); splay(root,u,0); } int get_k(int root,int v){ int u=root,res=0; while(u){ if(tr[u].v<v) res+=tr[ls(u)].size+1,u=rs(u); else u=ls(u); } return res; } void update(int &root,int x,int y){ int u=root; while(u){ if(tr[u].v==x) break; if(tr[u].v<x) 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; pushup(r),pushup(l); insert(root,y); } int get_pre(int root,int v){ int u=root,res=-INF; while(u){ if(tr[u].v<v) res=max(res,tr[u].v),u=rs(u); else u=ls(u); } return res; } int get_nxt(int root,int v){ int u=root,res=INF; while(u){ if(tr[u].v>v) res=min(res,tr[u].v),u=ls(u); else u=rs(u); } return res; } //////////线段树 void build(int u,int l,int r){ L[u]=l,R[u]=r; insert(T[u],-INF),insert(T[u],INF); for(int i=l; i<=r; i++) insert(T[u],w[i]); if(l==r) return; int mid=l+r>>1; build(lc,l,mid); build(rc,mid+1,r); } void change(int u,int p,int x){ update(T[u],w[p],x); if(L[u]==R[u]) return; int mid=L[u]+R[u]>>1; if(p<=mid) change(lc,p,x); else change(rc,p,x); } int query_rank(int u,int a,int b,int x){ if(L[u] >= a && R[u]<=b) return get_k(T[u],x)-1; int mid=L[u]+R[u]>>1,res=0; if(a<=mid) res += query_rank(lc,a,b,x); if(b>mid) res += query_rank(rc,a,b,x); return res; } int query_pre(int u,int a,int b,int x){ if(L[u] >= a && R[u]<=b) return get_pre(T[u],x); int mid=L[u]+R[u]>>1,res=-INF; if(a<=mid) res=max(res,query_pre(lc,a,b,x)); if(b>mid) res=max(res,query_pre(rc,a,b,x)); return res; } int query_nxt(int u,int a,int b,int x){ if(L[u] >= a && R[u]<=b) return get_nxt(T[u],x); int mid=L[u]+R[u]>>1,res=INF; if(a<=mid) res=min(res,query_nxt(lc,a,b,x)); if(b>mid) res=min(res,query_nxt(rc,a,b,x)); 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,a,b,x; scanf("%d",&op); if(op==1){ scanf("%d%d%d",&a,&b,&x); printf("%d\n",query_rank(1,a,b,x)+1); } else if(op==2){ //logn*logn*logn scanf("%d%d%d",&a,&b,&x); int l=0,r=1e8; while(l<r){ int mid=l+r+1>>1; if(query_rank(1,a,b,mid)+1<=x) l=mid; else r=mid-1; } printf("%d\n",r); } else if(op==3){ scanf("%d%d",&a,&x); change(1,a,x); w[a]=x; } else if(op==4){ scanf("%d%d%d",&a,&b,&x); printf("%d\n",query_pre(1,a,b,x)); } else{ scanf("%d%d%d",&a,&b,&x); printf("%d\n",query_nxt(1,a,b,x)); } } return 0; }
标签：树套,int,res,线段,tr,query,172,define From： https://www.cnblogs.com/dx123/p/16595024.html