记录编号	567398	评测结果	AAAAAAAAAA
题目名称	[BOI 2007] 摩基亚Mokia	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	2.452 s
提交时间	2021-11-26 22:32:44	内存使用	93.84 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 2e6 + 5;
struct query {
	int op,id,x,y,k;
	query() {
		op = id = x = y = k = 0;
	}
	query(int op,int id,int x,int y,int k):op(op),id(id),x(x),y(y),k(k){}
}Q[maxn],b[maxn];
int read() {
	int s = 0;
	char c = getchar();
	for(;!isdigit(c);c = getchar());
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s;
}
void write(int x) {
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void print(int x) {
	write(x);
	putchar('\n');
	return ;
}
int n;         
int c[maxn];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	for(;x <= n;x += lowbit(x)) {
		c[x] += y;
	}
	return ;
}
int Query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += c[x];
	return ans;
}
int opt,cnt,tot;
int ans[maxn];
void solve(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1 , r);
	int i = l,j = mid + 1;
	for(int k = l;k <= r;++ k) {
		if(j > r||(i <= mid&&Q[i].x <= Q[j].x)) {
			if(Q[i].op == 1)add(Q[i].y , Q[i].k);
			b[k] = Q[i ++];
		}
		else {
			if(Q[j].op == 2)ans[Q[j].id] -= Query(Q[j].y);
			if(Q[j].op == 3)ans[Q[j].id] += Query(Q[j].y);
			b[k] = Q[j ++];
		}
	}
	for(int k = l;k <= mid;++ k)
		if(Q[k].op == 1)add(Q[k].y , -Q[k].k);
	for(int k = l;k <= r;++ k)Q[k] = b[k];
	return ;
}
int main() {
	freopen("mokia.in","r",stdin);
	freopen("mokia.out","w",stdout);
	n = read();
	n = read();
	while(~ scanf("%d",&opt)) {
		if(opt == 3)break ;
		int x1,y1,x2,y2,x,y,k;
		if(opt == 1) {
			x = read();
			y = read();
			k = read();
			Q[++ cnt] = query(1 , 0 , x , y , k);
		}
		else {
			x1 = read();
			y1 = read();
			x2 = read();
			y2 = read();
			Q[++ cnt] = query(3 , ++ tot , x1 - 1 , y1 - 1 , 0);
			Q[++ cnt] = query(2 , tot , x1 - 1 , y2 , 0);
			Q[++ cnt] = query(2 , tot , x2 , y1 - 1 , 0);
			Q[++ cnt] = query(3 , tot , x2 , y2 , 0);
		}
	}
	//三个维度：时间，x，y
	//时间有序，x用CDQ，y用BIT即可 
	solve(1 , cnt);
	for(int i = 1;i <= tot;++ i)print(ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}