#include <bits/stdc++.h>
using namespace std;

// 设置最大常量,根据题目要求调整
const int N = 2e5 + 10; 

// 树状数组实现(用于维护列加法)
long long tr[N]; // 使用long long防止溢出

// 计算lowbit(获取x的最低有效位)
int lowbit(int x) {
	return x & -x; // 位运算技巧,获取最低位的1
}

// 树状数组单点增加操作
void add(int x, long long c, int n) {
	// 从x开始,向上更新所有相关节点
	for(int i = x; i <= n; i += lowbit(i))
		tr[i] += c;
}

// 树状数组前缀和查询
long long ask(int x) {
	long long res = 0;
	// 从x开始,向下累加所有相关节点
	for(int i = x; i; i -= lowbit(i))
		res += tr[i];
	return res;
}

// 操作存储数组
int t[N];       // 操作类型(1/2/3)
int a[N];       // 操作参数1(行/左边界)
int b[N];       // 操作参数2(列/右边界)
long long c[N]; // 操作参数3(值)

// 查询相关数据结构a
vector<int> subt[N]; // 每个赋值操作影响的查询列表
pair<int, long long> latest[N]; // 每行最后一次赋值操作(时间点,值)
long long ans[N];    // 存储所有查询结果
int ans_cnt = 0;         // 查询结果计数器

int main() {
	// 关闭同步,加速IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, q;
	cin >> n >> m >> q;
	
	// 初始化latest数组(-1表示未被赋值过)
	for(int i = 0; i < n; ++i) {
		latest[i] = {-1, 0};
	}
	
	// 读取并预处理所有查询
	for (int i = 1; i <= q; i++) {
		cin >> t[i]; // 读取操作类型
		
		if (t[i] == 1) {
			// 加法操作:区间[l,r]加x
			cin >> a[i] >> b[i] >> c[i];
		} 
		else if (t[i] == 2) {
			// 赋值操作:行a[i]设为c[i]
			cin >> a[i] >> c[i];
			latest[a[i]] = {i, c[i]}; // 更新最后一次赋值记录 a[i] 行最后一次受操作i影响 变为c[i]
		} 
		else {
			// 查询操作:查询(i,j)的值
			cin >> a[i] >> b[i];
			
			// 获取该行最后一次赋值信息
			auto [j, x] = latest[a[i]]; //该行最后一次受j影响,变为了x
			
			// 初始化答案为最后一次赋值的x
			ans[ans_cnt] = x;
			c[i] = ans_cnt++; // 记录答案位置
			
			// 如果有赋值操作,记录这个查询受该赋值影响
			if (j >= 1) {
				subt[j].push_back(i); //j这个赋值操作影响的查询操作列表
			}
		}
	}
	
	// 初始化树状数组(清零)
	memset(tr, 0, sizeof(tr));
	
	// 处理所有操作
	for (int i = 1; i <= q; ++i) {
		if (t[i] == 1) {
			// 加法操作:区间[l,r]加c
			// 使用差分思想:l位置+c,r+1位置-c
			add(a[i], c[i], m); // 转换为1-based索引
			add(b[i] + 1, -c[i], m);
		} 
		else if (t[i] == 2) {
			// 赋值操作:处理受此操作影响的查询
			for (int j : subt[i]) {
				// 对于受影响的查询,减去赋值前的加法总和
				ans[c[j]] -= ask(b[j]); //c[j] 是查询的答案的位置
			}
		} 
		else {
			// 查询操作:加上当前的加法总和
			ans[c[i]] += ask(b[i]);
		}
	}
	
	// 输出所有查询结果
	for (int i = 0; i < ans_cnt; ++i) {
		cout << ans[i] << '\n';
	}
	
	return 0;
}

0 条评论

目前还没有评论...