/*input
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 1099;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
int n;map<int, int> conv;
multiset<int> positions[N];
class tree
{
int tree[4*N], lazy[4*N], ql, qr, val;
void prop(int i, int l, int r)
{
tree[i]+=lazy[i];
if(l!=r)
{
lazy[2*i]+=lazy[i];lazy[2*i+1]+=lazy[i];
}
lazy[i]=0;
}
void update(int i=1, int l=1, int r=N-1)
{
prop(i, l, r);
if(l>qr||r<ql) return;
if(l>=ql&&r<=qr)
{
lazy[i]+=val;prop(i, l, r);
return;
}
int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);tree[i]=max(tree[2*i], tree[2*i+1]);
}
int query(int i=1, int l=1, int r=N-1)
{
prop(i, l, r);
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr)
{
return tree[i];
}
int mid=(l+r)>>1;
int v1=query(2*i, l, mid), v2=query(2*i+1, mid+1, r);
tree[i]=max(tree[2*i], tree[2*i+1]);return max(v1, v2);
}
public:
void remove(int ind, int el)
{
int prevmax=(*positions[el].rbegin());
positions[el].erase(ind);
if(!positions[el].empty()) prevmax=(*positions[el].rbegin()) - prevmax;
else prevmax*=-1;
ql=qr=el;val=prevmax;
if(val!=0) update();
ql=el+1;qr=N-1;val=+1;update();
}
void add(int ind, int el)
{
int prevmax=0;
if(!positions[el].empty()) prevmax=(*positions[el].rbegin());
positions[el].insert(ind);
prevmax=(*positions[el].rbegin() - prevmax);
ql=qr=el;val=prevmax;
if(val!=0) update();
ql=el+1;qr=N-1;val=-1;update();
}
int qry()
{
ql=1;qr=N-1;return query();
}
};
tree Segtree;
vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> nval)
{
n=arr.size();int q=pos.size();vector<int> ans;
conv.clear();
for(auto i:arr) conv[i]=0;
for(auto i:nval) conv[i]=0;
int curv=1;
for(auto &i:conv) i.s=curv++;
for(int i=0;i<n;i++) {arr[i]=conv[arr[i]];Segtree.add(i, arr[i]);}
for(auto &i:nval) i=conv[i];
// cout<<Segtree.qry()<<endl;
for(int i=0;i<q;i++)
{
Segtree.remove(pos[i], arr[pos[i]]);
Segtree.add(pos[i], nval[i]);arr[pos[i]]=nval[i];
ans.push_back(Segtree.qry());
}
return ans;
}
Compilation message
/tmp/ccj9iHt6.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
