#include "bubblesort2.h"
#include <cstdio>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
struct node
{
node *left;
node *right;
int h;
int v;
int idx;
int v1;
int sz;
int pv;
int mv;
};
string tostr(node *a)
{
if (!a)
return string();
string r = tostr(a->left);
char tmp[20];
sprintf(tmp," (%d, %d, %d, %d, %d)", a->v, a->v1, a->mv, a->pv, a->idx);
r += tmp;
return r + tostr(a->right);
}
vector<int> grab(node *a, int pv)
{
if (!a)
return vector<int>();
vector<int> r = grab(a->left, pv+a->pv);
r.push_back(pv+a->v1);
vector<int> rb = grab(a->right, pv+a->pv);
for (int i = 0; i < rb.size(); ++i)
r.push_back(rb[i]);
return r;
}
void push(node *a)
{
int pv = a->pv;
if (pv)
{
a->pv = 0;
if (a->left)
{
a->left->pv += pv;
a->left->v1 += pv;
a->left->mv += pv;
}
if (a->right)
{
a->right->pv += pv;
a->right->v1 += pv;
a->right->mv += pv;
}
}
}
node * merge(node *a, node *b)
{
if (!a)
return b;
if (!b)
return a;
push(a);
push(b);
//vector<int> qwe = grab(a,0);
//vector<int> qwe1 = grab(b,0);
//for (int i = 0; i < qwe1.size(); ++i)
// qwe.push_back(qwe1[i]);
node *r;
if (a->h < b->h)
{
a->right = merge(a->right, b);
r = a;
}
else
{
b->left = merge(a, b->left);
r = b;
}
r->sz = 1;
r->mv = r->v1;
if (r->left)
{
r->sz += r->left->sz;
r->mv = max(r->mv, r->left->mv);
}
if (r->right)
{
r->sz += r->right->sz;
r->mv = max(r->mv, r->right->mv);
}
/*vector<int> qwe2 = grab(r,0);
int mmm = int(-1e9);
for (int i = 0; i < qwe.size(); ++i)
mmm = max(mmm, qwe[i]);
if (qwe != qwe2 || r->mv != mmm)
{
printf("======= wrong ==== %d %d\n", r->mv, mmm);
for (int i = 0; i < qwe.size(); ++i)
printf("%d ", qwe[i]);
printf("\n");
for (int i = 0; i < qwe2.size(); ++i)
printf("%d ", qwe2[i]);
printf("\n [%s] [%s]\n", tostr(a).c_str(), tostr(b).c_str());
}*/
return r;
}
pair<node*,node*> removefirst(node *a)
{
//string z = tostr(a);
pair<node*,node*> r;
//string ll = tostr(a->left);
//string rr = tostr(a->right);
push(a);
if (a->left)
{
node *a_left = a->left;
a->left = NULL;
a->sz -= a_left->sz;
a->mv = a->v1;
if (a->right)
a->mv = max(a->v1, a->pv + a->right->mv);
r = removefirst(a_left);
r.first = merge(r.first, a);
}
else
{
node *a_right = a->right;
if (a_right)
{
a->sz -= a_right->sz;
a->right = NULL;
a->mv = a->v1;
}
r.second = a;
r.first = a_right;
}
//printf("remove first (%s) (%s) (%s) = %s\n", z.c_str(), ll.c_str(), rr.c_str(), tostr(r).c_str());
return r;
}
int getsz(node *a, int x)
{
if (!a)
return 0;
if (a->v < x)
return (a->left ? a->left->sz : 0) + 1 + getsz(a->right, x);
return getsz(a->left, x);
}
pair<node*,node*> split_vidx(node *a, int x, int idx)
{
if (!a)
return pair<node*,node*>((node*)0, (node*)0);
pair<node*,node*> tmp;
//vector<int> qwe = grab(a,0);
//pair<node*,node*> ans;
push(a);
if (x < a->v || (x == a->v && idx <= a->idx))
{
if (a->left)
{
a->sz -= a->left->sz;
tmp = split_vidx(a->left, x, idx);
a->left = NULL;
a->mv = a->v1;
if (a->right)
a->mv = max(a->mv, a->right->mv + a->pv);
return pair<node*,node*>(tmp.first, merge(tmp.second,a));
}
else
return pair<node*,node*>((node*)NULL,a);
}
else
{
if (a->right)
{
a->sz -= a->right->sz;
tmp = split_vidx(a->right,x,idx);
a->right = NULL;
a->mv = a->v1;
if (a->left)
a->mv = max(a->mv, a->left->mv + a->pv);
return pair<node*,node*>(merge(a, tmp.first), tmp.second);
}
else
return pair<node*,node*>(a, (node*)NULL);
}
/*vector<int> qwe1 = grab(ans.first,0);
vector<int> qwe2 = grab(ans.second,0);
for (int i = 0; i < qwe2.size(); ++i)
qwe1.push_back(qwe2[i]);
if (qwe1 != qwe)
{
printf("======= wrong split ====\n");
for (int i = 0; i < qwe.size(); ++i)
printf("%d ", qwe[i]);
printf("\n");
for (int i = 0; i < qwe1.size(); ++i)
printf("%d ", qwe1[i]);
printf("\n [%s] %d\n", tostr(a).c_str(), x);
}
return ans;*/
}
node* add_bigger(node* n, int x, int delta)
{
pair<node*,node*> s = split_vidx(n, x, 0);
//printf("add_bigger %d %d [%s] [%s]\n", x, delta, tostr(s.first).c_str(), tostr(s.second).c_str());
if (s.second)
{
s.second->pv += delta;
s.second->v1 += delta;
s.second->mv += delta;
}
node *r = merge(s.first, s.second);
/*printf("%s\n", tostr(r).c_str());
vector<int> aa = grab(r, 0);
printf("[");
for (int i = 0; i < aa.size(); ++i)
printf("%d ", aa[i]);
printf("]\n");*/
return r;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int Q = X.size();
int N = A.size();
vector<int> answer(Q);
node* root = NULL;
for (int j = 0; j < Q; ++j)
{
//printf("j %d\n", j);
if (j == 0)
{
A[X[j]] = V[j];
/*for (int i = 0; i < N; ++i)
printf("%d ", A[i]);
printf("\n");*/
vector<int> B = A;
sort(B.begin(), B.end());
for (int i = 0; i < N; ++i)
{
int c = upper_bound(B.begin(), B.end(), A[i]) - B.begin();
node *nd = new node();
nd->h = rand()*32000+rand();
nd->v = A[i];
nd->idx = i;
nd->v1 = i + 1 - c;
nd->pv = 0;
nd->mv = nd->v1;
nd->sz = 1;
nd->left = NULL;
nd->right = NULL;
pair<node*,node*> s = split_vidx(root, A[i], i);
//printf("split_vidx [%s] [%s]\n", tostr(s.first).c_str(), tostr(s.second).c_str());
root = merge(merge(s.first, nd),s.second);
//printf("init %d %s\n", i, tostr(root).c_str());
}
}
else
{
/*for (int i = 0; i < N; ++i)
printf("%d ", A[i]);
printf("\n");
printf("X[%d] = %d V[%d] = %d\n", j, X[j], j, V[j]);*/
int awas = A[X[j]];
pair<node*,node*> s = split_vidx(root, awas, X[j]);
pair<node*,node*> rf = removefirst(s.second);
root = merge(s.first, rf.first);
//printf("after delete %s\n", tostr(root).c_str());
root = add_bigger(root, awas,1);
root = add_bigger(root, V[j],-1);
//printf("after modification %s\n", tostr(root).c_str());
int c = getsz(root, V[j]+1);
//printf("sz = %d\n", c);
node *nd = rf.second;
nd->h = rand()*32000+rand();
nd->v = V[j];
nd->idx = X[j];
nd->v1 = X[j] + 1 - c - 1;
nd->pv = 0;
nd->mv = nd->v1;
nd->sz = 1;
nd->left = NULL;
nd->right = NULL;
pair<node*,node*> s1 = split_vidx(root, V[j], X[j]);
root = merge(merge(s1.first, nd),s1.second);
}
A[X[j]] = V[j];
/*{
vector<int> B = A;
sort(B.begin(), B.end());
vector<pair<pair<int,int>,int>> tmp2;
for (int z = 0; z < N; ++z)
{
int c = upper_bound(B.begin(), B.end(), A[z]) - B.begin();
tmp2.push_back(pair<pair<int,int>,int>(pair<int,int>(A[z],z),z+1-c));
}
sort(tmp2.begin(), tmp2.end());
vector<int> tmp;
for (int z = 0; z < N; ++z)
{
tmp.push_back(tmp2[z].second);
printf("(%d %d %d)", tmp2[z].first.first, tmp2[z].first.second, tmp2[z].second);
}
printf("\n");
vector<int> tmp1 = grab(root, 0);
if (tmp1 != tmp)
printf("====== wrong ====\n");
{ for (int z = 0; z < tmp.size(); ++z)
printf("%d ", tmp[z]);
printf("\n");
for (int z = 0; z < tmp1.size(); ++z)
printf("%d ", tmp1[z]);
printf("\n");
}
}
printf("now %s ans = %d\n", tostr(root).c_str(), root->mv);*/
answer[j] = root->mv;
}
return answer;
}
