#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"
const int ar = 5e5 + 5;
const ll mod = 1e9 + 7;
int n, q;
int a[ar];
int pos[ar], x[ar];
vector<int> nen;
set<int> lis[ar * 2];
int st[(1 << 21) + 5];
int lz[(1 << 21) + 5];
void down(int id, int l, int r)
{
if (lz[id] == 0) return;
st[id] += lz[id];
if (l != r)
{
lz[id << 1] += lz[id];
lz[id << 1 | 1] += lz[id];
}
lz[id] = 0;
}
void update(int id, int l, int r, int u, int v, int val)
{
if (u > v) return;
down(id, l, r);
if (l > v || r < u) return;
if (u <= l && r <= v)
{
lz[id] += val;
down(id, l, r);
return;
}
int mid = l + r >> 1;
update(id << 1, l, mid, u, v, val);
update(id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
void update(int p, int add, int sub)
{
int id = 1;
int l = 1;
int r = nen.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
down(id << 1, l, mid);
down(id << 1 | 1, mid + 1, r);
if (mid >= p)
{
id <<= 1;
r = mid;
}
else
{
id = id << 1 | 1;
l = mid + 1;
}
}
st[id] += add - sub;
while(id > 1)
{
id >>= 1;
st[id] = max(st[id << 1], st[id << 1 | 1]);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if (fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
nen.push_back(a[i]);
}
for (int i = 1; i <= q; i++)
{
cin >> pos[i] >> x[i];
pos[i]++;
nen.push_back(x[i]);
}
nen.push_back(0);
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
for (int i = 1; i < nen.size(); i++) lis[i].insert(0);
for (int i = 1; i <= n; i++)
{
a[i] = lower_bound(nen.begin(), nen.end(), a[i]) - nen.begin();
update(a[i], i, *lis[a[i]].rbegin());
lis[a[i]].insert(i);
update(1, 1, nen.size() - 1, a[i], nen.size() - 1, -1);
}
for (int i = 1; i <= q; i++)
{
x[i] = lower_bound(nen.begin(), nen.end(), x[i]) - nen.begin();
update(1, 1, nen.size() - 1, a[pos[i]], nen.size() - 1, 1);
update(1, 1, nen.size() - 1, x[i], nen.size() - 1, -1);
if (pos[i] == *lis[a[pos[i]]].rbegin())
{
update(a[pos[i]], *(--lis[a[pos[i]]].rbegin()), pos[i]);
}
if (pos[i] > *lis[x[i]].rbegin())
{
update(x[i], pos[i], *lis[x[i]].rbegin());
}
lis[a[pos[i]]].erase(pos[i]);
lis[x[i]].insert(pos[i]);
a[pos[i]] = x[i];
cout << st[1] << '\n';
}
}
Compilation message
bubblesort2.cpp: In function 'void update(int, int, int, int, int, int)':
bubblesort2.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int mid = l + r >> 1;
| ~~^~~
bubblesort2.cpp: In function 'void update(int, int, int)':
bubblesort2.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = l + r >> 1;
| ~~^~~
bubblesort2.cpp: In function 'int main()':
bubblesort2.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 1; i < nen.size(); i++) lis[i].insert(0);
| ~~^~~~~~~~~~~~
bubblesort2.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccAornHe.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUXansf.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccAornHe.o: in function `main':
grader.cpp:(.text.startup+0x181): 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
