yaoxi-std 的博客

$\text{开}\mathop{\text{卷}}\limits^{ju\check{a}n}\text{有益}$

0%

P5356 [Ynoi2017] 由乃打扑克

发表于 分类于

P5356 [Ynoi2017] 由乃打扑克

题面

题目链接

解法

看到 Ynoi 第一时间想到分块。

关于区间第 $k$ 大，一般的做法是主席树，动态单点修改的做法就是树套树，或者分块套值域分块。但是这题不仅区间修改，值域也很大。

而区间第 $k$ 大有个更加暴力的分块，就是给每个块排序，查询的时候二分。

考虑如何修改，对于散块暴力重构，整块打上标记。重构的时候不要直接 sort，而是归并排序，可以丢掉一个 $\log$。

查询的时候，将周围的两个散块归并成一个，然后直接二分。

假设块大小为 $S$，那么一次修改的复杂度就是 $O(\frac{n}{S} + S)$，一次查询的复杂度是 $O(\frac{n}{S} \log S \log a)$。当 $S=\sqrt{n}\log n$ 的时候修改和查询的复杂度平衡，均为 $O(\sqrt{n} \log n)$。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/**
 * @file:           P5356.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P5356
*/
// #pragma GCC optimize ("O2")
// #pragma GCC optimize ("Ofast", "inline", "-ffast-math")
// #pragma GCC target ("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
using namespace std;
#define resetIO(x) \
    freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define debug(fmt, ...) \
    fprintf(stderr, "[%s:%d] " fmt "\n", __FILE__, __LINE__, ##__VA_ARGS__)
namespace fastio {
const int MAXBUF = 1 << 21;
char buf[MAXBUF], *p1 = buf, *p2 = buf;
char pbuf[MAXBUF], *pp = pbuf;
inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), *p1++; }
inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
};  // namespace fastio
using namespace fastio;
template <class _Tp>
inline _Tp& read(_Tp& x) {
    bool sign = false; char ch = getc();
    for (; !isdigit(ch); ch = getc()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>
inline void write(_Tp x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) write(x / 10);
    putc((x % 10) ^ 48);
}
bool m_be;
using ll = long long;
const int MAXN = 1e5 + 10;
const int MAXB = 2e3 + 10;
const int INF = 0x3f3f3f3f;
int n, q, a[MAXN], b[MAXN], tag[MAXB];
int blk, bn, pos[MAXN], bl[MAXB], br[MAXB];
int cnt, cntl, cntr, tmp[MAXN], tmpl[MAXN], tmpr[MAXN];
inline void chkmin(int& x, int y) { (x > y) && (x = y); }
inline void chkmax(int& x, int y) { (x < y) && (x = y); }
inline int argcmp(int x, int y) { return a[x] < a[y]; }
inline void msort(int l, int r, int pl, int pr) {
    cntl = cntr = 0;
    for (int i = l; i <= r; ++i) {
        if (pl <= b[i] && b[i] <= pr) tmpl[++cntl] = b[i];
        else tmpr[++cntr] = b[i];
    }
    merge(tmpl + 1, tmpl + cntl + 1, tmpr + 1, tmpr + cntr + 1, b + l, argcmp);
}
inline int count(int l, int r, int k) {
    int ret = 0, cl = 1, cr = cnt, t = 0;
    while (cl <= cr) {
        int mid = (cl + cr) >> 1;
        if (tmp[mid] <= k) t = mid, cl = mid + 1;
        else cr = mid - 1;
    }
    ret += t;
    for (int i = pos[l] + 1; i < pos[r]; ++i) {
        int cl = bl[i], cr = br[i], t = bl[i] - 1;
        while (cl <= cr) {
            int mid = (cl + cr) >> 1;
            if (a[b[mid]] + tag[i] <= k) t = mid, cl = mid + 1;
            else cr = mid - 1;
        }
        ret += t - bl[i] + 1;
    }
    return ret;
}
bool m_ed;
signed main() {
    // debug("Mem %.5lfMB.", fabs(&m_ed - &m_be) / 1048576);
    read(n), read(q);
    for (int i = 1; i <= n; ++i) read(a[i]);
    blk = ceil(sqrt(n * log(n)) + 1e-6);
    for (int l = 1; l <= n; l += blk) {
        int r = min(n, l + blk - 1);
        ++bn, bl[bn] = l, br[bn] = r;
        for (int i = l; i <= r; ++i) pos[i] = bn;
    }
    iota(b + 1, b + n + 1, 1);
    for (int i = 1; i <= bn; ++i) sort(b + bl[i], b + br[i] + 1, argcmp);
    while (q--) {
        int op, l, r, k;
        read(op), read(l), read(r), read(k);
        if (op == 1) {
            int mn = 2e9, mx = -2e9, ans = -1;
            cnt = cntl = cntr = 0;
            if (pos[l] == pos[r]) {
                for (int i = l; i <= r; ++i)
                    chkmin(mn, a[i] + tag[pos[l]]), chkmax(mx, a[i] + tag[pos[l]]);
                for (int i = bl[pos[l]]; i <= br[pos[l]]; ++i)
                    if (l <= b[i] && b[i] <= r) tmp[++cnt] = a[b[i]] + tag[pos[l]];
            } else {
                for (int i = l; i <= br[pos[l]]; ++i)
                    chkmin(mn, a[i] + tag[pos[l]]), chkmax(mx, a[i] + tag[pos[l]]);
                for (int i = bl[pos[r]]; i <= r; ++i)
                    chkmin(mn, a[i] + tag[pos[r]]), chkmax(mx, a[i] + tag[pos[r]]);
                for (int i = pos[l] + 1; i < pos[r]; ++i)
                    chkmin(mn, a[b[bl[i]]] + tag[i]), chkmax(mx, a[b[br[i]]] + tag[i]);
                for (int i = bl[pos[l]]; i <= br[pos[l]]; ++i)
                    if (l <= b[i] && b[i] <= r) tmpl[++cntl] = a[b[i]] + tag[pos[l]];
                for (int i = bl[pos[r]]; i <= br[pos[r]]; ++i)
                    if (l <= b[i] && b[i] <= r) tmpr[++cntr] = a[b[i]] + tag[pos[r]];
                cnt = cntl + cntr;
                merge(tmpl + 1, tmpl + cntl + 1, tmpr + 1, tmpr + cntr + 1, tmp + 1);
            }
            if (k == 1) {
                write(mn), putc('\n');
            } else if (k == r - l + 1) {
                write(mx), putc('\n');
            } else if (k < 1 || k > r - l + 1) {
                write(-1), putc('\n');
            } else {
                while (mn <= mx) {
                    int mid = (mn + mx) >> 1;
                    if (count(l, r, mid) >= k) mx = mid - 1, ans = mid;
                    else mn = mid + 1;
                }
                write(ans), putc('\n');
            }
        } else {
            if (pos[l] == pos[r]) {
                for (int i = l; i <= r; ++i) a[i] += k;
                msort(bl[pos[l]], br[pos[l]], l, r);
            } else {
                for (int i = l; i <= br[pos[l]]; ++i) a[i] += k;
                for (int i = bl[pos[r]]; i <= r; ++i) a[i] += k;
                msort(bl[pos[l]], br[pos[l]], l, r);
                msort(bl[pos[r]], br[pos[r]], l, r);
                for (int i = pos[l] + 1; i < pos[r]; ++i) tag[i] += k;
            }
        }
    }
    return print_final(), 0;
}