abc253F - Operations on a Matrix

F - Operations on a Matrix

初看起来感觉不是很好搞，主要是有赋值操作，我们需要知道的是最近一次在这个行上的赋值操作以及之间的贡献

那么我们离线处理，每个3操作都往前找一个最近的同行2操作，然后两个做差就能得到中间的和。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("YES")
#define B puts("NO")

using namespace std;
typedef double db;
typedef long long ll;
const ll mo=998244353;
const int N = 2e5 + 5;


struct node {
	int op, l, r, x;
};
node a[N];
int n, m, Q, x, r,id;

struct key {
	int id, x;
};
vector<key> q[N];
vector<key> v[N];

ll c[N], ans[N];
int lowbit(int x) {
	return x & (-x);
}
void upd(int x, ll y) {
	for (;x < N;x += lowbit(x)) c[x] += y;
}
ll ask(int x) {
	ll s = 0;
	for (;x;x -= lowbit(x)) s += c[x];
	return s;
}

int main()
{

#ifdef LOCAL
 		freopen("in.txt", "r", stdin);
    	freopen("out.txt", "w", stdout);
#endif	
	scanf("%d %d %d", &n, &m, &Q);
	fo(i, 1, Q) {
		scanf("%d %d %d", &a[i].op, &a[i].l, &a[i].r);
		if (a[i].op == 1) scanf("%d", &a[i].x);
	}
	fd(i, Q, 1) {
		if (a[i].op == 1) continue;
		if (a[i].op == 2) {
			r = a[i].l;
			for (int j = 0;j < (int)v[r].size();j++) {
				q[i].emplace_back(v[r][j]);
			}
			v[r].clear();
		}
		if (a[i].op == 3) {
			v[a[i].l].emplace_back((key) { i, a[i].r });
		}
	}

	fo(i, 1, Q) {
		if (a[i].op == 1) {
			upd(a[i].l, (ll)a[i].x);
			upd(a[i].r + 1, (ll)-a[i].x);
		}
		if (a[i].op == 2) {
			for (int j = 0;j < q[i].size();j++) {
				x = q[i][j].x;
				id = q[i][j].id;
				ans[id] = (ll)a[i].r - ask(x);

				// printf("%d %d %lld\n", id,a[i].r, ask(x));
			}
		}
		if (a[i].op == 3) {
			ans[i] += ask(a[i].r);
		}
	}

	// return 0;
	fo(i, 1, Q) {
		if (a[i].op == 3) printf("%lld\n", ans[i]);
	}



	



	return 0;
}