自动搬运

查看原文

来自洛谷，原作者为

	LoongPig 人生中最大的遗憾，不是努力了没有成功，而是从未尝试过努力||发接龙拉黑

搬运于2025-08-24 21:17:28，当前版本为作者最后更新于2025-05-03 14:51:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

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

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

1. 定义 $S_i$ 为前 $i$ 个操作中乘法操作的数量。可以通过前缀和数组快速计算任意区间 $l\sim r$ 内的乘法操作次数：$S_r-S_{l-1}$。
2. 令 $V_1$ 表示当前区间之前的所有乘法操作的累积倍数，$V_2$ 表示当前区间之后的所有乘法操作的累积倍数。
3. 对于区间 $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$ 来记录：
     • ${D_1}_{r_i}$ 增加 $V_1$。
     • ${D_2}_{l_i-1}$ 增加 $V_2$。
     • 更新 $V_1$ 为 $V_1\times 2^{C_i}$。
4. 对于每个操作：
   • 如果是加法操作（操作 $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;
}