bzoj 4923 [Lydsy1706月赛]K小值查询

bzoj 4923 [Lydsy1706月赛]K小值查询

​​ Description 维护一个长度为n的正整数序列a_1,a_2,…,a_n，支持以下两种操作： 1 k，将序列a从小到大排序，输出a_k的值。 2 k，将所有严格大于k的数a_i减去k。 Input 第一行包含两个正整数n,m(1<=n,m<=100000)，分别表示序列的长度和操作的个数。 第二行包含n个正整数a_1,a_2,…,a_n(1<=a_i<=10^9)，分别表示序列中的每个元素。 接下来m行，每行两个正整数op(1<=op<=2),k，若op=1，则1<=k<=n；若op=2，则1<=k<=10^9；依次描述每个操作。 Output 输出若干行，对于每个询问输出一行一个整数，即第k小的值。 Sample Input 4 5 1 5 6 12 2 5 1 1 1 2 1 3 1 4 Sample Output 1 1 5 7 HINT

Source 本OJ付费获取

分类讨论 1~k不变 k+1~2k暴力修改 2k+1以上打splay上标记

可以证明发现每次减半 这样复杂度是log^2的 全部操作仅由splay即可完成

#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=1e5+10;const int inf=0x3f3f3f3f;int tag[N],v[N],n,m,c[N][2],fa[N],size[N],pre,succ,q[N],top,rt;inline void update(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+1;}inline void build(int &x,int l,int r,int f){ int mid=l+r>>1;x=mid;fa[mid]=f;size[mid]=1; if(lmid) build(c[mid][1],mid+1,r,mid);update(x);}inline void pushdown(int x){ if (!tag[x]) return; int l=c[x][0],r=c[x][1]; if (l) tag[l]+=tag[x],v[l]+=tag[x]; if (r) tag[r]+=tag[x],v[r]+=tag[x];tag[x]=0;}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if(y==tar) tar=x;else c[z][c[z][1]==y]=x; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x,int &tar){ q[top=1]=x;for (int i=x;fa[i];i=fa[i]) q[++top]=fa[i]; while(top) pushdown(q[top--]); while(x!=tar){ int y=fa[x],z=fa[y]; if(y!=tar){ if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar); }rotate(x,tar); }}inline int findk(int x,int k){ if (size[c[x][0]]+1==k) {splay(x,rt);return v[x];} pushdown(x); if (k<=size[c[x][0]]) return findk(c[x][0],k); else return findk(c[x][1],k-size[c[x][0]]-1);}inline void pre1(int x,int vv){ if (!x) return;pushdown(x); if (v[x]vv) succ=x,succ1(c[x][0],vv); else succ1(c[x][1],vv);}inline void insert1(int &x,int id,int f){ if (!x) {x=id;fa[x]=f;size[x]=1;c[x][0]=c[x][1]=0;splay(x,rt);return;} pushdown(x); if (v[id]

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。