#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//*find_by_order: iterator to kth elem (0-indexed)
//order_of_key: # of items < k (stictly less)
using ll = long long;
const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
bool sorted(vector<int> a) {
int n = a.size();
for (int i=1; i<n; i++) {
if (a[i] < a[i-1]) return false;
}
return true;
}
int brute(vector<int> a) {
int n = a.size();
int res = 0;
while (!sorted(a)) {
res++;
for (int i=0; i<n-1; i++) {
if (a[i] > a[i+1]) swap(a[i], a[i+1]);
}
}
return res;
}
int solve(vector<int> a) {
vector<int> sa = a;
int n = a.size();
sort(sa.begin(), sa.end());
map<int,vector<int>> inds;
for (int i=n-1; i>=0; i--) {
inds[sa[i]].push_back(i);
}
int mx = 0;
for (int i=0; i<n; i++) {
int to = inds[a[i]].back();
if (to < i) {
mx = max(mx, i-to);
}
inds[a[i]].pop_back();
}
return mx;
}
int solveInversion(vector<int> a) {
map<int,int> ind;
ordered_set<pair<int,int>> os;
int hi = 0;
for (int x: a) {
pair<int,int> cur = {x, ind[x]++};
int lte = os.order_of_key(cur);
int inv = int(os.size()) - lte;
hi = max(hi, inv);
os.insert(cur);
}
return hi;
}
void print(vector<int> a) {
for (int i: a) cout<<i<<" ";
cout<<endl;
}
vector<int> solveTask3(vector<int> A, vector<int> X, vector<int> V) {
//cerr<<"task3"<<endl;
int n = A.size();
vector<set<int>> inds(102);
for (int i=0; i<n; i++) {
inds[A[i]].insert(i);
}
vector<int> ans;
for (int q=0; q<(int)X.size(); q++) {
int idx = X[q];
int val = V[q];
inds[A[idx]].erase(idx);
A[idx] = val;
inds[A[idx]].insert(idx);
int mx = 0;
int prev = 0;
for (int i=1; i<=100; i++) {
if (inds[i].empty()) {
continue;
}
int dest = prev + int(inds[i].size()) - 1;
int dist = *inds[i].rbegin() - dest;
mx = max(mx, dist);
prev += int(inds[i].size());
}
//assert(mx == brute(A));
ans.push_back(mx);
}
return ans;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
if (max(*max_element(A.begin(),A.end()), *max_element(V.begin(),V.end())) <= 100) {
return solveTask3(A,X,V);
}
int Q = X.size();
vector<int> res(Q);
for (int i=0; i<Q; i++) {
A[X[i]] = V[i];
res[i] = solveInversion(A);
// assert(res[i] == brute(A));
}
return res;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n,q;
cin>>n>>q;
vector<int> a(n);
for (int i=0; i<n; i++) {
cin>>a[i];
}
vector<int> x, v;
while (q--) {
int i, val;
cin>>i>>val;
x.push_back(i);
v.push_back(val);
}
auto res = countScans(a,x,v);
for (int i: res) cout<<i<<" ";
cout<<endl;
return 0;
}
Compilation message
/tmp/ccHMpy98.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccAMXePM.o:bubblesort2.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
