C++(g++ 7.5.0) 解法, 执行用时: 165ms, 内存消耗: 16276K, 提交时间: 2022-08-09 16:46:58

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxm = 210010;
const int maxn = 2100000;
struct Node{
	int op,x,y;
	int val,id;
	bool friend operator < (const Node &a,const Node &b){
		return a.x < b.x;
	}Node(){}
	Node(int a,int b,int c,int d,int e){op=a;x=b;y=c;val=d;id = e;}
}a[maxm],atmp[maxm];
int cnt,n;
int anss[10010];
int c[maxn],tmp[maxm];
#define lowbit(x) (x&-x)
inline void modify(int x,int y){
	if(!x) return;
	for(;x <= n;x+=lowbit(x)) c[x] += y;
}
inline int query(int x){
	int ret = 0;
	for(;x>=1;x-=lowbit(x)) ret += c[x];
	return ret;
}
inline void merge(int l,int r){
	if(l == r) return;
	int mid = l+r >> 1;
	int i = l,j = mid+1,k = l;
	while(i <= mid || j <= r){
		if(j > r || ( i <= mid && a[i].x < a[j].x)) atmp[k++] = a[i++];
		else atmp[k++] = a[j++];
	}for(int i=l;i<=r;++i) a[i] = atmp[i];
}
void solve(int l,int r){
	if(l == r) return ;
	int mid = l+r >> 1;
	solve(l,mid);
	solve(mid+1,r);
	merge(l,mid);
	merge(mid+1,r);
	int p = l,cnt = 0;
	for(int i = mid+1;i<=r;++i){
		if(a[i].op == 2){
			while(p <= mid && a[p].x <= a[i].x){
				if(a[p].op == 1){
					tmp[++cnt] = p;
					modify(a[p].y,a[p].val);
				}++p;
			}anss[a[i].id] += a[i].val*query(a[i].y);
		}
	}
	for(int i=1;i<=cnt;++i) modify(a[tmp[i]].y,-a[tmp[i]].val);
}
int main(){
	read(cnt);read(n);
	int op,x1,y1,x2,y2,x;
	int query_id = 0;
	while(1){
		read(op);if(op == 3) break;
		if(op == 1){
			read(x1);read(y1);read(x);
			a[++cnt] = (Node){op,x1,y1,x,0};
		}else{
			x = ++query_id;
			read(x1);read(y1);read(x2);read(y2);
			a[++cnt] = (Node){op,x2,y2,1,x};
			a[++cnt] = (Node){op,x1-1,y2,-1,x};
			a[++cnt] = (Node){op,x2,y1-1,-1,x};
			a[++cnt] = (Node){op,x1-1,y1-1,1,x};
		}
	}
	solve(1,cnt);
	for(int i=1;i<=query_id;++i){
		printf("%d\n",anss[i]);
	}
	getchar();getchar();
	return 0;
}

C++ 解法, 执行用时: 395ms, 内存消耗: 19932K, 提交时间: 2021-08-26 22:15:00

#include<bits/stdc++.h>
using namespace std;
struct trsz{
	int w[2001000],n;
	int lowbit(int x){
		return x&(-x);
	}
	void insert(int x,int val){
		while(x<=n){
			w[x]+=val;
			x+=lowbit(x);
		}
	}
	int query(int x){
		int ans=0;
		while(x){
			ans+=w[x];
			x-=lowbit(x);
		}
		return ans; 
	}
}; 
trsz ty;
struct node{
	int op,id,x,y,w;
};
int cmp(node x,node y){
	return x.x<y.x;
}
node p[300010],p1[300010],p2[300010];
int ans[170010],num,gs,op;
void cdq(int l,int r);
int main(){
	scanf("%d",&op);
	while(op!=3){
		if(op==0){
			int o;
			scanf("%d",&o);
			ty.n=o+1;
		}
		if(op==1){
			int l,r,w;
			scanf("%d%d%d",&l,&r,&w);
			p[++gs]={1,0,l,r,w};
		}
		if(op==2){
			int x,y,xx,yy;
			scanf("%d%d%d%d",&x,&y,&xx,&yy);
			num++;
			p[++gs]={2,num,x-1,y-1,1};
			p[++gs]={2,num,xx,y-1,-1};
			p[++gs]={2,num,x-1,yy,-1};
			p[++gs]={2,num,xx,yy,1};
		}
		scanf("%d",&op);
	}
	cdq(1,gs);
	for(int i=1;i<=num;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
} 
void cdq(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	cdq(l,mid);
	cdq(mid+1,r);
	for(int i=l;i<=mid;i++) p1[i]=p[i];
	for(int i=mid+1;i<=r;i++) p2[i]=p[i];
	
	sort(p1+l,p1+mid+1,cmp);
	sort(p2+mid+1,p2+r+1,cmp);
	int x=l;
	for(int i=mid+1;i<=r;i++){
		if(p2[i].op==1) continue;
		while(p1[x].x<=p2[i].x&&x<=mid){
			if(p1[x].op==2){
				x++;
				continue;
			}
			ty.insert(p1[x].y,p1[x].w);
			x++;
		} 
		ans[p2[i].id]=ans[p2[i].id]+p2[i].w*ty.query(p2[i].y);
	}
	for(int i=l;i<x;i++){
		if(p1[i].op==1){
			ty.insert(p1[i].y,-p1[i].w);
		}
	}
}