神秘RE求调
  • 板块学术版
  • 楼主qyy_abc
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/1/25 17:13
  • 上次更新2024/1/25 19:44:11
查看原帖
神秘RE求调
537547
qyy_abc楼主2024/1/25 17:13

本地正常运行但是洛谷IDE在注释处RE,求大佬看看/kel

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define test puts("test")
const int N=4e5+15;
const int maxn=4e5;
int a[200003],d[N<<2],b[N<<2];
int cnt[N];
void build(int s,int t,int p){
	if(s==t){
		d[p]=cnt[s];
		return;
	}
	int m=s+((t-s)>>1);
	build(s,m,p*2);
	build(m+1,t,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
	return;
}

void update(int l,int r,int s,int t,int c,int p){
	if(l<=s&&t<=r){
		d[p]+=(t-s+1)*c;
		b[p]+=c;
		return;
	}
	int m=s+((t-s)>>1);
	if(b[p]&&s<t){
		d[p*2]+=(m-s+1)*b[p];
		d[p*2+1]+=(t-m)*b[p];
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		b[p]=0;
	}
	if(m>=l)
		update(l,r,s,m,c,p*2);
	if(m<r)
		update(l,r,m+1,t,c,p*2+1);
	d[p]=d[p*2]+d[p*2+1];
	return;
}

int getsum(int l,int r,int s,int t,int p){
	if(l<=s&&t<=r)
		return d[p];
	int m=s+((t-s)>>1);
	if(b[p]&&s<t){
		d[p*2]+=(m-s+1)*b[p];
		d[p*2+1]+=(t-m)*b[p];
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		b[p]=0;
	}
	int sum=0;
	if(l<=m)
		sum+=getsum(l,r,s,m,p*2);
	if(m<r)
		sum+=getsum(l,r,m+1,t,p*2+1);
	return sum;
}
int fd0(int k){
	int l=k,r=maxn;
	int mid;
	while(l<r){
		mid=l+r>>1;
		if(getsum(k,mid,1,maxn,1)==(mid-k+1)) l=mid+1;
		else r=mid;
	}
}
int fd1(int k){
	int l=k,r=maxn;
	int mid;
	while(l<r){
		mid=l+r>>1;
		if(getsum(k,mid,1,maxn,1)) r=mid;
		else l=mid+1;	
	}
	return l;
}
void del(int k){
	int x=fd1(k);
	update(x,x,1,maxn,-1,1);
	if(k<x)update(k,x-1,1,maxn,1,1);
}
void add(int k){
	int x=fd0(k);
	update(x,x,1,maxn,1,1);
	if(k<x) update(k,x-1,1,maxn,-1,1);
}
int qry(int l,int r,int s,int t,int p){
	if(s==t) return s;
	int m=s+((t-s)>>1);
	if(b[p]&&s<t){
		d[p*2]+=(m-s+1)*b[p];
		d[p*2+1]+=(t-m)*b[p];
		b[p*2]+=b[p];
		b[p*2+1]+=b[p];
		b[p]=0;
	}
	if(d[p*2+1]>0) return qry(l,r,m+1,t,(p*2+1));
	else return qry(l,r,s,m,(p*2));
}
signed main(){
	
	int n,q;
    int kkk,k;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cnt[a[i]]++;
	} 
	for(int i=1;i<=maxn;i++){
		cnt[i]+=cnt[i-1]/2;
		cnt[i-1]%=2;
	}
	build(1,maxn,1);
	while(q--){
		cin>>k;
      test;
        cin>>kkk;
      test; // qwqqwqqwqqwq这里无法输出
		int del_x=a[k];
		a[k]=kkk;
		del(del_x);
		add(kkk);
		cout<<qry(1,maxn,1,maxn,1)<<'\n';
	}
	return 0;
}
2024/1/25 17:13
加载中...