#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=1e6+5; //make sure this is right
const int mod=1e9+7;
struct node{
int lft,rt;
};
node st[4*mxN];
int a[mxN],lazy[4*mxN],cnt[mxN];
vector<int> all;
int get(int x){
int f=lower_bound(all.begin(),all.begin(),x)-all.begin()+1;
return f+(cnt[f]++);
}
void pushup(int v){
st[v].lft=max(st[v<<1].lft,st[v<<1|1].lft);
st[v].rt=max(st[v<<1].rt,st[v<<1|1].rt);
}
void prop(int v,int val){
if(val<0){
int tmp=st[v].rt;
st[v].rt=max(0,st[v].rt+val);
val=min(0,val+tmp);
st[v].lft+=abs(val);
} else{
int tmp=st[v].lft;
st[v].lft=max(0,st[v].lft-val);
val=max(0,val-tmp);
st[v].rt+=val;
}
}
void push(int v){
lazy[v<<1]+=lazy[v];
lazy[v<<1|1]+=lazy[v];
prop(v<<1,lazy[v]);
prop(v<<1|1,lazy[v]);
lazy[v]=0;
}
void point_upd(int v,int l,int r,int ind,int val){
if(ind<l || ind>r)
return;
if(l==r){
if(val<0){
st[v].rt=0;
st[v].lft=abs(val);
} else{
st[v].lft=0;
st[v].rt=val;
}
} else{
int m=(l+r)>>1;
push(v);
point_upd(v<<1,l,m,ind,val);
point_upd(v<<1|1,m+1,r,ind,val);
pushup(v);
}
}
void range_upd(int v,int l,int r,int lq,int rq,int val){
if(lq>rq)
return;
if(l>=lq && r<=rq){
prop(v,val);
lazy[v]+=val;
} else{
int m=(l+r)>>1;
push(v);
range_upd(v<<1,l,m,lq,min(m,rq),val);
range_upd(v<<1|1,m+1,r,max(lq,m+1),rq,val);
pushup(v);
}
}
struct BIT{
ll bit[mxN];
void upd(int x,int v){while(x<mxN){bit[x]+=v;x+=x&-x;}}
ll sum(int x){ll res=0;while(x){res+=bit[x];x-=x&-x;}return res;}
};
BIT bit;
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int n=sz(A); int q=sz(X);
for(int &i:A)
all.pb(i);
for(int &i:V)
all.pb(i);
sort(all.begin(),all.end());
all.resize(unique(all.begin(),all.end())-all.begin());
vector<int> ans;
for(int i=0;i<n;i++){
A[i]=get(A[i]);
bit.upd(A[i],1);
}
for(int i=0;i<n;i++){
int s=bit.sum(A[i]);
int move=s-i-1;
point_upd(1,1,n,A[i],move);
}
for(int i=0;i<q;i++){
V[i]=get(V[i]);
bit.upd(A[X[i]],-1);
point_upd(1,1,n,A[X[i]],0);
int f=A[X[i]]; int s=V[i];
bit.upd(s,1); int su=bit.sum(s);
int move=su-X[i]-1;
point_upd(1,1,n,s,move);
if(f<s){
range_upd(1,1,n,f+1,s-1,-1);
} else{
range_upd(1,1,n,s+1,f-1,1);
}
ans.pb(max(st[1].lft,st[1].rt));
A[X[i]]=s;
}
return ans;
}
int main(){
cin.sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int n,q; cin>>n>>q;
vector<int> a(n),x(q),v(q);
for(int &i:a)
cin>>i;
for(int i=0;i<q;i++)
cin>>x[i]>>v[i];
vector<int> res=countScans(a,x,v);
for(int &i:res)
cout<<i<<" ";
}
Compilation message
/usr/bin/ld: /tmp/cc0YtblY.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccqYX75Y.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
