题解：P11754 [COCI 2024/2025 #5] 绘图 / Crtež

· · 题解

思路

我在做完这道题后想出了一个更好理解的推结论过程，所以这里附出更简单的版本。至于更丑陋的考场版本有兴趣可以看看。

答案显然是每一段连续的 0 的情况相乘后的答案，因此先只考虑连续的 0。因为显然对一个位置进行操作 2 后，直到其左边第一个非 0 数，之间的所有数全部会被染成一种颜色，不好讨论，考虑从左到右来进行操作。

随后，不难发现，对于一个已经被选择为 0 的点，即使这个点被后面的一次操作 2 染上色了，这也仍然只是一种情况，可推出对于每一个点，有进行操作 1，进行操作 2，以及不操作三种情况，可得如果有 n 个连续的 0，总情况为 3^n。

然后我们的问题就变成了如何求出每次询问里序列 a 中 0 的数量。不难想到离散化后使用线段树维护即可，因为不是此题重点就不细说了。

时间复杂度 O(q\log n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll (k<<1)
#define rr (k<<1|1)
#define mid ((l+r)>>1)
const int mod = 1e9 + 7;
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
struct que {
    int l, r;
} p[1000005];
map <int, int> mp;
int num[1000005], cnt, ls[1000005], un;
struct tree {
    int l, r, lazy, num, sum;
} t[4000005];
int n, q;
inline void pushup(int k) {
    t[k].num = t[ll].num + t[rr].num;
}
void build(int k, int l, int r) {
    t[k].l = l;
    t[k].r = r;
    if (l == r) {
        t[k].num = num[l];
        t[k].sum = num[l];
        return ;
    }
    build(ll, l, mid);
    build(rr, mid + 1, r);
    pushup(k);
    t[k].sum = t[ll].sum + t[rr].sum;
    return ;
}
inline void pushdown(int k) {
    if (t[k].lazy) {
        t[ll].lazy ^= 1;
        t[rr].lazy ^= 1;
        t[ll].num = t[ll].sum - t[ll].num;
        t[rr].num = t[rr].sum - t[rr].num;
        t[k].lazy = 0;
    }
}
void update(int k, int l, int r) {
    if (t[k].r < l || t[k].l > r) return ;
    if (t[k].r <= r && t[k].l >= l) {
        t[k].lazy ^= 1;
        t[k].num = t[k].sum - t[k].num;
        return ;
    }
    pushdown(k);
    update(ll, l, r);
    update(rr, l, r);
    pushup(k);
    return ;
}
signed main() {
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        cin >> p[i].l >> p[i].r;
        ls[i * 2 - 1] = p[i].l, ls[i * 2] = p[i].r;
    }
    sort(ls + 1, ls + q * 2 + 1);
    un = unique(ls + 1, ls + q * 2 + 1) - ls - 1;
    for (int i = 1; i <= un; i++) {
        num[i * 2 - 1] = ls[i] - ls[i - 1] - 1;
        num[i * 2] = 1;
        mp[ls[i]] = i * 2;
    }
    num[un * 2 + 1] = n - ls[un];//num 数组保存的是这一个新点存储了几个点 
    build(1, 1, un * 2 + 1); 
    for (int i = 1; i <= q; i++) {
        p[i].l = mp[p[i].l];
        p[i].r = mp[p[i].r];
        update(1, p[i].l, p[i].r);
        cout << qpow(3, t[1].num) % mod << "\n";
    }
    return 0;
//}

关于更多

这里附考场思路：

首先只考虑对一段连续的 0 做操作 2 的情况。操作 2 也就是把从一个点到其左边第一个非 0 数前的所有数染上同一个颜色。接下来，我们对于每个数就有了“染了色”和“未染色”两种情况。根据题面给出的“等价”的概念，我们不用在意这个染色具体是哪种颜色，只需要知道这一段的颜色与其他所有颜色都不同就好了。

接下来对这个情况进行简单的讨论：

接着根据这个规律，显然可得有 n 个 0 时，总情况有 2^n 种。

接下来，我们加入第 1 种操作。可以将第 1 种操作看作是把一段连续的 0 拆成几个部分，显然若添加了 x 个 -1，则总情况为 2^{n-x} 种。可得总情况为：

\sum^n_{i=0} \binom{n}{i}\times 2^i

根据牛顿二项式定理（或者打一点表出来看）可得此式为 3^n。随后可得结论。