#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e17+100))
ll wl,wr,wx,wi;
struct nodes{
nodes *L,*R;
ll x;
nodes(){
L=R=NULL;
x=0;
}
void updt(){
x=0;
if(L)x+=L->x;
if(R)x+=R->x;
}
};
void updt(ll l,ll r,nodes *& x){
if(wi<l||r-1<wi)return;
if(!x)x=new nodes();
if(l==r-1){
x->x+=wx;
return;
}
updt(l,l+r>>1,x->L);
updt(l+r>>1,r,x->R);
x->updt();
}
ll quer(ll l,ll r,nodes *& x){
if(wr<l||r-1<wl)return 0;
if(!x)return 0;
if(wl<=l&&r-1<=wr)return x->x;
return quer(l,l+r>>1,x->L)
+quer(l+r>>1,r,x->R);
}
struct node{
node *L,*R;
ll x,s;
node(){
L=R=NULL;
s=0;
x=-MAX;
}
void updt(){
x=-MAX;
if(L)x=max(x,L->x);
if(R)x=max(x,R->x);
}
void shep(ll y){
s+=y;
x+=y;
}
void shplit(){
if(!L)L=new node();
if(!R)R=new node();
L->shep(s);
R->shep(s);
s=0;
}
};
void updt(ll l,ll r,node *& x){
if(wr<l||r-1<wl)return;
if(!x)x=new node();
if(wl<=l&&r-1<=wr){
x->shep(wx);
return;
}
x->shplit();
updt(l,l+r>>1,x->L);
updt(l+r>>1,r,x->R);
x->updt();
}
void updt1(ll l,ll r,node *& x){
if(wr<l||r-1<wl)return;
if(!x)x=new node();
if(wl<=l&&r-1<=wr){
x->x=wx;
x->s=0;
return;
}
x->shplit();
updt1(l,l+r>>1,x->L);
updt1(l+r>>1,r,x->R);
x->updt();
}
map<ll, set<ll> > mp;
node *rt=NULL;
nodes *rts=NULL;
void up(ll x){
if(mp[x].size()){
wl=x+1; wr=MAX;
wx=-(*mp[x].begin())+quer(-MAX,MAX,rts);
wl=wr=x;
// cout<<wl<<" "<<wx<<" "<<x<<" "<<(-*mp[x].begin())<<endl;
updt1(-MAX,MAX,rt);
}
else {
wl=wr=x;
wx=-MAX;
updt1(-MAX,MAX,rt);
}
}
ll a[ARRS],n;
void quer(ll i,ll x){
mp[a[i]].erase(n-i-1);
mp[x].insert(n-i-1);
wi=a[i];
wx=-1;
updt(-MAX,MAX,rts);
wi=x;
wx=1;
updt(-MAX,MAX,rts);
up(x);
up(a[i]);
if(a[i]<=x){
wl=a[i]+1;
wr=x-1;
wx=1;
}
else {
wl=x+1;
wr=a[i]-1;
wx=-1;
}
updt(-MAX,MAX,rt);
a[i]=x;
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
n=A.size();
ll q=X.size();
vector<ll> PAS;
for(int i=0; i<n; i++){
a[i]=A[i];
wi=a[i];
wx=1;
updt(-MAX,MAX,rts);
}
for(int i=0; i<n; i++){
mp[a[i]].insert(n-i-1);
up(a[i]);
}
//cout<<" ----> "<<rt->x<<endl;
for(int i=0; i<q; i++){
ll k=X[i];
ll p=V[i];
quer(k,p);
PAS.pb(rt->x);
}
return PAS;
}
Compilation message
bubblesort2.cpp: In function 'void updt(long long int, long long int, nodes*&)':
bubblesort2.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt(l,l+r>>1,x->L);
~^~
bubblesort2.cpp:36:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt(l+r>>1,r,x->R);
~^~
bubblesort2.cpp: In function 'long long int quer(long long int, long long int, nodes*&)':
bubblesort2.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
return quer(l,l+r>>1,x->L)
~^~
bubblesort2.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
+quer(l+r>>1,r,x->R);
~^~
bubblesort2.cpp: In function 'void updt(long long int, long long int, node*&)':
bubblesort2.cpp:82:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt(l,l+r>>1,x->L);
~^~
bubblesort2.cpp:83:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt(l+r>>1,r,x->R);
~^~
bubblesort2.cpp: In function 'void updt1(long long int, long long int, node*&)':
bubblesort2.cpp:96:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt1(l,l+r>>1,x->L);
~^~
bubblesort2.cpp:97:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
updt1(l+r>>1,r,x->R);
~^~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:178:9: error: could not convert 'PAS' from 'std::vector<long long int>' to 'std::vector<int>'
return PAS;
^~~
