#include <bits/stdc++.h>
#include <bubblesort2.h>
#define pb push_back
#define int long long
using namespace std;
const int MAXN = 500000;
const int K = 10000000;
int n, q;
int a[MAXN*2+5];
int cpy[MAXN*2+5];
class Seg{
private:
int arr[MAXN*2*4+5];
int tag[MAXN*2*4+5];
void pull(int now) {
arr[now] = max(arr[now*2], arr[now*2+1]);
}
void push(int now, int len) {
if (!tag[now]) return;
arr[now] += tag[now];
if (len > 1) {
tag[now*2 ] += tag[now];
tag[now*2+1] += tag[now];
}
tag[now] = 0;
}
public:
void build(int now=1, int l=1, int r=MAXN*2) {
if (l == r) {
arr[now] = a[l];
return;
}
int mid = l + r >> 1;
build(now*2 , l, mid);
build(now*2+1,mid+1,r);
pull(now);
return;
}
void mdy(int ml, int mr, int k, int now=1, int l=1, int r=MAXN*2) {
push(now, r-l+1);
if (l >= ml && r <= mr) {
arr[now] += k;
push(now, r-l+1);
return;
} else if (l > mr || r < ml) return;
int mid = l + r >> 1;
mdy(ml, mr, k, now*2 , l, mid);
mdy(ml, mr, k, now*2+1,mid+1,r);
pull(now);
}
int qry() {
return arr[1];
}
} seg;
vector <int> countScans(vector <int> A, vector <int> X, vector <int> Y) {
int n = A.size(), q = Y.size();
for (int i = 0; i < n; i++)
cpy[i] = A[i] * K + i;
for (int i = 0; i < q; i++)
cpy[i+n] = Y[i] * K + X[i];
sort(cpy, cpy+n+q);
for (int i = 0; i < n; i++)
A[i] = lower_bound(cpy, cpy+n+q, A[i] * K + i) - cpy + 1;
for (int i = 0; i < q; i++)
Y[i] = lower_bound(cpy, cpy+n+q, Y[i] * K + X[i]) - cpy + 1;
for (int i = 0; i < n; i++)
seg.mdy(A[i], n+q, -1);
vector <int> ans;
for (int i = 0; i < q; i++) {
seg.mdy(A[X[i]], n+q, 1);
seg.mdy(Y[i], n+q, -1);
A[X[i]] = Y[i];
ans.pb(seg.qry());
}
return ans;
}
Compilation message
bubblesort2.cpp: In member function 'void Seg::build(long long int, long long int, long long int)':
bubblesort2.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
bubblesort2.cpp: In member function 'void Seg::mdy(long long int, long long int, long long int, long long int, long long int, long long int)':
bubblesort2.cpp:48:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
/tmp/cc4H2jNz.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
