RT

记录

评测说第95行第4个字符为9，而标准答案为7078，但是下载数据本地评测后第95行输出为7078

附代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lc k<<1
#define rc k<<1|1
#define mid ((l+r)>>1)
const int M=1e5+10,INF=0x7fffffff;
int n,m;
int val[M];
struct Treap{
	int l,r,pri,size,val,cnt;
}treap[M*20];
int cnt=0;
int new_node(int val){
	cnt++;
	treap[cnt]=Treap{0,0,rand(),1,val,1};
	return cnt;
}
void update(int k){
	treap[k].size=treap[treap[k].l].size+treap[treap[k].r].size+treap[k].cnt;
}
void zig(int &k){
	int zc=treap[k].l;
	treap[k].l=treap[zc].r;
	treap[zc].r=k;
	update(k);
	update(zc);
	k=zc;
}
void zag(int &k){
	int zc=treap[k].r;
	treap[k].r=treap[zc].l;
	treap[zc].l=k;
	update(k);
	update(zc);
	k=zc;
}
void Insert(int &k,int val){
	if(!k){
		k=new_node(val);
		return;
	}
	treap[k].size++;
	if(val==treap[k].val){
		treap[k].cnt++;
		return;
	}
	if(val<treap[k].val){
		Insert(treap[k].l,val);
		if(treap[treap[k].l].pri>treap[k].pri)zig(k);
	}else{
		Insert(treap[k].r,val);
		if(treap[treap[k].r].pri>treap[k].pri)zag(k);
	}
}
void Delete(int &k,int val){
	if(!k)return;
	treap[k].size--;
	if(treap[k].val==val){
		if(treap[k].cnt>=2)treap[k].cnt--;
		else{
			if(!treap[k].l||!treap[k].r)k=treap[k].l+treap[k].r;
			else{
				if(treap[treap[k].l].pri>treap[treap[k].r].pri){
					zig(k);
					Delete(treap[k].r,val);
				}else{
					zag(k);
					Delete(treap[k].l,val);
				}
			}
		}
		return;
	}
	if(val<treap[k].val)Delete(treap[k].l,val);
	else Delete(treap[k].r,val);
}
int query_pre(int k,int val){
	int res=-INF;
	while(k){
		if(treap[k].val<val)res=treap[k].val,k=treap[k].r;
		else k=treap[k].l;
	}
	return res;
}
int query_nex(int k,int val){
	int res=INF;
	while(k){
		if(treap[k].val>val)res=treap[k].val,k=treap[k].l;
		else k=treap[k].r;
	}
	return res;
}
int query_rk(int k,int val){
	if(!k)return 0;
	if(val<treap[k].val)return query_rk(treap[k].l,val);
	else if(val>treap[k].val)return treap[treap[k].l].size+treap[k].cnt+query_rk(treap[k].r,val);
	else return treap[treap[k].l].size;
}
int seg[M<<2];
void build(int k,int l,int r){
	for(int i=l;i<=r;i++)Insert(seg[k],val[i]);
	if(l==r)return;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void modify(int k,int l,int r,int pos,int x){
	Delete(seg[k],val[pos]);
	Insert(seg[k],x);
	if(l==r)return;
	if(pos<=mid)modify(lc,l,mid,pos,x);
	else modify(rc,mid+1,r,pos,x);
}
int pre(int k,int l,int r,int x,int y,int val){
	if(l>=x&&r<=y)return query_pre(seg[k],val);
	if(y<=mid)return pre(lc,l,mid,x,y,val);
	else if(x>mid)return pre(rc,mid+1,r,x,y,val);
	else return max(pre(lc,l,mid,x,y,val),pre(rc,mid+1,r,x,y,val));
}
int nex(int k,int l,int r,int x,int y,int val){
	if(l>=x&&r<=y)return query_nex(seg[k],val);
	if(y<=mid)return nex(lc,l,mid,x,y,val);
	else if(x>mid)return nex(rc,mid+1,r,x,y,val);
	else return min(nex(lc,l,mid,x,y,val),nex(rc,mid+1,r,x,y,val));
}
int rk(int k,int l,int r,int x,int y,int val){
	if(l>=x&&r<=y)return query_rk(seg[k],val);
	if(y<=mid)return rk(lc,l,mid,x,y,val);
	else if(x>mid)return rk(rc,mid+1,r,x,y,val);
	else return rk(lc,l,mid,x,y,val)+rk(rc,mid+1,r,x,y,val);
}
int num(int k,int x,int y,int rank){
	int l=0,r=1e8;
	while(l<r){
		int dmid=(l+r+1)>>1;
		if(rk(1,1,n,x,y,dmid)<rank)l=dmid;
		else r=dmid-1;
	}
	return r;
}
signed main(){
	int tot=0;
	//	freopen("in.txt","r",stdin);
	//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>val[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,k;
			cin>>l>>r>>k;
		//	cout<<opt<<endl;
			//	cout<<++tot<<' ';
			cout<<rk(1,1,n,l,r,k)+1<<endl;
		}
		if(opt==2){
			int l,r,k;
			cin>>l>>r>>k;
		//	cout<<opt<<endl;
			//	cout<<++tot<<' ';
			cout<<num(1,l,r,k)<<endl;
		}
		if(opt==3){
			int pos,k;
			cin>>pos>>k;
			modify(1,1,n,pos,k);
			val[pos]=k;
		}
		if(opt==4){
			int l,r,k;
			cin>>l>>r>>k;
		//	cout<<opt<<endl;
			//	cout<<++tot<<' ';
			cout<<pre(1,1,n,l,r,k)<<endl;
		}
		if(opt==5){
			int l,r,k;
			cin>>l>>r>>k;
		//	cout<<opt<<endl;
			//	cout<<++tot<<' ';
			cout<<nex(1,1,n,l,r,k)<<endl;
		}
	}
	return 0;
}