#include <bits/stdc++.h>
#include "bubblesort2.h"
#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define ll long long
#define int long long
#define F first
#define S second
using namespace std;
const int N=50006;
long long inf=-100000000000000000LL;
int n,q,S;
int a[N],pos[N],x[N];
int G[2*N];
vector < int > answer;
vector < pair < pair < int , int > , bool > > s;
typedef struct { ll x; int add; } res;
res v[4*N];
void Shift(Tree) {
if (!v[h].add) return ;
v[h].x+=v[h].add;
if (l!=r) {
v[(h<<1)].add+=v[h].add;
v[((h<<1)|1)].add+=v[h].add;
}
v[h].add=0;
}
int L,R,dl;
void Updlr(Tree) {
Shift(h,l,r);
if (R<l || r<L) return ;
if (L<=l && r<=R) {
v[h].add+=dl;
Shift(h,l,r);
return ;
}
Updlr(Left),Updlr(Right);
v[h].x=max(v[(h<<1)].x,v[((h<<1)|1)].x);
}
int idx;
ll val;
void Upd(Tree) {
Shift(h,l,r);
if (r<idx || idx<l) return ;
if (l==idx && r==idx) { v[h].x=val; return ; }
Upd(Left),Upd(Right);
v[h].x=max(v[(h<<1)].x,v[((h<<1)|1)].x);
}
void Up(int x,int dl) {
while (x<=S) {
G[x]+=dl;
x+=(x & -x);
}
}
int Ge(int x) {
int res=0;
while (x>0) {
res+=G[x];
x-=(x & -x);
}
return res;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
n=A.size(),q=X.size();
for (int i=1; i<=n; i++) {
a[i]=A[i-1];
s.push_back({{a[i],n-i},0});
}
for (int i=1; i<=q; i++) {
pos[i]=X[i-1]+1,x[i]=V[i-1];
s.push_back({{x[i],n-pos[i]},1});
}
sort(s.begin(),s.end());
S=s.size();
for (int i=0; i<s.size(); i++)
if (!s[i].S)
a[-(s[i].F.S-n)]=i+1;
else
x[-(s[i].F.S-n)]=i+1;
for (int i=1; i<=n; i++) Up(a[i],1);
for (int i=1; i<=4*S; i++) v[i].x=inf;
for (int i=1; i<=n; i++)
idx=a[i],val=i-Ge(a[i]),Upd(1,1,S);
int Xx,Yy;
for (int i=1; i<=q; i++) {
Xx=a[pos[i]],Yy=x[i];
Up(a[pos[i]],-1),Up(x[i],1);
if (Xx<=Yy) {
idx=Xx,val=inf,Upd(1,1,S);
L=Xx+1,R=Yy-1,dl=1,Updlr(1,1,S);
idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
}
else {
idx=Xx,val=inf,Upd(1,1,S);
L=Yy+1,R=Xx-1,dl=-1,Updlr(1,1,S);
idx=Yy,val=pos[i]-Ge(x[i]),Upd(1,1,S);
}
a[pos[i]]=x[i];
answer.push_back(v[1].x);
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<long long int> countScans(std::vector<long long int>, std::vector<long long int>, std::vector<long long int>)':
bubblesort2.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<s.size(); i++)
~^~~~~~~~~
/tmp/ccwJcvrf.o: In function `main':
grader.cpp:(.text.startup+0x12b): undefined reference to `countScans(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
