daimayuan, codeforces, 博客, csdn

题目描述

蜗蜗有两个长度都为 n​ 的数列 A,B​​​，同时他会进行 q​ 次操作。

对于每一次操作，他会先选择其中一个数列 (A/B) ，再选择一个区间 l,r，将选定的序列 [l,r] 中的数对位加上Fibonacci数列。

换句话说，就是将选定数列的第 l 项加上 1，第 l+1 项加上 1，第 l+2 项加上 2，第 l+3 项加上 3… 第 r 项加上 Fib(r−l+1)​​，即 Fibonacci 数列的第 r−l+1 项。

在每次操作结束的时候，蜗蜗都会变得非常好奇。他想知道此时 A​ 和 B​ 两个序列是否相同，由于他一看到比较长的数就会头晕，所以你只需要判断 A​ 和 B​ 在模 M​ 的意义下是否相同即可。

输入格式

第一行三个数 n,q,M，分别表示数列的长度，操作的总次数和模数。

第二行和第三行各输入 n​ 个整数，表示 A 和 B 的初始值。

接下来 q 行每行包含一个字符 c 和两个整数 l,r​，描述一次操作。具体细节见样例。

输出格式

输出 q​ 行，每行一个字符串 Yes 或 No ，表示此时两个数列是否在模 M 的意义下相同。

思路

两个数组分开操作不方便，我们设C = A - B, 如果A == B则 C == 0, 考虑怎么优化，类似于我们区间加一个相同的数我们有差分可以O ( 1 )的做, 因为中间的差分是不变的，所以对于区间加减法我们可以找一下什么是不变的，发现相邻的差会改变但是$A_i - A_{i-1} - A_{i-2}$是不变的, 因为$fbi_i = fbi_{i-1} + fbi_{i-2}$

我们考虑设$D_i = C_i - C_{i-1} - C_{i-2}$, $D_1 = C_1$, $D_2 = C_2 - C_1$. 如果A == B则C == 0则D == 0, 因此原问题转化为看D的值，我们以对A操作为例，B同理，假设区间为[l, r], 则$D_l += 1, D_{r+1} -= fbi_{r-l+2}$.这是正常的差分，但是我们这里$D_i$减去了$D_{i-1}$和$D_{i-2}$，所以$D_r$的变动会影响到$D_{r+2}$。

对于$D_{r+3}$，它是维护了$D_{r+2}$和$D_{r+1}$，既然这两个没变，那$D_{r+3}$也就没变。
那么v变了多少？我们可以发现$D_{r}$加上了$fbi_{r-l+1}$，$D_{r+1}$不变，那么$D_{r+2}$由于维护的是$D_{r+2} - D_{r+1} - D_{r}$，所以应该减小$dbi_{r-l+1}$。那么我们可以记录一下当前D中不为0的个数，如果操作完后均为零就合法。

代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, q, mod;

int a[N], b[N], d[N];
int fbi[N];
int cnt;

int sum(int a, int b) { return (a + b) % mod; }
int sub(int a, int b) { return (a - b + mod) % mod; }

void init() {
    fbi[1] = fbi[2] = 1;
    for (int i = 3; i < N; i ++ ) fbi[i] = sum(fbi[i - 1], fbi[i - 2]);
}

void modify(int x, int u) {
    cnt -= (d[x] != 0);
    d[x] = sum(d[x], u);
    cnt += (d[x] != 0);
}

void solve() {
    scanf("%d%d%d", &n, &q, & mod);
    for (int i = 1; i <= n; i ++ ) scanf("%d", a + i);
    for (int i = 1; i <= n; i ++ ) scanf("%d", b + i);

    init();

    for (int i = 1; i <= n; i ++ ) d[i] = sub(a[i], b[i]);
    for (int i = n; i >= 3; i -- ) d[i] = sub(d[i], sum(d[i - 1], d[i - 2]));
    d[2] = sub(d[2], d[1]);

    for (int i = 1; i <= n; i ++ ) {
        if (d[i])
            cnt ++;
    }

    while (q -- ) {
        char op[2];
        int l, r;
        scanf("%s%d%d", op, &l, &r);
        if (op[0] == 'A') {
            modify(l, 1);
            if (r + 1 <= n) modify(r + 1, mod - fbi[r - l + 2]);
            if (r + 2 <= n) modify(r + 2, mod - fbi[r - l + 1]);
        }
        else {
            modify(l, mod - 1);
            if (r + 1 <= n) modify(r + 1, fbi[r - l + 2]);
            if (r + 2 <= n) modify(r + 2, fbi[r - l + 1]);
        }

        if (cnt == 0) puts("Yes");
        else puts("No");
    }
}

int main() {
    int T;
    T = 1;
    while (T --) {
        solve();
    }
    return 0;
}