人傻自带大常数
二分的可行性证明：
贴近他的正确答案不会被当作次优解删掉,因为,若二分在他右边发生,那么二分一定会把左边作为优解,左边同理,所以他一定是被扣掉的所以最后一个小于等于一定是正确答案
#include<cstdio> #include<cstring> #include<iostream> #define MAXN 1500005 using namespace std; const double A=0.756; const int inf=100000000; int n,m,a[50005]; struct ScapeGoat_Tree {ScapeGoat_Tree *ch[2];int ex,cover,size,key;bool bad(){return cover*A<ch[0]->cover||cover*A<ch[1]->cover;}void pushup(){size=ch[0]->size+ch[1]->size+ex;cover=ch[0]->cover+ch[1]->cover+1;} }*null,pool[MAXN],*stack[MAXN],*lst[MAXN]; int top,len; inline void Init() {null=pool;null->cover=null->size=null->ex=null->key=0;null->ch[1]=null->ch[0]=null;for(int i=1;i<MAXN;i++)stack[++top]=pool+i; } inline ScapeGoat_Tree *New(int key) {ScapeGoat_Tree *p=stack[top--];p->ch[1]=p->ch[0]=null;p->ex=p->cover=p->size=1;p->key=key;return p; } struct Tree {Tree *ch[2];int l,r,mid;ScapeGoat_Tree *root;Tree(){ch[1]=ch[0]=NULL;root=null;}void* operator new(size_t size); }*root,*C,*mempool; void* Tree :: operator new(size_t size) {if(C==mempool){C=new Tree[(1<<15)+10];mempool=C+(1<<15)+10;}return C++; } void travel(ScapeGoat_Tree *p) {if(p==null)return;travel(p->ch[0]);if(p->ex) lst[++len]=p;else stack[++top]=p;travel(p->ch[1]); } ScapeGoat_Tree *divide(int l,int r) {if(l>r)return null;int mid=(l+r)>>1;lst[mid]->ch[0]=divide(l,mid-1);lst[mid]->ch[1]=divide(mid+1,r);lst[mid]->pushup();return lst[mid]; } ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key) {if(p==null){p=New(key);return &null;}p->size++;p->cover++;ScapeGoat_Tree **ret=insert(p->ch[p->key<=key],key);if(p->bad())ret=&p;return ret; } inline void rebuild(ScapeGoat_Tree *&p) {len=0;travel(p);p=divide(1,len); } inline void Insert(ScapeGoat_Tree *&Root,int key) {ScapeGoat_Tree **p=insert(Root,key);if(*p!=null)rebuild(*p); } inline int rank(ScapeGoat_Tree *p,int key) {int ret=0;while(p!=null)if(p->key>=key)p=p->ch[0];elseret+=p->ch[0]->size+p->ex,p=p->ch[1];return ret; } void erase(ScapeGoat_Tree *p,int k) {p->size--;if(p->ex&&k==p->ch[0]->size+1){p->ex=0;return;}if(p->ch[0]->size>=k)erase(p->ch[0],k);else erase(p->ch[1],k-p->ch[0]->size-p->ex); } inline void Erase_kth(ScapeGoat_Tree *&p,int k) {erase(p,k);if(p->size<p->cover*A)rebuild(p); } inline void Erase(ScapeGoat_Tree *&p,int key) {Erase_kth(p,rank(p,key)+1); } void build(Tree *p) {p->mid=(p->l+p->r)>>1;if(p->l==p->r)return;p->ch[0]=new Tree;p->ch[0]->l=p->l;p->ch[0]->r=p->mid;p->ch[1]=new Tree;p->ch[1]->l=p->mid+1;p->ch[1]->r=p->r;build(p->ch[0]);build(p->ch[1]); } void get_in(int key,int aim,Tree *p) {Insert(p->root,key);if(p->l==p->r)return;if(aim<=p->mid)get_in(key,aim,p->ch[0]);else get_in(key,aim,p->ch[1]); } void get_rank(int l,int r,int key,Tree *p,int &ans) {if(l<=p->l&&p->r<=r){ans+=rank(p->root,key);return;}if(l<=p->mid)get_rank(l,r,key,p->ch[0],ans);if(p->mid<r)get_rank(l,r,key,p->ch[1],ans); } inline int Rank(int l,int r,int key) {int ans=0;get_rank(l,r,key,root,ans);return ans+1; } inline int Kth(int l,int r,int rk) {int z=0,y=inf,mid;int ans=0;while(z<=y){mid=(z+y)>>1;int k=Rank(l,r,mid);if(k<=rk)ans=mid,z=mid+1;elsey=mid-1;}return ans; } void get_out(int aim,int key,Tree *p) {Erase(p->root,key);if(p->l==p->r)return;if(aim<=p->mid)get_out(aim,key,p->ch[0]);else get_out(aim,key,p->ch[1]); } inline void work1() {int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",Rank(l,r,k)); } inline void work2() {int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",Kth(l,r,k)); } inline void work3() {int aim,key;scanf("%d%d",&aim,&key);get_out(aim,a[aim],root);a[aim]=key;get_in(key,aim,root); } inline void work4() {int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",Kth(l,r,Rank(l,r,k)-1)); } inline void work5() {int l,r,k;scanf("%d%d%d",&l,&r,&k);printf("%d\n",Kth(l,r,Rank(l,r,k+1))); } void dfs(Tree *p) {if(p->l==p->r)return;dfs(p->ch[0]);dfs(p->ch[1]); } int main() {freopen("psh.in","r",stdin);freopen("psh.out","w",stdout);Init();root=new Tree;root->l=1;scanf("%d%d",&n,&m);root->r=n;build(root);dfs(root);for(int i=1;i<=n;i++){scanf("%d",&a[i]);get_in(a[i],i,root);}dfs(root);int opt;while(m--){scanf("%d",&opt);switch(opt){case 1:work1();break;case 2:work2();break;case 3:work3();break;case 4:work4();break;case 5:work5();break;}}return 0; }