CSP2020-S 题解

    CSP2020-S 题解

    T1. 儒略日

    LOJ 3379

    Solution

    首先为了方便讨论,先令 r←r+1r \gets r + 1,这样的话,求的就是 ” 第几天 “ 而不是 ” 经过了几天 “ 了。

    显然可以考虑把 “ 时间轴 “ 分成一些 “ 时间段 “,在每一段中根据 “ 日期变化的周期性 “ 计算答案。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int Q;
    
    int c[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
    
    int onelimit = 1721424;
    int twolimit = 2299161;
    
    bool isrn(long long x) {
        if (x % 4 != 0 || (x % 100 == 0 && x % 400 != 0)) return false;
        return true;
    }
    
    pair<int, int> turn(int x, bool rn) {
        int cnt = 0;
        for (int i = 1; i <= 12; i ++) {
            int delta = c[i];
            if (i == 2 && rn) delta ++;
            if (x <= cnt + delta) return make_pair(x - cnt, i);
            else cnt += delta;
        }
    }
    
    long long r;
    int year;
    long long cnt;
    
    void work1() {
        if (r <= 366) {
            pair<int, int> ans = turn(r, 1);
            cout << ans.first << " " << ans.second << " " << 4713 << " BC" << endl;
    
            return;
        }
    
        r -= 366;
    
        cnt = (r - 1) / 1461 + 1;
        r -= (cnt - 1) * 1461;
        year = 4712 - (cnt - 1) * 4;
    
        cnt = (r - 1) / 365 + 1;
        if (r == 1461) cnt = 4;
        r -= (cnt - 1) * 365;
        year -= cnt - 1;
    
        pair<int, int> ans = turn(r, year % 4 == 1 ? 1 : 0);
        cout << ans.first << " " << ans.second << " " << year << " BC" << endl;
    }
    
    void work2() {
        r -= onelimit;
    
        cnt = (r - 1) / 1461 + 1;
        r -= (cnt - 1) * 1461;
        year = 1 + (cnt - 1) * 4;
    
        cnt = (r - 1) / 365 + 1;
        if (r == 1461) cnt = 4;
        r -= (cnt - 1) * 365;
        year += cnt - 1;
    
        pair<int, int> ans = turn(r, year % 4 == 0 ? 1 : 0);
        cout << ans.first << " " << ans.second << " " << year << endl;
    }
    
    void work3() {
        r -= twolimit;
    
        if (r <= 78) {
            if (r <= 17)
                cout << 14 + r << " " << 10 << " " << 1582 << endl;
            else if (r <= 47)
                cout << r - 17 << " " << 11 << " " << 1582 << endl;
            else
                cout << r - 47 << " " << 12 << " " << 1582 << endl;
            return;
        }
    
        r -= 78;
    
        if (r <= 731) {
            cnt = (r - 1) / 365 + 1;
            if (r == 731) cnt = 2;
            r -= (cnt - 1) * 365;
            year = 1582 + cnt;
    
            pair<int, int> ans = turn(r, cnt == 2 ? 1 : 0);
            cout << ans.first << " " << ans.second << " " << year << endl;
    
            return;
        }
    
        r -= 731;
    
        if (r <= 5844) {
            cnt = (r - 1) / 1461 + 1;
            r -= (cnt - 1) * 1461;
            year = 1585 + (cnt - 1) * 4;
    
            cnt = (r - 1) / 365 + 1;
            if (r == 1461) cnt = 4;
            r -= (cnt - 1) * 365;
            year += cnt - 1;
    
            pair<int, int> ans = turn(r, cnt == 4 ? 1 : 0);
            cout << ans.first << " " << ans.second << " " << year << endl;
    
            return;
        }
    
        r -= 5844;
    
        cnt = (r - 1) / 146097 + 1;
        r -= (cnt - 1) * 146097;
        year = 1601 + (cnt - 1) * 400;
    
        cnt = (r - 1) / 36524 + 1;
        if (r == 146097) cnt = 4;
        r -= (cnt - 1) * 36524;
        year += (cnt - 1) * 100;
    
        if (cnt == 4) {
            cnt = (r - 1) / 1461 + 1;
            if (r == 36525) cnt = 25;
            r -= (cnt - 1) * 1461;
            year += (cnt - 1) * 4;
        } else {
            cnt = (r - 1) / 1461 + 1;
            r -= (cnt - 1) * 1461;
            year += (cnt - 1) * 4;
        }
    
        cnt = (r - 1) / 365 + 1;
        if (r == 1461) cnt = 4;
        r -= (cnt - 1) * 365;
        year += cnt - 1;
    
        pair<int, int> ans = turn(r, isrn(year));
        cout << ans.first << " " << ans.second << " " << year << endl;
    }
    
    void work() {
        scanf("%lld", &r);
        r ++;
    
        if (r <= onelimit)
            work1();
        else if (r <= twolimit)
            work2();
        else
            work3();
    }
    
    int main() {
        scanf("%d", &Q);
    
        while (Q --)    work();
    
        return 0;
    }

    但是这个做法比较 naive,有没有更给力点的?有没有更加短小精悍的?

    那当然还是有的:

    1. 对于 4713.1.1 BC→1600.12.314713.1.1 \ \text{BC} \to 1600.12.31 的每一个日期,可以通过 “ day by day “ 的方式将答案先预处理出来。
    2. 对于 1601.1.11601.1.1 及以后的每一个日期,可以通过 “ 日期变化的周期性 “ 来计算答案。

    这样子做会少讨论许多的情况,比较好写。

    T2. 动物园

    LOJ 3380

    Solution

    注意到对于所有的约束关系 (pi,qi)(p_i, q_i),所对应的 qiq_i 是互不相同的。

    那么,也就是说,如果我这里有一个动物编号,其中的第 ii 位存在约束关系,那我的第 ii 位就会固定的影响到清单中的若干位。

    约定变量:

    • matchj\text{match}_j:表示第 jj 位是否存在约束关系。
    • existj\text{exist}_j:表示是否存在一个 aia_i,满足 aia_i 的第 jj 位为 11。

    那么当我们新加进去一个动物时,考虑每一位的取值。
    显然第 jj 位填 00 是可以的,因为这样不可能会影响到清单。
    如果第 jj 位填 11,当且仅当满足以下 22 个条件之一:

    1. matchj=0\text{match}_j = 0。
    2. matchj=1∧existj=1\text{match}_j = 1 \land \text{exist}_j = 1。

    第一条显然。第二条指的是:虽然第 jj 位存在约束关系,但是已经存在一个动物编号影响到了清单,那么我第 jj 位填 11 也不会再次影响到清单了。

    记 “ 有多少位可以填 11 “ 的数量为 fre\text{fre},根据乘法原理,一共可以养 2fre2^\text{fre} 个动物。

    但是题目问的是 “ 还可以养多少个 “,可以证明,养过的 nn 个动物一定被包含在这 2fre2^\text{fre} 之内。

    故答案即为 2fre−n2^\text{fre} - n。

    这题数据范围比较刁钻,有几个 X 点:

    1. k == 64 && n == 0 && m == 0 :会爆 unsigned long long,需要特判,直接输出 2642^{64} 即可。
    2. fre == 64:使用 1ull << 64 时会爆炸,可以输出 (1ull << 63) - n + (1ull << 63)。
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1001000;
    
    int n, m, c, k;
    
    unsigned long long a[N];
    
    bool match[65];
    bool exist[65];
    
    int main() {
        scanf("%d%d%d%d", &n, &m, &c, &k);
    
        if (k == 64 && n == 0 && m == 0) {
            puts("18446744073709551616");
            return 0;
        }
    
        for (int i = 1; i <= n; i ++)
            scanf("%llu", &a[i]);
    
        for (int i = 1, p, q; i <= m; i ++) {
            scanf("%d%d", &p, &q);
            match[p] = 1;
        }
    
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j < k; j ++)
                if (a[i] >> j & 1) exist[j] = 1;
    
        int fre = 0;
        for (int j = 0; j < k; j ++)
            if (!(match[j] && !exist[j])) fre ++;
    
        if (fre == 64) {
            unsigned long long ans = 0;
            ans += (1ull << 63);
            ans -= n;
            ans += (1ull << 63);
            printf("%llu\n", ans);
        } else {
            printf("%llu\n", (1ull << fre) - n);
        }
    
        return 0;
    }

    T3. 函数调用

    LOJ 3381

    Solution

    不难看出,如果我把每个函数看成一个点。
    那么对于每个 Tj=3T_j = 3 的函数 jj,我让 jj 向 g1(j),g2(j),...,gCj(j)g_1^{(j)}, g_2^{(j)}, ..., g_{C_j}^{(j)} 连边的话,会得到一张 DAG。

    记 “ 调用函数 ii 会使全局乘多少倍 “ 为 muli\text{mul}_i,该数组可以在 DAG 上记忆化搜索求出。

    注意到影响到答案最后取值的操作只有 “ 单点加 “ 和 “ 全局乘 “ 两种操作。
    那么我可以尝试把最终序列上,第 ii 个位置上的数表示为下列该式的形式:

    ai×b+kia_i \times b + k_i

    其中:

    • aia_i 表示:初始序列中第 ii 个位置上的值。
    • bb 表示:所有操作结束后,” 全局乘 “ 的倍数。
    • kik_i 表示:所有 “ 单点加 “ 操作对第 ii 个位置的贡献。

    那现在关键是在于如何求出每个 kik_i。

    一个重要的思想是:如果我进行了一次 “ 值为 aa 的单点加 “,然后我进行了一次 “ 值为 bb 的全局乘 “,那么我可以看作是进行了 bb 次 “ 值为 aa 的单点加 “。

    记 “ 函数 ii 进行了多少次 “ 为 fif_i,对于每次调用,先在节点上打上标记,最后再用拓扑排序向下传递贡献。

    具体地,倒序处理每一个调用(因为只有时间更靠后的 “ 全局乘 “ 才能影响到 “ 单点加 “),假设说我这次要调用第 ii 个函数,那么:

    • 令 fi←fi+bf_i \gets f_i + b。
    • 令 b←b×mulib \gets b \times \text{mul}_i。

    然后考虑拓扑排序,假设说我这次要处理第 ii 个函数,那么:

    • 若 Ti=1T_i = 1,则令 kPi←kPi+Vi×fik_{P_i} \gets k_{P_i} + V_i \times f_i。
    • 若 Ti=2T_i = 2,则无视该操作。
    • 若 Ti=3T_i = 3,则倒序处理每一个调用,假设说我现在要将贡献传递给函数 jj,那么:
      • 令 fj←fj+fif_j \gets f_j + f_i。
      • 令 fi←fi×muljf_i \gets f_i \times \text{mul}_j。

    拓扑排序完直接输出 ai×b+kia_i \times b + k_i 即可。

    时间复杂度 O(n+m+Q)\mathcal{O}(n + m + Q)。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <vector>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 100100;
    const int mod = 998244353;
    
    int n;
    
    int a[N];
    
    int m;
    
    struct operation {
        int opt;
        int pos, val;
        vector<int> g;
    } T[N];
    
    int mul[N];
    
    void calc(int u) {
        if (mul[u] != -1) return;
    
        switch (T[u].opt) {
            case 1: {
                mul[u] = 1;
    
                break;
            }
    
            case 2: {
                mul[u] = T[u].val;
    
                break;
            }
    
            case 3: {
                mul[u] = 1;
                for (int i = 0; i < (int)T[u].g.size(); i ++) {
                    int v = T[u].g[i];
                    calc(v);
                    mul[u] = 1ll * mul[u] * mul[v] % mod;
                }
    
                break;
            }
        }
    }
    
    int Q;
    int idx[N];
    
    int b;
    int f[N];
    
    int deg[N];
    
    int k[N];
    
    void topsort() {
        queue<int> q;
    
        for (int i = 1; i <= m; i ++)
            if (deg[i] == 0) q.push(i);
    
        while (q.size()) {
            int u = q.front(); q.pop();
    
            switch (T[u].opt) {
                case 1: {
                    k[T[u].pos] = (k[T[u].pos] + 1ll * f[u] * T[u].val) % mod; 
    
                    break;
                }
    
                case 2: {
                    break;
                }
    
                case 3: {
                    for (int j = T[u].g.size() - 1; j >= 0; j --) {
                        int v = T[u].g[j];
                        f[v] = (f[v] + f[u]) % mod;
                        f[u] = 1ll * f[u] * mul[v] % mod;
                        if (-- deg[v] == 0) q.push(v);
                    }
    
                    break;
                }
            }
        }
    }
    
    int main() {
        n = read();
    
        for (int i = 1; i <= n; i ++)
            a[i] = read();
    
        m = read();
    
        for (int i = 1; i <= m; i ++) {
            T[i].opt = read();
    
            switch (T[i].opt) {
                case 1: {
                    T[i].pos = read(), T[i].val = read();
    
                    break;
                }
    
                case 2: {
                    T[i].val = read();
    
                    break;
                }
    
                case 3: {
                    int C = read();
                    for (int j = 1; j <= C; j ++) {
                        int x = read();
                        T[i].g.push_back(x);
                    }
    
                    break;
                }
            } 
        }
    
        memset(mul, -1, sizeof(mul));
        for (int i = 1; i <= m; i ++)
            if (mul[i] == -1) calc(i); 
    
        Q = read();
    
        for (int i = 1; i <= Q; i ++)
            idx[i] = read();
    
        b = 1;
        for (int i = Q; i >= 1; i --) {
            switch (T[idx[i]].opt) {
                case 1: {
                    f[idx[i]] = (f[idx[i]] + b) % mod;
    
                    break;
                }
    
                case 2: {
                    b = 1ll * b * T[idx[i]].val % mod;
    
                    break;
                }
    
                case 3: {
                    f[idx[i]] = (f[idx[i]] + b) % mod;
                    b = 1ll * b * mul[idx[i]] % mod;
    
                    break;
                }
            }
        }
    
        for (int u = 1; u <= m; u ++) {
            if (T[u].opt != 3) continue;
    
            for (int j = 0; j < (int)T[u].g.size(); j ++) {
                int v = T[u].g[j];
                deg[v] ++;
            } 
        }
    
        topsort();
    
        for (int i = 1; i <= n; i ++)
            printf("%d ", (1ll * a[i] * b + k[i]) % mod);
        puts("");
    
        return 0;
    }

    T4. 贪吃蛇

    LOJ 3382

    Solution

    算法一

    部分分:n≤5×104n \leq 5 \times 10^4。

    先是一个引理 1:

    引理 1

    那么我们将蛇分成 “ 没有被操作过 “ 和 “ 被操作过 “ 两类。 现最强蛇操作后成为最弱蛇的局面之前,捕食后产生的蛇的强度是单调递减的。

    即,捕食后产生的蛇中,先产生的蛇强于后产生的蛇。

    证明

    在保证没有出现最强蛇操作后成为最弱蛇的情况下。显然,当前的最强蛇没有上次操作时的最强蛇强,当前的最弱蛇也没有上次操作时的最弱蛇弱。根据不等式基本性质可知,当前产生的新蛇的实力值一定不大于上次操作时产生的蛇的实力值。

    又由于给出来的实力值序列 {an}\{a_n\} 满足 a1≤a2≤⋯≤an−1≤ana_1 \leq a_2 \leq \cdots \leq a_{n - 1} \leq a_{n}。

    那么我们将蛇分成 “ 没有被操作过 “ 和 “ 被操作过 “ 两类。

    将第一类蛇取出来的顺序肯定是按照 n,n−1,⋯n, n - 1, \cdots 这样编号递减的顺序取出来的。

    由于将第一类蛇取出来后就会变成第二类蛇,所以第二类蛇产生的顺序也是按照 n,n−1,⋯n, n - 1, \cdots 这样编号递减的顺序产生的,由于捕食后产生的蛇的实力值是单调递减的,所以将第二类蛇取出来的顺序自然也是按照 n,n−1,⋯n, n - 1, \cdots 这样编号递减的顺序取出来的。

    所以,即使是在权值相等的情况下,当前产生的新蛇的编号也一定不大于上次操作时产生的蛇的编号。

    故当前产生的新蛇的强度一定不大于上次操作时产生的蛇的强度,引理 1 得证。

    又是一个引理 2:

    引理 2

    在出现最强蛇操作后成为最弱蛇的局面之前,若一个最强蛇操作后不会成为最弱蛇,那么这条最强蛇一定会无脑进行该次操作。

    证明

    设当前有一条最强蛇 AA。

    (1):如果这个最强蛇 AA 操作后还是最强蛇。那当然吃就完事了。

    (2):如果这个最强蛇 AA 操作后会有另一条蛇 BB 取代了它最强的位置。由于我们假设的大前提,蛇 AA 不会成为这次蛇 BB 操作的目标。根据引理 1,蛇 BB 进行该次操作后,强度一定不如操作过后的蛇 AA。故蛇 BB 成为狩猎对象的优先级一定高于蛇 AA。在题目给定的 “ 所有蛇均采取最优策略 “ 的博弈背景下,蛇 BB 会在不让自己死的前提下采取最优策略,那么蛇 AA 肯定也不会死。

    综上所述,引理 2 得证。

    有了引理 1 和引理 2,可以考虑做一些事情。

    注意到,不论蛇是怎么进行选择,每一轮中的捕食者与被捕食者都是不会发生变化的。

    根据引理 2,在出现最强蛇操作后成为最弱蛇的局面之前,所有的局面都可以无脑的进行下去。

    那重点就在于,第一次出现最强蛇操作后成为最弱蛇的局面。
    现在要讨论该操作是否进行,就出现了蛇之间的千层博弈:

    • 当前有蛇 A,BA, B。

      • 蛇 AA 操作后成为了最弱蛇。
      • 蛇 BB 吃了蛇 AA 后不会成为最弱蛇。

      考虑到蛇 AA 进行了该次操作后会被蛇 BB 无脑吃掉,那么蛇 AA 不该进行这次操作。

    • 当前有蛇 A,B,CA, B, C。

      • 蛇 AA 操作后成为了最弱蛇。
      • 蛇 BB 吃了蛇 AA 后成为了最弱蛇。
      • 蛇 CC 吃了蛇 BB 后不会成为最弱蛇。

      考虑到蛇 BB 吃了蛇 AA 后自身难保,那么蛇 AA 就会预判蛇 BB 不敢吃它,那么蛇 AA 就可以放心进行该次操作。

    • ……

    亦可以归纳证明,当第一次出现最强蛇操作后成为最弱蛇的局面时,该次操作是否进行,与 “ 最强蛇操作后成为最弱蛇 “ 这样的局面连续进行了多少次的奇偶性有关。若为偶数,那么该次操作可以放心进行;若为奇数,那么该次操作便不该进行。

    讨论到这里,本题就有了一个初步的做法,分成 Part 1 与 Part 2:

    • 在 Part 1 中:模拟操作,若第 ii 步进行后最强蛇会成为最弱蛇,则进入 Part 2。

    • 在 Part 2 中:模拟操作,统计 “ 最强蛇操作后成为最弱蛇 “ 这样的局面连续进行了多少次。
      若为偶数,则答案为 n−in - i;若为奇数,则答案为 n−i+1n - i + 1。

    使用线段树或平衡树随意维护一下蛇,回答单次询问的时间复杂度是 O(nlog⁡n)\mathcal{O}(n \log n) 的,期望得分 7070。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 1001000;
    
    int T;
    
    int n, m;
    struct Node {
        int val;
        int id;
        Node() { val = id = 0; }
        Node(int X, int Y) : val(X), id(Y) {}
    } a[N], zero = (Node) { 0, 0 };
    
    bool operator < (Node a, Node b) {
        if (a.val != b.val) return a.val < b.val;
        return a.id < b.id;
    }
    
    bool operator == (Node a, Node b) {
        return a.id == b.id;
    }
    
    bool operator != (Node a, Node b) {
        return a.id != b.id;
    }
    
    bool operator > (Node a, Node b) {
        if (a.val != b.val) return a.val > b.val;
        return a.id > b.id;
    }
    
    void makedata(int id) {
        if (id == 1) {
            n = read();
            for (int i = 1; i <= n; i ++) {
                a[i].val = read();
                a[i].id = i;
            }
        } else {
            m = read();
            for (int i = 1; i <= m; i ++) {
                int x = read(), y = read();
                a[x].val = y;
            }
        }
    }
    
    struct SegmentTree {
        int l, r;
        Node max, min;
    } t[N * 4];
    
    void upd(int p) {
        t[p].max = zero;
        if (t[p * 2].max != zero && t[p * 2].max > t[p].max) t[p].max = t[p * 2].max;
        if (t[p * 2 + 1].max != zero && t[p * 2 + 1].max > t[p].max) t[p].max = t[p * 2 + 1].max;
    
        t[p].min = (Node) { 0x3f3f3f3f, n + 1 };
        if (t[p * 2].min != zero && t[p * 2].min < t[p].min) t[p].min = t[p * 2].min;
        if (t[p * 2 + 1].min != zero && t[p * 2 + 1].min < t[p].min) t[p].min = t[p * 2 + 1].min;
    }
    
    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) {
            t[p].max = t[p].min = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
        upd(p);
    }
    
    void change(int p, int delta, Node val) {
        if (t[p].l == t[p].r) {
            t[p].max = t[p].min = val;
            return;
        }
        int mid = (t[p].l + t[p].r) >> 1;
        if (delta <= mid)
            change(p * 2, delta, val);
        else
            change(p * 2 + 1, delta, val);
        upd(p);
    }
    
    void work() {
        build(1, 1, n);
    
        int now = 1;
        for (; now < n; now ++) {
            if (now == n - 1) break;
    
            Node Max = t[1].max, Min = t[1].min;
    
            change(1, Min.id, zero);
            change(1, Max.id, zero);
    
            Node G = (Node) { Max.val - Min.val, Max.id };
    
            if (G < t[1].min) {
                change(1, Max.id, Max);
                change(1, Min.id, Min);
                break;
            } else {
                change(1, G.id, G);
            }
        }
    
        if (now == n - 1)  {
            puts("1");
            return;
        }
    
        int ans = n - now + 1;
        int round = 0;
    
        for (; now < n; now ++) {
            round ++;
    
            if (now == n - 1) {
                round ++;
                break;
            }
    
            Node Max = t[1].max, Min = t[1].min;
    
            change(1, Min.id, zero);
            change(1, Max.id, zero);
    
            Node G = (Node) { Max.val - Min.val, Max.id };
    
            if (G < t[1].min) {
                change(1, G.id, G);
            } else {
                round --;
                break;
            }
        }
    
        if (round % 2 == 0) ans --;
    
        printf("%d\n", ans);
    }
    
    int main() {
        T = read();
    
        for (int i = 1; i <= T; i ++) {
            makedata(i);
            work();
        }
    
        return 0;
    }

    算法二

    从数据范围中亦可猜得标算是一个线性的做法。从输入格式中亦可猜得标算充分利用了 {an}\{a_n\} 的单调性,不然时间复杂度的瓶颈就会在排序上。

    优化方式便是类似 「NOIP2016 提高组」蚯蚓 中的利用数据独特的单调性,配合队列来维护最值的方法。

    具体的,开两个队列 Q1,Q2\mathtt{Q_1}, \mathtt{Q_2}。其中 Q1\mathtt{Q_1} 维护的是 “ 没有被操作过 “ 的蛇。Q2\mathtt{Q_2} 维护的是 “ 被操作过 “ 的蛇。且 Q1,Q2\mathtt{Q_1}, \mathtt{Q_2} 中的蛇均按强度递减的顺序存放。

    根据定义,最强蛇便是 Q1,Q2\mathtt{Q_1}, \mathtt{Q_2} 中队首中的较大值,最弱蛇便是 Q1,Q2\mathtt{Q_1}, \mathtt{Q_2} 中队尾中的较小值。

    相较于算法一中,不同的地方在于:

    • 在 Part 1 中:我们每次取出最强蛇与最弱蛇,然后进行该次操作,新产生的蛇直接放到 Q2\mathtt{Q_2} 的队尾即可,根据引理 1,不失单调性。

    • 在 Part 2 中:我们每次取出最强蛇与最弱蛇,先是判断该次操作后最强蛇是否会成为最弱蛇,若最强蛇会成为最弱蛇,那么将新产生的蛇直接放到 Q2\mathtt{Q_2} 的队尾即可,根据最弱蛇的定义,不失单调性。

    这样就可以使用队列来维护蛇了,回答单次询问的时间复杂度是 O(n)\mathcal{O}(n) 的,十分优秀。

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <deque>
    
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char s = getchar();
        while (s < '0' || s > '9') {  s = getchar(); }
        while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
        return x * f;
    }
    
    const int N = 1000100;
    
    int T;
    
    int n, m;
    struct Node {
        int val;
        int id;
        Node() { val = id = 0; }
        Node(int X, int Y) : val(X), id(Y) {}
    } a[N];
    
    bool operator < (Node a, Node b) {
        if (a.val != b.val) return a.val < b.val;
        return a.id < b.id;
    }
    
    bool operator == (Node a, Node b) {
        return a.id == b.id;
    }
    
    bool operator > (Node a, Node b) {
        if (a.val != b.val) return a.val > b.val;
        return a.id > b.id;
    }
    
    void makedata(int id) {
        if (id == 1) {
            n = read();
            for (int i = 1; i <= n; i ++) {
                a[i].val = read();
                a[i].id = i;
            }
        } else {
            m = read();
            for (int i = 1; i <= m; i ++) {
                int x = read(), y = read();
                a[x].val = y;
            }
        }
    }
    
    deque<Node> p, q;
    
    int GetMax() {
        int id = 0; Node val = (Node) { -0x3f3f3f3f, 0 };
        if (p.size() && p.front() > val) id = 1, val = p.front();
        if (q.size() && q.front() > val) id = 2, val = q.front();
        return id;
    }
    
    int GetMin() {
        int id = 0; Node val = (Node) { 0x3f3f3f3f, n + 1 };
        if (p.size() && p.back() < val) id = 1, val = p.back();
        if (q.size() && q.back() < val) id = 2, val = q.back();
        return id;
    }
    
    void work() {
        while (p.size()) p.pop_back();
        while (q.size()) q.pop_back();
    
        for (int i = n; i >= 1; i --)
            p.push_back(a[i]);
    
        int now = 1;
    
        for (; now < n; now ++) {
            if (now == n - 1) break;
    
            int Max = GetMax(), Min = GetMin();
            Node X, Y;
    
            if (Max == 1) X = p.front();
            if (Max == 2) X = q.front();
    
            if (Min == 1) Y = p.back();
            if (Min == 2) Y = q.back();
    
            Node G;
            G.val = X.val - Y.val;
            G.id = X.id;
    
            if (X == Y) {
                if (Max == 1) p.pop_front();
                if (Max == 2) q.pop_front();
            } else {
                if (Max == 1) p.pop_front();
                if (Max == 2) q.pop_front();
    
                if (Min == 1) p.pop_back();
                if (Min == 2) q.pop_back();
            }
    
            int id = GetMin();
            Node cur;
    
            if (id == 1) cur = p.back();
            if (id == 2) cur = q.back();
    
            if (G < cur) {
                if (X == Y) {
                    if (Max == 1) p.push_front(X);
                    if (Max == 2) q.push_front(X);
                } else {
                    if (Max == 1) p.push_front(X);
                    if (Max == 2) q.push_front(X);
    
                    if (Min == 1) p.push_back(Y);
                    if (Min == 2) q.push_back(Y);
                }
                break;
            } else {
                q.push_back(G);
            }
        }
    
        if (now == n - 1) {
            puts("1");
            return;
        }
    
        int ans = n - now + 1;
        int round = 0;
    
        for (; now < n; now ++) {
            round ++;
    
            if (now == n - 1) {
                round ++;
                break;
            }
    
            int Max = GetMax(), Min = GetMin();
            Node X, Y;
    
            if (Max == 1) X = p.front();
            if (Max == 2) X = q.front();
    
            if (Min == 1) Y = p.back();
            if (Min == 2) Y = q.back();
    
            Node G;
            G.val = X.val - Y.val;
            G.id = X.id;
    
            if (X == Y) {
                if (Max == 1) p.pop_front();
                if (Max == 2) q.pop_front();
            } else {
                if (Max == 1) p.pop_front();
                if (Max == 2) q.pop_front();
    
                if (Min == 1) p.pop_back();
                if (Min == 2) q.pop_back();
            }
    
            int id = GetMin();
            Node cur;
    
            if (id == 1) cur = p.back();
            if (id == 2) cur = q.back();
    
            if (G < cur) {
                q.push_back(G);
            } else {
                round --;
                break;
            }
        }
    
        if (round % 2 == 0) ans --;
    
        printf("%d\n", ans);
    }
    
    int main() {
        T = read();
    
        for (int i = 1; i <= T; i ++) {
            makedata(i);
            work();
        }
    
        return 0;
    }