P5356 由乃打扑克

Clover_BY · 2022-10-14 21:09:57 · 个人记录

P5356 由乃打扑克

写在前面

抱着这个数据不会出锅的flag，我TMD终于A了XD
算是做过的第一道纯正的分块吧
这个题让我知道了什么叫卡常，什么叫优化细节。

毒瘤lxl将时限缩至1s之后，现存题解许多都不能在规定时间内跑出结果，不过大多只差0.1s~0.2s通过。
但这一点小差距整个导致我重构三次，最终抛弃了题解，从我自己的思路上优化常数。
实现上和代码上可能有非常多读者不愿意看到的细节，但我绝不做无用功。希望您阅读此篇博客后能够轻松切掉此题。

题目描述

给定一个长度为 n 的序列，要求支持两种操作：

区间加
查询区间第 k 小

题目分析

~~一眼主席树，一眼错了。~~
仔细想想会发现主席树根本无法支持区间加，即使在标记永久化的前提下也不能灵活地查询第 k 小。
lxl在题目提示中也明确告诉我们：此题无 polylog 解法，只能用最朴素的分块。

对于区间加，对整块打 tag，散块暴力修改；
对于查询，先对值域进行二分，再对整块和两侧散块进行二分确定 mid 的排名，搜到结果后退出即可。
嗯，没了。

代码实现

我不认为一个人看到上面的描述能够清晰地构造好所有的细节。一但开始实现，成倍的问题会朝你涌来：

按照什么样的方式对块进行排序？
修改时如何对边角块暴力重构？
如何快速界定值域和某个元素在一整块内的位置？
查询时边角块是否直接暴力排序？
如何设置块长才能平衡查询与修改的复杂度？
............

我们对这些问题逐个进行处理。

排序

首先打破常规：对元素下标而非元素本身进行排序。
这样做是基于我们同样能手动编写 cmp 函数对下标顺序加以控制，并且同样能使此条性质作用于 lower_bound （二分）。

“那么为什么不使用相同复杂度的直接排序呢？”
问这个问题之前请先想好复杂度是否真的相同。
在下面几个模块内，我会详细分析原因。

修改

整、散先后分析。

整块

对块直接打上 tag，同时更新每个块的 minn 和 maxn。注意三个值都是直接累加即可。

散块

首先，为了节省时间开销，代码实现任意步骤时都不应出现把 tag 全部下放的步骤。tag 作为一个块内元素的共同特征，在查询时仍能够继续使用，因而不必进行操作。

之后我们考虑怎么处理。
直观的想法是暴力重构。且慢。
我们设块长为 \delta，显然我们要保证修改复杂度在 \mathcal O(\delta+\frac{n}{\delta}) 的可接受范围内。然而，暴力重构之后我们需要对块进行排序，这无疑为每次修改又增添了 \mathcal O(\delta log\delta) 的复杂度。

于是，为了减少这部分损耗，我们考虑使用归并排序。
当然，我们不能真的套个归并的板子上去，这样复杂度丝毫未减。
考虑：如果在修改之前元素就已经排好序了，我们便可以直接进行处理，将不需要修改的放进一个数组 rec1，需要的修改过后放进另一个 rec2，最后进行归并，照样放在原地。
然而直接对元素排序有个弊病：我们并不知道排序过后的哪些元素仍然在修改的区间范围内，仍然需要无差别扫一次过后再全部放进去。这时，由于元素发生变动，先前的顺序完全不能适应当前的大小关系，弥补办法只有再次使用带 log 的 sort 函数。

这种方法几乎直接流产，事实也证明用这种方式写的代码无论如何卡也都只能被限制在 76pts。（当然您常数小的话当我没说）
那我们考虑：对下标进行排序是如何避免这种问题的？
仍旧是暴力扫一遍整个块。我们来举一组栗子：

原数组：2 4 5 1 3 6
排序后：4 1 5 2 3 6（均为下标）

现在，我们对下标在 2~4 的元素加个 10，并把操作后的结果分别压入 rec1 和 rec2：

修改后：2 14 15 11 3 6（直接对原数组进行更改）
rec1：1 5 6（不需要修改）
rec2：2 3 4（需要修改）

其对应元素分别为：
rec1-> 2, 3, 6
rec2-> 4 + 10 = 14, 5 + 10 = 15, 1 + 10 = 11

进行归并：

由于2 < 3 < 6 < 11 < 14 < 15，进行归并，
归并后：1 5 6 2 3 4
对应元素：2 3 6 11 14 15

发现了吗？我们在不改变元素顺序，只是拆成两部分，修改后再次合并的解法，既能保证 \mathcal O(\delta) 的复杂度，又能继续维护元素顺序。这就是这种排序方法的优势。同时，修改操作也就说完了。
还是注意：不下放 tag （当然你下放了也行），但比较下标时记得加上。

查询

Part1 遍历元素

分为界定值域、整块部分、散块部分。默认忽略左右段点在同一块内的情况，这种情况下只能暴力 sort 元素并直接输出，我并没有更好的做法。

值域

之前在修改整块的时候提到我们维护了 minn 和 maxn，但实际上分块时已经可以维护出来了。在我的代码中，这两个值是涵盖着 tag 的（意味着查询时不需要再进行增添操作）。

定义上下界分别为 kl 和 kr，对所有元素分别取 min 和 max，最终得到的就是答案可能分布的上下界。

整块

直接遍历，随着更新上下界。比较简单。

散块

我们只有左右两个散块。为了保证复杂度，我们仍旧采用归并的形式。
这里塞进去的是下标还是元素就随你了。不过为了减少代码实现难度并维持统一，我仍然选用了下标，并使用了一个不存在的位置 shift = 100008 辅助我进行二分。

Part2 二分查找

现在我们已经有了两大部分：整块和归并后的散块，且两部分均是有序的。于是直接考虑对值域进行二分并判断答案是否合法。
界定一个 mid 值作为当前判断的对象，对两部分查找确定小于等于这个元素的个数，记为 res。若结果不小于排名则记录答案，锁定 mid 左侧，否则锁定右侧。

至此，查询函数也施工完毕。Part1 复杂度为 \mathcal O(\frac{n}{\delta}+\delta)，Part2 大概是 \mathcal O(\frac{n}{\delta}log\delta logSIZE) （吧？不会分析）
各位也都看到了我在犇犇里发的求助信息，不过当前的总复杂度比之前那一版好得多。

常数问题 & 实现细节

关于块长：我是用块数决定的块长。块数设置为 900 会T，650~750 正好。
使用具有针对性的函数。代码中为了适配 int 和 long long，我将输入输出以及归并函数都复写了两份。删掉快读快写中适配字符串的部分能一定程度上缩小常数。
对块排序直接用一整个数组。本人代码中为 rebuild。查询、修改时位置界定以块的左右端点下标 st 和 ed 为准。
查询函数中特判 k < 1, k > r - l + 1, k == 1 和 k == r - l + 1，lower_bound 之前线先行确定 mid 与最大最小值关系，在范围之外直接跳过并加上相应的值即可。
minn 和 maxn 在初统计时不要读入一个比较一个。排序后直接赋值。
注意下标位置以及 tag 的有无。

当然，我们都不可能一次写对，因此请抱着耐心调试。

由于lxl给的样例过水，请自行参考讨论区中的一篇帖子进行调试。（当然数据过小的话 \delta=750 也调不出来）
此处提供本人用了四天的数据生成器 & 暴力对拍程序。自行调参即可。

//data-maker
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
int l, r, ope, x;
int main()
{
    freopen("aaa.txt", "w", stdout);
    printf("100000\n100000\n");
    const int n = 100000, m = 100000;
    srand(time(0));
    for(register int i = 1; i <= n; ++i)
    {
        x = rand() % 20;
        if(rand() & 1) x = -x;
        printf("%d ", x);
    }
    for(register int i = 1; i <= m; ++i)
    {
        ope = (rand());
        l = rand() % n + 1;
        r = rand() % n + 1;
        if(l < 0 || r < 0)
        {
            do{
                l = rand() % n + 1;
                r = rand() % n + 1;
            }while(l < 0 || r < 0);
        }
        if(l > r) x = l, l = r, r = x;
        x = rand() % 200 + 1;
        if(rand() & 1) x = -x;
        if(!ope) printf("1 %d %d %d\n", l, r, x < 0 ? -x : x);
        else printf("2 %d %d %d\n", l, r, x);
    }
    return 0;
}

//BF
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#define int long long
using namespace std;

inline int min(int &a, int b){return a < b ? a : b;}
inline int max(int &a, int b){return a > b ? a : b;}
inline int read()
{
    int x = 0; char c; bool f = false;
    while(!isdigit(c = getchar()))
        if(c == '-') f = true;
    do{
        x = (x << 1) + (x << 3) + (c ^ 48);
    }while(isdigit(c = getchar()));
    return f ? -x : x;
}

int top = 0, stk[20];
inline void write(int x)
{
    if(x < 0) putchar('-'), x = -x;
    do{
        stk[++top] = x % 10;
        x /= 10;
    }while(x);
    for(register int i = top; i; --i)
        putchar(stk[i] | 48);
    putchar('\n'); top = 0;
    return ;
}

int n, m, ope, l, r, x;
int sz[100010], tmp[100010];
#undef int
int main()
{
    freopen("aaa.txt", "r", stdin);
    freopen("ccc.txt", "w", stdout);
    n = read(); m = read();
    for(register int i = 1; i <= n; ++i)
        sz[i] = read();
    for(register int i = 1; i <= m; ++i)
    {
        ope = read(); l = read(); r = read(); x = read();
        if(ope == 2)
        {
            for(register int j = l; j <= r; ++j)
            sz[j] += x;
        }
        else
        {
            if(x < 1 || x > r - l + 1)
            {
                printf("-1\n");
                continue;
            }
            for(register int j = l; j <= r; ++j)
            tmp[j - l + 1] = sz[j];
            sort(tmp + 1, tmp + r - l + 2);
            printf("%lld\n", tmp[x]);
        }
    }
    return 0;
}

//automatic comparing
//注意若数据过大暴力跑得很慢，请更改sleep内参数
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <unistd.h>
using namespace std;

inline int read()
{
    int x = 0; char c;
    while(!isdigit(c = getchar()));
    do{
        x = (x << 1) + (x << 3) + (c ^ 48);
    }while(isdigit(c = getchar()));
    return x;
}

int top = 0, stk[20];
inline void write(int x)
{
    do{
        stk[++top] = x % 10;
        x /= 10;
    }while(x);
    for(register int i = top; i; --i)
        putchar(stk[i] | 48);
    putchar('\n'); top = 0;
    return ;
}

int tot = 0;
int main()
{
    while(1)
    {
        system("./a"); sleep(0.5);
        system("./b"); sleep(0.5);
        system("./c"); sleep(0.5);
        printf("Test case %d\n:", ++tot);
        if(system("diff bbb.txt ccc.txt"))
        {
            printf("Wrong Answer.See the error log.\n");
            return 0;
        }
        else printf("Accepted.\n");
    }
    return 0;
}

写在最后

在正确性上，我几乎调了一天才保证了如此工业化代码的正确性。
在常数上，我又不得不放弃了之前这一版构想，之后用几乎相同的时间又写了第二版、第三版、第四版，最终改成了现在的模样。
衷心希望看到这篇博客的人能避掉这些坑，减少卡常的尝试。

Code\space Time

警告：代码中可能含有巨幅代码块、针对不同数据具有适应性的相同功能函数、压行等内容，码长约 7.7KB，314 行，请谨慎浏览。

#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;

inline int min(int &a, int &b){return a < b ? a : b;}
inline int max(int &a, int &b){return a > b ? a : b;}
const int SIZE = 524288;
namespace Fread 
{
    static char buf[SIZE], *p1 = buf, *p2 = buf;
    inline char getchar()
    {return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++);}
}
namespace Fwrite
{
    static char buf[SIZE], *S = buf, *T = buf + SIZE;
    inline void flush(){fwrite(buf, 1, S - buf, stdout), S = buf;}
    struct NTR{~NTR(){flush();}}ztr;
    inline void putchar(char c)
    {
        *S++ = c;
        if(S == T) flush();
    }
}
#ifdef ONLINE_JUDGE
    #define getchar Fread::getchar
    #define putchar Fwrite::putchar
#endif
namespace Fastio
{
    struct Reader
    {
        inline Reader & operator >> (int &x)
        {
            x = 0; static char c = getchar(); bool f = false;
            while(!isdigit(c))
            {
                if(c == '-') f = true;
                c = getchar();
            } 
            while(isdigit(c))
            {
                x = (x << 1) + (x << 3) + (c ^ 48);
                c = getchar();
            }
            if(f) x = -x; return *this;
        }
        inline Reader & operator >> (long long &x)
        {
            x = 0; static char c = getchar(); bool f = false;
            while(!isdigit(c))
            {
                if(c == '-') f = true;
                c = getchar();
            } 
            while(isdigit(c))
            {
                x = (x << 1) + (x << 3) + (c ^ 48);
                c = getchar();
            }
            if(f) x = -x; return *this;
        }
        Reader(){}
    }cin;

    struct Writer
    {
        inline Writer & operator << (long long x)
        {
            if(x == 0) return putchar(48), *this;
            if(x < 0) putchar('-'), x = -x;
            static int sta[45], top = 0;
            while(x) sta[++top] = x % 10, x /= 10;
            while(top) putchar(sta[top] + 48), --top;
            return *this;
        }
        inline Writer & operator << (int x)
        {
            if(x == 0) return putchar(48), *this;
            if(x < 0) putchar('-'), x = -x;
            static int sta[45], top = 0;
            while(x) sta[++top] = x % 10, x /= 10;
            while(top) putchar(sta[top] + 48), --top;
            return *this;
        }
        inline Writer & operator << (char c)
        {
            putchar(c);
            return *this;
        }
        Writer(){}
    }cout;
}
const char endl = '\n'; 
#define cin  Fastio :: cin
#define cout Fastio :: cout

const int shift = 100008;
int n, m, ope, l, r, k, sq, bl, br;
int tp1, tp2, a1, a2, a3;
int len[2000], st[2000], ed[2000], bel[100010];
int rec1[5000], rec2[5000], rec3[5000], tag[2000];
const long long maximum = 1LL << 62LL;
long long kl, kr, mid, ans;
long long sz[100010], rebuild[100010], maxn[2000], minn[2000];

inline bool cmp(int a, int b)
{
    int k1 = bel[a], k2 = bel[b];
    return sz[a] + tag[k1] < sz[b] + tag[k2];
}
inline bool pmc(int a, int b)
{
    int k1 = bel[a], k2 = bel[b];
    return sz[a] + tag[k1] >= sz[b] + tag[k2];
}

inline void preblocks()
{
    sq = 650; bl = n / sq;
    for(register int i = 1; i < sq; ++i)
    {
        st[i] = ed[i - 1] + 1;
        ed[i] = st[i] + bl - 1; len[i] = bl;
        for(register int j = st[i]; j <= ed[i]; ++j)
        {
            cin >> sz[j];
            bel[j] = i;
            rebuild[j] = j;
        }
        sort(rebuild + st[i], rebuild + ed[i] + 1, cmp);
        minn[i] = sz[rebuild[st[i]]];
        maxn[i] = sz[rebuild[ed[i]]];
    }
    st[sq] = ed[sq - 1] + 1; ed[sq] = n;
    for(register int i = st[sq]; i <= n; ++i)
    {
        cin >> sz[i];
        bel[i] = sq;
        rebuild[i] = i;
    }
    sort(rebuild + st[sq], rebuild + n + 1, cmp);
    minn[sq] = sz[rebuild[st[sq]]];
    maxn[sq] = sz[rebuild[n]];
    len[sq] = n - st[sq] + 1; return ;
}

inline void mergesort(int st, int goal[])
{
    a1 = a2 = 1; a3 = st;
    while(a1 <= tp1 && a2 <= tp2)
    {
        if(cmp(rec1[a1], rec2[a2])) goal[a3++] = rec1[a1++];
        else goal[a3++] = rec2[a2++];
    }
    while(a1 <= tp1) goal[a3++] = rec1[a1++];
    while(a2 <= tp2) goal[a3++] = rec2[a2++];
    --a3; return ;
}

inline void mergesort(int st, long long goal[])
{
    a1 = a2 = 1; a3 = st;
    while(a1 <= tp1 && a2 <= tp2)
    {
        if(cmp(rec1[a1], rec2[a2])) goal[a3++] = rec1[a1++];
        else goal[a3++] = rec2[a2++];
    }
    while(a1 <= tp1) goal[a3++] = rec1[a1++];
    while(a2 <= tp2) goal[a3++] = rec2[a2++];
    --a3; return ;
}

inline void restart(int b, int lb, int rb, int k)
{
    tp1 = tp2 = 0;
    for(register int i = st[b]; i <= ed[b]; ++i)
    {
        int rk = rebuild[i];
        if(rk >= lb && rk <= rb)
        {
            sz[rk] += k;
            rec1[++tp1] = rk;
        }
        else rec2[++tp2] = rk;
    }
    mergesort(st[b], rebuild);
    minn[b] = sz[rebuild[st[b]]] + tag[b];
    maxn[b] = sz[rebuild[ed[b]]] + tag[b];
    return ;
}

inline void modify(int l, int r, int k)
{
    bl = bel[l]; br = bel[r];
    if(bl == br) restart(bl, l, r, k);
    else
    {
        if(l == st[bl]) --bl;
        else restart(bl, l, ed[bl], k);
        if(r == ed[br]) ++br;
        else restart(br, st[br], r, k);
        for(register int i = bl + 1; i < br; ++i)
        tag[i] += k, maxn[i] += k, minn[i] += k;
    }
    return ;
}

inline bool check(int bl, int br, int mid, int k)
{
    int res = 0;
    for(register int i = bl + 1; i < br; ++i)
    {
        if(mid < minn[i]) continue;
        else if(mid >= maxn[i]) res += len[i];
        else
        {
            sz[shift] = mid;
            res += upper_bound(rebuild + st[i], rebuild + ed[i] + 1, shift, cmp) - rebuild - st[i];
        }
        if(res >= k) return true;
    }
    if(a3)
    {
        sz[shift] = mid;
        if(cmp(shift, rec3[1])) ;
        else if(pmc(shift, rec3[a3])) res += a3;
        else res += upper_bound(rec3 + 1, rec3 + a3 + 1, shift, cmp) - rec3 - 1;
    }
    return res >= k;
}

inline void query(int l, int r, int k)
{
    if(k < 1 || k > r - l + 1)
    {
        cout << -1 << endl;
        return ;
    }
    bl = bel[l]; br = bel[r]; tp1 = tp2 = 0;
    kl = maximum; kr = -maximum;
    if(bl == br)
    {
        for(register int i = l; i <= r; ++i)
            rec1[++tp1] = sz[i] + tag[bl];
        sort(rec1 + 1, rec1 + tp1 + 1);
        cout << (long long)rec1[k] << endl;
    }
    else
    {
        if(l == st[bl]) --bl;
        else
        {
            for(register int i = st[bl]; i <= ed[bl]; ++i)
            {
                int rk = rebuild[i];
                if(rk >= l) rec1[++tp1] = rk;
            }
        }
        if(r == ed[br]) ++br;
        else
        {
            for(register int i = st[br]; i <= ed[br]; ++i)
            {
                int rk = rebuild[i];
                if(rk <= r) rec2[++tp2] = rk;
            }
        }
        mergesort(1, rec3);
        if(a3)
        {
            kl = sz[rec3[1]] + tag[bel[rec3[1]]];
            kr = sz[rec3[a3]] + tag[bel[rec3[a3]]];
        }
        for(register int i = bl + 1; i < br; ++i)
        {
            kl = min(kl, minn[i]);
            kr = max(kr, maxn[i]);
        }
        if(k == 1)
        {
            cout << kl << endl;
            return ;
        }
        if(k == r - l + 1)
        {
            cout<< kr << endl;
            return ;
        }
        while(kl <= kr)
        {
            mid = kl + kr >> 1;
            if(check(bl, br, mid, k))
                ans = mid, kr = mid - 1;
            else kl = mid + 1;
        }
        cout << ans << endl;
    }
    return ;
}
#define debug true
#undef debug
int main()
{
    #ifdef debug
        freopen("aaa.txt", "r", stdin);
        freopen("bbb.txt", "w", stdout);
    #endif
    cin >> n >> m; preblocks();
    for(register int i = 1; i <= m; ++i)
    {
        cin >> ope >> l >> r >> k;
        if(ope == 2) modify(l, r, k);
        else query(l, r, k);
    }
    return 0;
}