#include "bubblesort2.h"
#include "bits/stdc++.h"
using namespace std;
Struct SegT{
int n;
vector<int> seg,lazy;
SegT(int _n){
n=_n;
seg.assign(4*n+5,0);
lazy.assign(4*n+5,0);
}
void push(int rt,int l,int r){
int u=lazy[rt];
lazy[rt]=0;
seg[rt]+=u;
if(l==r) return;
lazy[rt*2]+=u;
lazy[rt*2+1]+=u;
}
void update(int rt,int l,int r,int gl,int gr,int u){
if(l>r || gl>gr || gr>=n) return;
push(rt,l,r);
if(r<gl || l>gr) return;
if(l>=gl && r<=gr){
lazy[rt]+=u;
push(rt,l,r);
return;
}
int m=(l+r)/2;
update(rt*2,l,m,gl,gr,u),update(rt*2+1,m+1,r,gl,gr,u);
seg[rt]=max(seg[rt*2],seg[rt*2+1]);
}
void update(int l,int r,int u){
update(1,0,n-1,l,r,u);
}
};
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int q=X.size(),n=A.size();
vector<int> answer(q);
vector<array<int,2>> zip;
for(int i=0;i<n;i++) zip.push_back({A[i],i});
for(int i=0;i<q;i++) zip.push_back({V[i],X[i]});
sort(zip.begin(),zip.end());
zip.erase(unique(zip.begin(),zip.end()),zip.end());
for(int i=0;i<n;i++) A[i]=lower_bound(zip.begin(),zip.end(),
array<int,2>{A[i],i})-zip.begin();
for(int i=0;i<q;i++) V[i]=lower_bound(zip.begin(),zip.end(),
array<int,2>{V[i],X[i]})-zip.begin();
SegT T(n+q+5);
for(int i=0;i<n;i++){
T.update(A[i],A[i],i);
T.update(A[i]+1,n+q,-1);
}
for(int i=0;i<q;i++){
T.update(A[X[i]],A[X[i]],-X[i]);
T.update(A[X[i]]+1,n+q,1);
A[X[i]]=Y[i];
T.update(A[X[i]],A[X[i]],X[i]);
T.update(A[X[i]]+1,n+q,-1);
answer[i]=T.seg[1];
}
return answer;
}
Compilation message
bubblesort2.cpp:6:1: error: 'Struct' does not name a type; did you mean 'struct'?
6 | Struct SegT{
| ^~~~~~
| struct
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:54:5: error: 'SegT' was not declared in this scope
54 | SegT T(n+q+5);
| ^~~~
bubblesort2.cpp:57:7: error: 'T' was not declared in this scope
57 | T.update(A[i],A[i],i);
| ^
bubblesort2.cpp:62:7: error: 'T' was not declared in this scope
62 | T.update(A[X[i]],A[X[i]],-X[i]);
| ^
bubblesort2.cpp:64:15: error: 'Y' was not declared in this scope
64 | A[X[i]]=Y[i];
| ^
