#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int Off = 1<<20;
struct SegTree {
int a[2 * Off], lazy[2 * Off];
set<int> inds[Off];
SegTree() {
for (int i = 1; i < 2 * Off; i++) a[i] = -1e9;
for (int i = 0; i < Off; i++) inds[i].insert(-1e9);
}
void propagate(int i) {
a[i] += lazy[i];
if (i < Off) {
lazy[2 * i] += lazy[i];
lazy[2 * i + 1] += lazy[i];
}
lazy[i] = 0;
}
void update_path(int j, int i = 1, int lo = 0, int hi = Off) {
propagate(i);
if (lo + 1 == hi) return;
if (lo > j || j >= hi) return;
int mid = (lo + hi) / 2;
update_path(j, 2 * i, lo, mid);
update_path(j, 2 * i + 1, mid, hi);
a[i] = max(a[2 * i], a[2 * i + 1]);
}
void update_inds(int i, int ind, bool add) {
a[i + Off] -= *inds[i].rbegin();
if (add) inds[i].insert(ind);
else inds[i].erase(ind);
a[i + Off] += *inds[i].rbegin();
update_path(i);
}
void update_segment(int l, int r, int val, int i = 1, int lo = 0, int hi = Off) {
propagate(i);
if (r <= lo || hi <= l) return;
if (l <= lo && hi <= r) {
lazy[i] += val;
propagate(i);
} else {
int mid = (lo + hi) / 2;
update_segment(l, r, val, 2 * i, lo, mid);
update_segment(l, r, val, 2 * i + 1, mid, hi);
a[i] = max(a[2 * i], a[2 * i + 1]);
}
}
void update_segment(int i, bool add) {
if (add) update_segment(i + 1, Off, -1);
else update_segment(i + 1, Off, 1);
}
int query() {
propagate(1);
return a[1];
}
} T;
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
int n = a.size(), q = x.size();
vector<int> answer(q);
vector<tuple<int, int, int>> val;
map<int, int> compress;
for (int i = 0; i < n; i++) val.push_back(make_tuple(a[i], i, i));
for (int i = 0; i < q; i++) val.push_back(make_tuple(v[i], x[i], i + n));
sort(val.begin(), val.end());
for (int i = 0; i < (int)val.size(); i++)
compress[get<2>(val[i])] = i;
for (int i = 0; i < n; i++) {
int t = compress[i];
T.update_inds(t, i, true);
T.update_segment(t, true);
}
for (int i = 0; i < n; i++) a[i] = i;
for (int i = 0; i < q; i++) {
int t = compress[a[x[i]]];
T.update_inds(t, x[i], false);
T.update_segment(t, false);
a[x[i]] = i + n;
t = compress[i + n];
T.update_inds(t, x[i], true);
T.update_segment(t, true);
answer[i] = T.query();
}
if(n > 50000) return 0;
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:118:25: error: could not convert '0' from 'int' to 'std::vector<int>'
if(n > 50000) return 0;
^
