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

· · 题解

题目传送门

思路

每次乘法操作会使得之前的所有加法操作的贡献翻倍。因此，一个加法操作的最终贡献不仅取决于它自己的值，还取决于它之后的所有乘法操作。

操作序列是由多个区间拼接而成，我们要算出每个加法操作在它之后的所有乘法操作的次数。

  1. 定义 S_i 为前 i 个操作中乘法操作的数量。可以通过前缀和数组快速计算任意区间 l\sim r 内的乘法操作次数：S_r-S_{l-1}。
    1. 令 V_1 表示当前区间之前的所有乘法操作的累积倍数，V_2 表示当前区间之后的所有乘法操作的累积倍数。
  2. 对于区间 l_i\sim r_i，令其内部的乘法操作次数为 C_i = S_{r_i} - S_{l_i-1}。
    • 当前区间的乘法操作会使得 v_2 乘以 2^{C_i}。
    • 加法操作的贡献是 V_1\times 2^k，其中 k 是该加法操作之后的所有乘法操作次数。
    • 通过差分数组 D_1 和 D_2 来记录：
      • 更新 V_1 为 V_1\times 2^{C_i}。
  3. 对于每个操作：
    • 如果是加法操作（操作 1），则其贡献为 v\times B \bmod 10^4，累加到对应的 A_{id} 上。
    • 如果是乘法操作（操作 2），则 B 乘以 2。

代码

提交记录

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
typedef long long ll;
const int mod = 1e4;
void add(int& a, int b) {a = (a + b) % mod;}

int n,m,q;
struct node{
    int op,i,v;
} c[MAXN];

int pw2[MAXN], b[MAXN][2];
int s[MAXN], a[MAXN], d1[MAXN], d2[MAXN];
int getsum(int l, int r){
    return s[r] - s[l-1];
}

int main(){
    cin>>n>>m>>q;
    pw2[0] = 1;
    int op,id,v;
    for(int i=1;i<=m;++i){
        cin>>op;
        if(op==1) cin>>id>>v;
        v %= mod;
        c[i] = node{op,id,v};
        s[i] = s[i-1] + (c[i].op == 2);
        pw2[i] = pw2[i-1] * 2 % mod;
    }

    for(int i=1;i<=q;++i) cin>>b[i][0]>>b[i][1];
    int v1 = 1, v2 = 1;
    for(int i=q;i>=1;i--){
        int l = b[i][0], r = b[i][1];
        v2 = v2 * pw2[getsum(l,r)] % mod;
        add(d1[r], v1);
        add(d2[l-1], v2); 
        v1 = v1 * pw2[getsum(l,r)] % mod;
    }

    int now = 0; 
    for(int i=m;i>=1;i--){ 
        add(now, d1[i] - d2[i] + mod); 
        if(c[i].op == 1) add(a[c[i].i], c[i].v * now % mod);
        else now = now * 2 % mod;
    }

    for(int i=1;i<=n;++i) cout<<a[i]<<" ";
    return 0;
}