题解：P5356 [Ynoi Easy Round 2017] 由乃打扑克

· · 题解

基本思路

需要数据结构维护区间信息，考虑分块。

询问

对于每一个询问，需要查 [L,R] 的 k 小值，不妨离散化后二分答案，因此需要求解 x 在区间 [L,R] 中的排名，即求解 [L,R] 有多少值小于等于 x。

对于零散块，直接暴力扫一遍统计即可。

对于整的块，我们需要知道整的块中有多少小于等于 x，所以可以对每一个块分别排序，然后二分出第一个大于等于 x 的下标，然后统计答案即可。

修改

对于零散块，暴力修改，记得修改完要重新排一遍序。

对于整块，我们用 tag_i 表示第 i 个整块加了多少，每次访问的时候把标记加上即可。

其他技巧

如果你 TLE 飞，可以尝试维护出区间最大最小值，然后每次二分答案范围取 [MIN,MAX]。

如果你还是 TLE，可以尝试加入有力的剪枝。求解每一个块中小于等于 x 的值的个数时，如果最小值都大于 x，返回 0，如果最大值都小于等于 x，返回区间长度。

AC Code

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = a; i <= b; ++i)
#define _F(i, a, b) for (int i = a; i >= b; --i)
#define ll long long
using namespace std;
ll rd() {
    ll p = 0, f = 1; char ch = getchar();
    while (ch>'9' || ch<'0') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch>='0' && ch<='9') p = p*10+ch-'0', ch = getchar();
    return p * f;
}
const int N = 1e5 + 5, BN = sqrt(N) + 5;
const ll inf = 5e9;
ll n, m, a[N];
namespace Blocks {
    ll SIZ, SC, st[BN], ed[BN], b[N], tag[BN];
    ll id(ll x) {return (x+SIZ-1) / SIZ;}
    void Pre() {
        SIZ = sqrt(n), SC = id(n);
        F(i, 1, SC) st[i] = ed[i-1] + 1, ed[i] = i * SIZ;
        ed[SC] = n;
        F(i, 1, SC) sort(b + st[i], b + ed[i] + 1);
    }
    void MoB(ll l, ll r, ll x) {
        ll lid = id(l);
        F(i, l, r) a[i] += x;
        F(i, st[lid], ed[lid]) b[i] = a[i];
        sort(b + st[lid], b + ed[lid] + 1);
    }
    void Modify(ll l, ll r, ll x) {
        ll lid = id(l), rid = id(r);
        if (lid == rid) {
            MoB(l, r, x);
            return ;
        }
        MoB(l, ed[lid], x), MoB(st[rid], r, x);
        F(i, lid + 1, rid - 1) tag[i] += x; 
    }
    ll Check(ll l, ll r, ll x) { // 统计有多少个数小于等于x
        ll ans = 0, lid = id(l), rid = id(r);
        if (lid == rid) {
            F(i, l, r) if (a[i] + tag[lid] <= x) ++ans;
            return ans;
        }
        F(i, l, ed[lid]) if (a[i] + tag[lid] <= x) ++ans;
        F(i, st[rid], r) if (a[i] + tag[rid] <= x) ++ans;
        F(i, lid+1, rid-1) {
            if (b[st[i]] + tag[i] > x) continue;
            if (b[ed[i]] + tag[i] <= x) {ans += ed[i]-st[i]+1; continue;}
            ans += upper_bound(b + st[i], b + ed[i] + 1, x - tag[i]) - b - st[i];
        }
        return ans;
    }
    ll Qmin(ll l, ll r) {
        ll lid = id(l), rid = id(r), res = inf;
        if (lid == rid) {
            F(i, l, r) res = min(res, a[i] + tag[lid]);
            return res;
        }
        F(i, l, ed[lid]) res = min(res, a[i] + tag[lid]);
        F(i, st[rid], r) res = min(res, a[i] + tag[rid]);
        F(i, lid+1, rid-1) res = min(res, b[st[i]] + tag[i]);
        return res;
    }
    ll Qmax(ll l, ll r) {
        ll lid = id(l), rid = id(r), res = -inf;
        if (lid == rid) {
            F(i, l, r) res = max(res, a[i] + tag[lid]);
            return res;
        }
        F(i, l, ed[lid]) res = max(res, a[i] + tag[lid]);
        F(i, st[rid], r) res = max(res, a[i] + tag[rid]);
        F(i, lid+1, rid-1) res = max(res, b[ed[i]] + tag[i]);
        return res;
    }
    ll Qkth(ll L, ll R, ll k) {
        ll l = Qmin(L, R), r = Qmax(L, R), mid, ans = -1;
        while (l <= r) {
            mid = (l + r + 1) >> 1;
            ll cur = Check(L, R, mid);
            if (cur < k) l = mid + 1;
            else r = mid - 1, ans = mid;
        }
        return ans;
    }
}
using namespace Blocks;
int main() {
    n = rd(), m = rd();
    F(i, 1, n) a[i] = rd(), b[i] = a[i];
    Pre();
    F(_popo__popo__popo_, 1, m) {
        ll op = rd(), l = rd(), r = rd(), k = rd();
        if (op == 1) cout << Qkth(l, r, k) << '\n';
        else Modify(l, r, k);
    }
    return 0;
}