- 题解
矩阵操作
- @ 2025-7-21 15:18:06
#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 条评论
目前还没有评论...