P5356 [Ynoi Easy Round 2017] 由乃打扑克 Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{add}(l,r,x)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i+x$.
• $\mathrm{kth}(l,r,k)$：求 $a_{l\cdots r}$ 中第 $k$ 小的值，无解输出 $-1$.

Limitations

$1\le n,m\le 10^5$
$|a_i|,|x|\le 2\times 10^4$
$2\text{s},128\text{MB}$

Solution

看到这种很难维护的操作，考虑分块，每块分别拷贝一份 $p_i$ 并进行升序排序.
先考虑 $\mathrm{kth}$，先取 $a_{l\cdots r}$ 中的最小值和最大值.
若 $k=1$，答案为最小值，若 $k=r-l+1$，答案为最大值，若超出范围则为 $-1$，否则以最小值和最大值为左右端点，进行二分.
对于 $\mathrm{check}$，求出区间内不大于 $\text{mid}$ 的数的个数，具体就是散块暴力，整块二分，外层二分出的结果就是答案.

再考虑 $\mathrm{add}$，整块显然打上 $\text{tag}$。
对于散块，由于 $a_i$ 和 $p_i$ 都要更新，我们将加过 $x$ 和没加过 $x$ 的部分分成两个数组，再进行归并.

注意分块的标记是永久化的，计算时不要漏了.
要开 long long，否则会被 hack.

Code

$4.48\text{KB},11.20\text{s},3.92\text{MB}\text{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}#ifdef LOCAL
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endiftemplate<class T>
inline T read() {T x = 0, f = 1;char ch = getchar_unlocked();while (ch < '0' || ch > '9') {if (ch == '-') f = -1;ch = getchar_unlocked();}while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48);ch = getchar_unlocked();}return x * f;
}template<class T>
inline void write(T x) {if (x < 0) {putchar_unlocked('-');x = -x;}if (x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');return;
}constexpr int B = 256;
constexpr i64 inf = 6e18;
struct Node {i64 val;int pos;inline Node() {}inline Node(i64 _val, int _pos) : val(_val), pos(_pos) {}bool operator<(const Node& rhs) const { return val < rhs.val; }
};struct Block {int n, blocks;vector<i64> a, tag;vector<int> belong, L, R;vector<Node> p, t1, t2;inline Block() {}inline Block(const vector<i64>& _a) : a(_a) {n = a.size();blocks = (n + B - 1) / B;p.resize(n), belong.resize(n);L.resize(blocks), R.resize(blocks), tag.resize(blocks);for (int i = 0; i < blocks; i++) {L[i] = i * B;R[i] = min(L[i] + B, n) - 1;for (int j = L[i]; j <= R[i]; j++) {belong[j] = i;p[j] = Node(a[j], j);}sort(p.begin() + L[i], p.begin() + R[i] + 1);}}inline pair<i64, i64> bound(int l, int r) {int bl = belong[l], br = belong[r];i64 vl = inf, vr = -inf;if (bl == br) {for (int i = l; i <= r; i++) {vl = min(vl, a[i] + tag[bl]);vr = max(vr, a[i] + tag[bl]);}}else {for (int i = l; i <= R[bl]; i++) {vl = min(vl, a[i] + tag[bl]);vr = max(vr, a[i] + tag[bl]);}for (int i = L[br]; i <= r; i++) {vl = min(vl, a[i] + tag[br]);vr = max(vr, a[i] + tag[br]);}for (int i = bl + 1; i < br; i++) {vl = min(vl, p[L[i]].val + tag[i]);vr = max(vr, p[R[i]].val + tag[i]);}}return {vl, vr};}inline int count(int l, int r, int k) {int res = 0, bl = belong[l], br = belong[r];if (bl == br) {for (int i = l; i <= r; i++) res += (a[i] + tag[bl] <= k);}else {for (int i = l; i <= R[bl]; i++) res += (a[i] + tag[bl] <= k);for (int i = L[br]; i <= r; i++) res += (a[i] + tag[br] <= k);for (int i = bl + 1; i < br; i++) {int vl = L[i], vr = R[i];if (p[vl].val + tag[i] > k) continue;if (p[vr].val + tag[i] <= k) {res += vr - vl + 1;continue;}while (vl < vr) {int mid = ((vl + vr) >> 1) + 1;if (p[mid].val + tag[i] <= k) vl = mid;else vr = mid - 1;}if (p[vl].val + tag[i] <= k) res += vl - L[i] + 1;}}return res;}inline i64 kth(int l, int r, int k) {auto [vl, vr] = bound(l, r);const int len = r - l + 1;if (k == 1) return vl;if (k == len) return vr;if (k < 1 || k > len) return -1;i64 res = -1;while (vl <= vr) {i64 mid = (vl + vr) >> 1;if (count(l, r, mid) < k) vl = mid + 1;else vr = (res = mid) - 1;}return res;}inline void msort(int l, int r, int b, int k) {t1.clear(), t2.clear();for(int i = L[b]; i <= R[b]; i++) {if (i >= l && i <= r) a[i] += k;if (p[i].pos >= l && p[i].pos <= r) t1.push_back(Node(p[i].val + k, p[i].pos));else t2.push_back(p[i]);}int lp = 0, rp = 0, ptr = L[b];while (ptr <= R[b]) {if (lp < t1.size() && (rp >= t2.size() || t1[lp].val < t2[rp].val)) p[ptr++] = t1[lp++];else p[ptr++] = t2[rp++];}}inline void add(int l, int r, int k) {int bl = belong[l], br = belong[r];msort(l, r, bl, k);if (bl != br) {msort(l, r, br, k);for (int i = bl + 1; i < br; i++) tag[i] += k;}}
};signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);const int n = read<int>(), m = read<int>();vector<i64> a(n);for (int i = 0; i < n; i++) a[i] = read<i64>();Block blk(a);for (int i = 0, op, l, r, k; i < m; i++) {op = read<int>(), l = read<int>(), r = read<int>(), k = read<int>();l--, r--;if (op == 1) write(blk.kth(l, r, k)), putchar_unlocked('\n');else blk.add(l, r, k);}return 0;
}