简单题_简单题 csdn-CSDN博客

本文链接：https://blog.csdn.net/DancingZ/article/details/83003831

本文深入解析了一道CDQ模板题，详细介绍了如何使用树状数组进行区间更新和查询的操作。通过拆分矩形和偏移处理，有效解决了大规模数据下二维数组的快速更新和求和问题，适用于竞赛编程中复杂的数据结构挑战。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目大意：

你有一个N*N的棋盘，每个格子初始值v=0，现在要求你支持两种操作：

1、v(x,y)+=d

2、getsum(x1,y1,x2,y2)

Input

输入文件第一行一个正整数N。
接下来每行一个操作。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

Hint

1<=N<=500000,操作数不超过200000个，内存限制20M。
对于100%的数据，操作1中的A不超过2000。

cdq模板题，拆矩形分开查询，坑点是取0，树状数组要加偏移。

#include<bits/stdc++.h>
using namespace std;
const int Maxn=1000005;
inline int getint(){
	int res=0;char c=getchar();
	while(!isdigit(c))c=getchar();
	while(isdigit(c))res=res*10+c-'0',c=getchar();
	return res;
}
struct Matrix{
	int x,y,idx,cmd;
	Matrix(int x=0,int y=0,int idx=0,int cmd=0):x(x),y(y),idx(idx),cmd(cmd){}
	bool operator<(const Matrix&rhs)const{
		return x<rhs.x;
	}
}a[Maxn];
int n,cnt,cntq,f[Maxn];
struct BIT{
	int c[Maxn];
	#define lowbit(x) (x)&-(x)
	void add(int x,int k){
		for(++x;x<=n+1;x+=lowbit(x))c[x]+=k;
	}
	int sum(int x){
		int ret=0;
		for(++x;x>0;x-=lowbit(x))ret+=c[x];
		return ret;
	}
}bit;
void cdq(int l,int r){
	if(l>=r)return ;
	int mid=l+r>>1;
	cdq(l,mid),cdq(mid+1,r);
//	sort(a+l,a+mid+1),sort(a+mid+1,a+r+1);
	int i=l,j=mid+1;
	for(;j<=r;++j){
		for(;i<=mid&&a[i].x<=a[j].x;++i)
			if(!a[i].idx)bit.add(a[i].y,a[i].cmd);
		if(a[j].idx)f[a[j].idx]+=bit.sum(a[j].y)*a[j].cmd;
	}
	while(--i>=l)if(!a[i].idx)bit.add(a[i].y,-a[i].cmd);
	inplace_merge(a+l,a+mid+1,a+r+1);
}
int main(){
	n=getint();
	while(233){
		int op=getint();
		if(op==3)break;
		if(op==1){
			int x=getint(),y=getint(),v=getint();
			a[++cnt]=Matrix(x,y,0,v);
		}else {
			int x1=getint(),y1=getint(),x2=getint(),y2=getint();
			a[++cnt]=Matrix(x2,y2,++cntq,1);
			a[++cnt]=Matrix(x1-1,y2,cntq,-1);
			a[++cnt]=Matrix(x2,y1-1,cntq,-1);
			a[++cnt]=Matrix(x1-1,y1-1,cntq,1);
		}
	}
	cdq(1,cnt);
	for(int i=1;i<=cntq;++i)
		cout<<f[i]<<'\n';
	return 0;
}