题解 P5356 【[Ynoi2017]由乃打扑克】

Sol1 · 2020-02-15 17:46:29 · 题解

lxl少有的不用怎么卡常就能过的良心题……

因为在线段树或平衡树上维护一个排好序的数组非常困难，而树套树区间加无法打 tag ，所以去考虑万能的分块。

很容易想到如下做法：

整块加打一个 tag ，零散点直接暴力加然后整个块暴力重构；查询直接二分一个值然后在每一个块内和零散点内二分查 rank ，加起来和 k 比较即可。

复杂度 O(N\sqrt{N \log N}\log N) 。

“很遗憾，被我卡掉了。” ——lxl

其实优化的方法很简单：上述做法取的块大小 S 是 \sqrt{N} ，优化就是取 S = \sqrt{N} \log N 。

这样的话，因为块内重构时，加的部分提取出来依然是有序的，没有加的部分也是有序的，所以可以 O(S) 完成。注意直接排序的 O(S \log S) 理论上是过不掉此题的。

所以此时修改就是单次 O(S)=O(\sqrt{N} \log N) 的。

而二分查询时，因为块数是 O(\frac{N}{S})=O(\frac{\sqrt N}{\log N}) 的，而因为是两个二分套在一起，所以此时查询是 O(\sqrt{N}\log N) 的。又因为可以把两边的零散点归并为一个 O(S) 大小的块来二分，所以零散点的复杂度是 O(\log N \cdot \log S) 的。

所以此时总复杂度是 O(N \sqrt N \log N) 。做法还是和暴力的 O(N\sqrt{N \log N}\log N) 一样。

代码略长。。

#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
    register char c = getchar();
    register int x = 0, f = 1;
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

const int S = (int)(317 * log2(100000)), N = 100005;
pair <int, int> a[N], ta[N], tb[N], tc[N];
int bid[N], n, m, tag[int(N / S) + 5], cnt[int(N / S) + 5], bcnt, tap, tbp, tcp, LL = 2e4, RR = -2e4;

//读入数据
inline void Read() {
    n = qread(); m = qread();
    for (register int i = 1;i <= n;i++) {
        bid[i] = (i - 1) / S + 1;
        LL = Min(LL, a[a[i].second = i].first = qread());
        RR = Max(RR, a[i].first);//求值域
    }
    bcnt = (n - 1) / S + 1;
}

//计算第idx个块的左端点和右端点
inline int BLeft(int idx) {return (idx - 1) * S + 1;}
inline int BRight(int idx) {return Min(idx * S, n);}

//块内排序
inline void Prefix() {
    for (register int i = 1;i <= bcnt;i++) {
        sort(a + BLeft(i), a + BRight(i) + 1);
    }
}

inline void Solve() {
    for (register int i = 1;i <= m;i++) {
        register int opt = qread(), l = qread(), r = qread(), k = qread();
        register int bl = bid[l], br = bid[r];
        if (opt == 2) {
            if (k > 0) RR += k;
            else LL += k;//更新值域
            tap = tbp = tcp = 0;
            if (bl == br) {
                for (register int j = BLeft(bl);j <= BRight(bl);j++) {
                    if (a[j].second >= l && a[j].second <= r) tb[++tbp] = make_pair(a[j].first + k, a[j].second);
                    else ta[++tap] = a[j];
                }
                register int i1 = 1, i2 = 1;
                while (i1 <= tap && i2 <= tbp) {
                    if (ta[i1] < tb[i2]) a[BLeft(bl) + (++tcp) - 1] = ta[i1++];
                    else a[BLeft(bl) + (++tcp) - 1] = tb[i2++];
                }
                while (i1 <= tap) a[BLeft(bl) + (++tcp) - 1] = ta[i1++];
                while (i2 <= tbp) a[BLeft(bl) + (++tcp) - 1] = tb[i2++];
            } else {
                for (register int j = bl + 1;j < br;j++) tag[j] += k;
                for (register int j = BLeft(bl);j <= BRight(bl);j++) {
                    if (a[j].second >= l) ta[++tap] = make_pair(a[j].first + k, a[j].second);
                    else tb[++tbp] = a[j];
                }
                register int i1 = 1, i2 = 1;
                while (i1 <= tap && i2 <= tbp) {
                    if (ta[i1] < tb[i2]) a[BLeft(bl) + (++tcp) - 1] = ta[i1++];
                    else a[BLeft(bl) + (++tcp) - 1] = tb[i2++];
                }
                while (i1 <= tap) a[BLeft(bl) + (++tcp) - 1] = ta[i1++];
                while (i2 <= tbp) a[BLeft(bl) + (++tcp) - 1] = tb[i2++];
                tap = tbp = tcp = 0;
                for (register int j = BLeft(br);j <= BRight(br);j++) {
                    if (a[j].second <= r) ta[++tap] = make_pair(a[j].first + k, a[j].second);
                    else tb[++tbp] = a[j];
                }
                i1 = i2 = 1;
                while (i1 <= tap && i2 <= tbp) {
                    if (ta[i1] < tb[i2]) a[BLeft(br) + (++tcp) - 1] = ta[i1++];
                    else a[BLeft(br) + (++tcp) - 1] = tb[i2++];
                }
                while (i1 <= tap) a[BLeft(br) + (++tcp) - 1] = ta[i1++];
                while (i2 <= tbp) a[BLeft(br) + (++tcp) - 1] = tb[i2++];
            }
        } else {
            if (k > r - l + 1) {
                puts("-1");
                continue;
            }
            if (bl == br) {
                tap = 0;
                for (register int j = BLeft(bl);j <= BRight(bl);j++) {
                    if (a[j].second >= l && a[j].second <= r) ta[++tap] = a[j];
                }
                printf("%d\n", ta[k].first + tag[bl]);
            } else {
                tap = tbp = tcp = 0;
                for (register int j = BLeft(bl);j <= BRight(bl);j++) {
                    if (a[j].second >= l) ta[++tap] = make_pair(a[j].first + tag[bl], a[j].second);
                }
                for (register int j = BLeft(br);j <= BRight(br);j++) {
                    if (a[j].second <= r) tb[++tbp] = make_pair(a[j].first + tag[br], a[j].second);
                }
                register int i1 = 1, i2 = 1;
                while (i1 <= tap && i2 <= tbp) {
                    if (ta[i1] < tb[i2]) tc[(++tcp)] = ta[i1++];
                    else tc[(++tcp)] = tb[i2++];
                }
                while (i1 <= tap) tc[(++tcp)] = ta[i1++];
                while (i2 <= tbp) tc[(++tcp)] = tb[i2++];
                if (bl == br - 1) {
                    printf("%d\n", tc[k].first);
                    continue;
                }
                register int ll = LL - 1, rr = RR + 1;
                while (ll < rr - 1) {
                    register int mid = (ll + rr) / 2, cnt = 0;
                    for (register int j = bl + 1;j <= br - 1;j++) {
                        register int lll = BLeft(j) - 1, rrr = BRight(j) + 1;
                        while (lll < rrr - 1) {
                            register int midmid = (lll + rrr) >> 1;
                            if (a[midmid].first + tag[j] <= mid) lll = midmid;
                            else rrr = midmid;
                        }
                        cnt += lll - BLeft(j) + 1;
                    }
                    register int lll = 0, rrr = tcp + 1;
                    while (lll < rrr - 1) {
                        register int midmid = (lll + rrr) >> 1;
                        if (tc[midmid].first <= mid) lll = midmid;
                        else rrr = midmid;
                    }
                    cnt += lll;
                    if (cnt < k) ll = mid;
                    else rr = mid;
                }
                printf("%d\n", rr);
            }
        }
    }
}

int main() {
    Read();
    Prefix();
    Solve();
    #ifndef ONLINE_JUDGE
    while (1);
    #endif
    return 0;
}