题解 P4340 【[SHOI2016]随机序列】

浮尘ii · 2019-03-19 17:31:45 · 题解

注意到有贡献的一定是开始的一段乘法段，因为后面的段一定又有 + 又有 -。

设 S_n=\prod_{i=1}^na_i，于是答案就为

组合意义即为枚举第一个连续的乘法段的最后一个数在哪里，那么下一个位置必须填 + 或 -，其余的随便填。

对于 a_i 的单点修改，有一个显然的想法是对于 S_i 的一段后缀做乘法，于是用线段树区间乘法，维护区间和即可。

但是以上的做法是错误的！

由于 0 不存在逆元，而题目中说是非负整数没有保证不为 0，所以该做法可以被以下数据轻松卡掉：

1 1
0
1 1

但是由于该题数据比较水，所以可以通过。

正确的维护方法应该是：仍然是单点修改，在向上回溯的过程中维护区间积 \rm mul 和答案 \rm ans。则

#include <cstdio>

typedef unsigned long long ull;
const int Mod = 1000000007;
const int maxN = 100005, maxL = 1 << 18 | 1;

int N, Q, A[maxN], Pow[maxN];

#define lc i << 1
#define rc i << 1 | 1
int Mul[maxL], Ans[maxL];
void build(int i, int l, int r)
{
    if (l == r)
    {
        Mul[i] = A[l];
        if (l == N)
            Ans[i] = A[l];
        else
            Ans[i] = A[l] * 2ULL * Pow[N - l - 1] % Mod;
        return;
    }
    int m = (l + r) >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    Mul[i] = (ull)Mul[lc] * Mul[rc] % Mod;
    Ans[i] = ((ull)Mul[lc] * Ans[rc] + Ans[lc]) % Mod;
}
void modify(int i, int l, int r, int pos, int v)
{
    if (l == r)
    {
        A[l] = v;
        Mul[i] = A[l];
        if (l == N)
            Ans[i] = A[l];
        else
            Ans[i] = A[l] * 2ULL * Pow[N - l - 1] % Mod;
        return;
    }
    int m = (l + r) >> 1;
    if (pos <= m)
        modify(lc, l, m, pos, v);
    else
        modify(rc, m + 1, r, pos, v);
    Mul[i] = (ull)Mul[lc] * Mul[rc] % Mod;
    Ans[i] = ((ull)Mul[lc] * Ans[rc] + Ans[lc]) % Mod;
}
#undef lc
#undef rc

int main()
{
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++i)
        scanf("%d", A + i);
    Pow[0] = 1;
    for (int i = 1; i <= N; ++i)
        Pow[i] = 3U * Pow[i - 1] % Mod;

    build(1, 1, N);

    for (int t, v; Q--;)
    {
        scanf("%d%d", &t, &v);
        modify(1, 1, N, t, v);
        printf("%d\n", Ans[1]);
    }

    return 0;
}