相关链接
题目传送门: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; }