#include <bits/stdc++.h> using namespace std; #define nmax 1000007 typedef long long ll; typedef pair<int,int> pii; int n, q; ll a[nmax]; int vt[nmax]; ll val[nmax]; // Compression vector vector<pair<ll, pii>> b; // Rời rạc hóa giá trị void roirac() { sort(b.begin(), b.end()); int counter = 1; if(b[0].second.second) a[b[0].second.first] = 1; else val[b[0].second.first] = 1; for(int i = 1; i < b.size(); i++) { if(b[i].first != b[i-1].first) counter++; if(b[i].second.second) a[b[i].second.first] = counter; else val[b[i].second.first] = counter; } } // Tính số lần pass sau mỗi query (chỉ áp dụng khi n, q <= 8000) vector<int> sub3() { vector<int> res; int b2[nmax]; for(int k = 1; k <= q; k++) { a[vt[k]] = val[k]; for(int i = 1; i <= n; i++) b2[i] = a[i]; sort(b2 + 1, b2 + n + 1); vector<queue<int>> mp(8007); for(int i = 1; i <= n; i++) mp[b2[i]].push(i); int pass = 0; for(int i = 1; i <= n; i++) { int correct_pos = mp[a[i]].front(); mp[a[i]].pop(); if(i > correct_pos) pass = max(pass, i - correct_pos); } res.push_back(pass); } return res; } // Hàm countScans theo yêu cầu vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) { n = A.size(); q = X.size(); for(int i = 0; i < n; i++) { a[i+1] = A[i]; b.push_back({A[i], {i+1, 1}}); } for(int i = 0; i < q; i++) { vt[i+1] = X[i] + 1; // giả sử X[i] 0-based val[i+1] = V[i]; b.push_back({V[i], {i+1, 0}}); } roirac(); return sub3(); }