#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int B = 9;
int n, m, a[400400];
multiset<int> mx[808];
priority_queue<int, vector<int>, greater<>> pq[808];
void update_block(int u) {
if(pq[u].empty()) return;
for(int i=(u << B);i<min(n, (u+1 << B));i++) if(a[i] > pq[u].top()) {
mx[u].erase(mx[u].find(a[i]));
pq[u].push(a[i]), a[i] = pq[u].top(), pq[u].pop();
mx[u].insert(a[i]);
}
while(!pq[u].empty()) pq[u].pop();
}
int update(int l, int r, int z) {
int lb = l >> B, rb = r >> B;
update_block(lb), update_block(rb);
int L = (lb+1 << B);
for(int i=l;i<=min(r, L-1);i++) if(a[i] > z) {
mx[lb].erase(mx[lb].find(a[i]));
swap(a[i], z);
mx[lb].insert(a[i]);
}
if(r < L) return z;
for(int i=lb+1;i<rb;i++) if(z < *mx[i].rbegin()) {
int u = *mx[i].rbegin();
mx[i].erase(mx[i].find(u));
pq[i].push(z), mx[i].insert(z), z = u;
}
for(int i=(rb << B);i<=r;i++) if(a[i] > z) {
mx[rb].erase(mx[rb].find(a[i]));
swap(a[i], z);
mx[rb].insert(a[i]);
}
return z;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<n;i++) mx[i >> B].insert(a[i]);
while(m--) {
int l, r, z; cin >> l >> r >> z; l--, r--;
cout << (r < l ? update(0, r, update(l, n-1, z)) : update(l, r, z)) << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |