打的树状数组套权值线段树;没离散化,空间瞎开还A了233。
其实loj还是很好用的哦
#include <iostream> #include <cstdio> #include <vector> using namespace std;const int N=1e6+7,INF=1e8+3,inf=0x7fffffff; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; }vector<int> v1,v2;int n,m,tot,lc[N<<5],rc[N<<5],T[N],siz[N<<5],a[N]; inline int lowbit(int x){return x&(-x);} inline void update(int &k,int l,int r,int w,int t) { if(!k) k=++tot;int mid=(l+r)>>1; siz[k]+=t;if(l==r) return; if(w<=mid) update(lc[k],l,mid,w,t); else update(rc[k],mid+1,r,w,t); } inline void add(int x,int y,int t) { for(int i=x;i<=n;i+=lowbit(i)) update(T[i],-INF,INF,y,t); } inline int trank(int k,int l,int r,int w) { if(!k||l==r) return 0;int mid=(l+r)>>1; if(w<=mid) return trank(lc[k],l,mid,w); else return siz[lc[k]]+trank(rc[k],mid+1,r,w); } inline int Q_trank(int l,int r,int k) { int res=0; while(r) res+=trank(T[r],-INF,INF,k),r-=lowbit(r); while(l) res-=trank(T[l],-INF,INF,k),l-=lowbit(l); return res; } inline int kth(int l,int r,int K) { int sum=0,mid=(l+r)>>1; if(l==r) return l; for(int i=0;i<v1.size();i++) sum+=siz[lc[v1[i]]]; for(int i=0;i<v2.size();i++) sum-=siz[lc[v2[i]]]; if(sum>=K) { for(int i=0;i<v1.size();i++) v1[i]=lc[v1[i]]; for(int i=0;i<v2.size();i++) v2[i]=lc[v2[i]]; return kth(l,mid,K); } else { for(int i=0;i<v1.size();i++) v1[i]=rc[v1[i]]; for(int i=0;i<v2.size();i++) v2[i]=rc[v2[i]]; return kth(mid+1,r,K-sum); } } inline int Q_kth(int l,int r,int k) { v1.clear();v2.clear(); while(r) v1.push_back(T[r]),r-=lowbit(r); while(l) v2.push_back(T[l]),l-=lowbit(l); return kth(-INF,INF,k); } int main() { n=read(),m=read();for(int i=1;i<=n;i++) add(i,a[i]=read(),1); while(m--) { int opt=read(),l=read(),r=read(),k;if(opt!=3) k=read(); if(opt==1) printf("%d\n",Q_trank(l-1,r,k)+1); if(opt==2) printf("%d\n",Q_kth(l-1,r,k)); if(opt==3) add(l,a[l],-1),add(l,a[l]=r,1); if(opt==4) { int rk=Q_trank(l-1,r,k); if(!rk) printf("%d\n",-inf); else printf("%d\n",Q_kth(l-1,r,rk)); } if(opt==5) { int rk=Q_trank(l-1,r,k+1); if(rk>r-l) printf("%d\n",inf); else printf("%d\n",Q_kth(l-1,r,rk+1)); } } return 0; }