[AGC031B] Reversi

题目大意

有一个长度为 \(n\) 的数列 \(a\)，你需要对其进行 \(q\) 次操作，操作有两种类型，按如下格式给出：

• 1 x y：将 \(a_x\) 变成 \(y\)；
• 2 l r：询问位置在 \(\left[ l,r \right]\) 之间的不下降子串有多少个。

思路

考虑 DP。

考虑第 \(i\) 个石头，如果第 \(i\) 个石头不修改，方案数仍为 \(dp_{i-1}\)；如果第 \(i\) 个石头修改，那么贡献就是第 \(i\) 个石头与前面所有颜色相同石头进行操作的可能操作数。

记 \(\operatorname{pre}_i\) 为上一个与 \(i\) 颜色相同石头的位置。

所以转移方程为

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 5005000;
const int Mod = 1e9 + 7;

int n;

int a[N];

int cnt,col[N];

int dp[N],last[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;

    for(int i = 1;i <= n; i++) {
        cin >> a[i];
    }
    
    for(int i = 1;i <= n; i++) {
        if(a[i] != a[i - 1]) {
            cnt ++;
            col[cnt] = a[i];
        }
    }

    dp[0] = 1;
    for(int i = 1;i <= cnt; i++) {
        dp[i] = dp[i - 1];

        if(last[col[i]]) {
            int j = last[col[i]];
            dp[i] = (dp[i] + dp[j]) % Mod;
        }

        last[col[i]] = i;
    }

    cout << (dp[cnt] + Mod) % Mod << "\n";
    return 0;
}