#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T = int, class O = less<T>>
struct heap_set {
priority_queue<T, vector<T>, O> pq, rpq;
const T& top() const { return pq.top(); }
int size() const { return int(pq.size() - rpq.size()); }
bool empty() const { return !size(); }
void flush() { while(rpq.size() && pq.top() == rpq.top()) pq.pop(), rpq.pop(); }
void insert(const T x) { pq.push(x); flush(); }
void pop() { pq.pop(); flush(); }
void erase(const T x) { rpq.push(x); flush(); }
};
const int B = 10;
int n, m, a[400400];
heap_set<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()) {
pq[u].push(a[i]), a[i] = pq[u].top(), pq[u].pop();
}
while(!pq[u].empty()) mx[u].erase(pq[u].top()), 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(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].top()) {
int u = mx[i].top(); mx[i].pop();
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(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... |