相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf
解题报告
看到这题我们不难想到分块
更进一步,对于每一个块来说,块内的数的相对大小不变
于是我们只需要用堆便可维护块内有哪些数
再稍加观察,我们发现只要再用一个堆记录块内的操作,然后从左向右扫一遍便可更新具体的数
于是我们就可以在:$O(n^{1.5} \log n)$的时间复杂度内解决这个问题了
另外priority_queue
的构造函数是$O(n)$的
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10;
int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];
inline int read() {
char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}
inline void get_element(int w) {
if (opr[w].empty()) {
return;
}
priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end());
for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
if (arr[i] > heap.top()) {
heap.push(arr[i]);
arr[i] = heap.top();
heap.pop();
}
}
opr[w].clear();
}
inline int modify_element(int w, int s, int t, int v) {
get_element(w);
int tmp = -1;
for (int i = s; i <= t; i++) {
if (v < arr[i]) {
tmp = arr[i];
swap(v, arr[i]);
}
}
val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
return v;
}
inline int modify_block(int w, int v) {
val[w].push(v);
int ret = val[w].top();
val[w].pop();
if (v != ret) {
opr[w].push_back(v);
}
return ret;
}
inline int solve(int s, int t, int v) {
int ss = s / S, st = t / S;
v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
if (ss != st) {
for (int i = ss + 1; i < st; i++) {
v = modify_block(i, v);
}
v = modify_element(st, st * S, t, v);
}
return v;
}
int main() {
n = read(); m = read();
sn = n / S;
for (int i = 1; i <= n; i++) {
arr[i] = read();
}
for (int i = 0; i <= sn; i++) {
val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
}
for (int tt = 1; tt <= m; tt++) {
int s = read(), t = read(), v = read();
if (s <= t) {
v = solve(s, t, v);
} else {
v = solve(s, n, v);
v = solve(1, t, v);
}
printf("%d\n", v);
}
return 0;
}