本地正常运行但是洛谷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;
}