题解：B4161 [BCSP-X 2024 12 月小学高年级组] 操作序列

这种题最大的特征就是关系层层叠叠，运算依赖区间，很复杂，要一层一层算。

题目中有几个区间 / 序列：

• 长度为 的数据序列 ；
• 长度为 的操作序列 ；
• 长度为 的操作区间 ；
  按照 去完成对应 的部分，最终作用在 上，而我们求的就是最终的 。

接下来请带上你的注意力：

• 注意到，对于值为 的不管乘多少次都是 ，所以可以考虑转化乘法操作为改变加法操作次数；
• 注意到，对 ，当且仅当 ，有 中的乘法操作会增加 中的操作次数；
• 注意到，对 ，当且仅当，有乘法操作 增加 的操作次数；

所以思路就清晰了：

1. 对于操作区间之间的贡献，进行倒序处理，累计其进行的乘法的个数：

   • 对于 ，每个操作都会继承上一个操作区间的影响；
   • 对于 ， 带来的影响就是 中乘法操作;

   综合以上两点，考虑：

   • 用差分维护乘法操作个数， 维护区间之间的影响；
   • 用前缀和维护 的乘法操作总个数，用于 计算结果；

2. 对于操作区间内的贡献，总的 完成倒序扫描：

   • 结合上述维护的区间之间的影响，不断累乘，计算出每个加法 的操作次数；
   • 同时根据 加到数据序列 上，得到答案；

代码如下：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 200005;
const LL mod = 10000;

int n, m, q;
LL seq[MAXN];

bitset<MAXN> optType;
LL ind[MAXN], val[MAXN];
LL mulCntSum[MAXN];
LL cntDif[MAXN];

LL l[MAXN], r[MAXN];

inline LL read() {
    LL x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}
inline void init() {
    n = read(), m = read(), q = read();
    for (int i = 1; i <= m; ++i) {
        optType[i] = (read() & 1);
        if (optType[i]) {
            ind[i] = read();
            val[i] = read();
        }
    }
    for (int i = 1; i <= q; ++i) {
        l[i] = read();
        r[i] = read();
    }
    return;
}

inline LL Pow(int base, int t) {
    LL res = 1;
    while (t) {
        if (t & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        t >>= 1;
    }
    return res;
}
inline void calcPrefixSum() {
    for (int i = 1; i <= m; ++i) {
        mulCntSum[i] = mulCntSum[i - 1];
        if (!optType[i])
            mulCntSum[i]++;
    }
    return;
}
inline void calcRangeDif() {
    LL cur = 1;
    for (int i = q; i >= 1; --i) {
        cntDif[r[i]] = (cntDif[r[i]] + cur) % mod;
        cur = (cur * Pow(2, mulCntSum[r[i]] - mulCntSum[l[i] - 1])) % mod;
        cntDif[l[i] - 1] = (cntDif[l[i] - 1] - cur + mod) % mod;
    }
    return;
}
inline void calcOptToSeq() {
    LL optCnt = 0;
    for (int i = m; i >= 1; --i) {
        optCnt = (optCnt + cntDif[i]) % mod;
        if (optType[i])
            seq[ind[i]] = (seq[ind[i]] + optCnt * val[i]) % mod;
        else
            optCnt = (optCnt << 1) % mod;
    }
    return;
}

int main() {
    init();
    calcPrefixSum();
    calcRangeDif();
    calcOptToSeq();
    for (int i = 1; i <= n; ++i)
        cout << seq[i] << ' ';
    return 0;
}