矩形求和（Rectangle Sum）

3

taojinghua LV 9 @ 2026-8-2 10:08:07

看到这道题的第一眼，让我想到了另一道题： CQOI2017 老C的任务

题意就不过多解释了，在给定的点中寻找在给出的矩阵内部的点的点权总和 ~~(有点绕口)~~，但是注意它们的输入和范围有不同之处，不得照抄！！！

不同的就是它是 $N<=2e5$ 且以x1，y1，x2，y2的顺序输入，且x2和y2取不到，但大致思路是能沿用的......

基础手动二分

这道题首先能想到的比暴力更优的方法就是手动二分，将点的x坐标排序，二分出满足x坐标要求的点，再遍历一遍找出y坐标也符合的点，加上点权即可，然后就可以得到一个28分的优秀TLE代码了......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
struct node{ll x,y,k;}t[200010];
bool cmp(node a,node b){return a.x<b.x;}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1,x,y,k;i<=n;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&k);
		t[i]={x,y,k};
	}
	sort(t+1,t+n+1,cmp);
	while(m--)
	{
		ll a,b,c,d,ans=0;scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		ll l=1,r=n,p=0,q=0;
		while(l<=r)
		{
			ll mid=(l+r)>>1;
			if(t[mid].x>=a)r=mid-1,p=mid;
			else l=mid+1;
		}
		l=1,r=n;
		while(l<=r)
		{
			ll mid=(l+r)>>1;
			if(t[mid].x<c)l=mid+1,q=mid;
			else r=mid-1;
		}
		for(ll i=p;i<=q;i++)if(t[i].x>=a&&t[i].x<c&&t[i].y>=b&&t[i].y<d)ans+=t[i].k;
		printf("%lld\n",ans);
	}
	return 0;
}

优化

显然 ~~(试了后知道的)~~，这样朴素二分的时间复杂度是过不去的，所以需要优化，这时，可以用出专门处理区间内点权及总和的数据结构--线段树，只不过是两个关键字的而已，但也可以转化成一个的

就是x和y坐标分别二分，但有一个还是要开成两个关键字，就是另外一个不参与二分，然后记得给单独的那个关键字进行离散化优化，再掏出线段树最擅长的区间求和即可解决问题 最后注意输入，内存及取值范围的不同即可

~~但是时间用的有亿点点长(807ms)......~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=200005;
#define mid ((l+r)>>1)
struct node
{
	ll x,y,k;
	node(ll x1=0,ll y1=0):x(x1),y(y1){}
	bool operator<(const node &b)const{return x<b.x;}
}a[N];
ll n,m,y[N],root[N],tot,ls[N*20],rs[N*20],sum[N*20];
void change(ll &u,ll v,ll l,ll r,ll y,ll p)
{
	u=++tot;
	ls[u]=ls[v],rs[u]=rs[v],sum[u]=sum[v]+p;
	if(l==r)return;
	if(y<=mid)change(ls[u],ls[v],l,mid,y,p);
	else change(rs[u],rs[v],mid+1,r,y,p);
}
ll query(ll u,ll l,ll r,ll x,ll y)
{
	if(x>r||y<l)return 0;
	if(x<=l&&r<=y)return sum[u];
	return query(ls[u],l,mid,x,y)+query(rs[u],mid+1,r,x,y);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].k);
	for(ll i=1;i<=n;i++)y[i]=a[i].y;
	sort(y+1,y+1+n);
	ll yn=unique(y+1,y+1+n)-y-1;
	for(ll i=1;i<=n;i++)a[i].y=lower_bound(y+1,y+1+yn,a[i].y)-y;
	sort(a+1,a+1+n);
	for(ll i=1;i<=n;i++)change(root[i],root[i-1],1,yn,a[i].y,a[i].k);
	while(m--)
	{
		ll x1,x2,y1,y2;scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		x2--,y2--;
	    x1=lower_bound(a+1,a+1+n,node(x1,0))-a;
	    x2=upper_bound(a+1,a+1+n,node(x2,0))-a-1;
	    y1=lower_bound(y+1,y+1+yn,y1)-y;
	    y2=upper_bound(y+1,y+1+yn,y2)-y-1;
	    printf("%lld\n",query(root[x2],1,yn,y1,y2)-query(root[x1-1],1,yn,y1,y2));
	}
	return 0;
}

1

Raoxuanrui01 LV 8 @ 2026-8-11 9:47:00

我们注意到此题除了数据范围与此题略有差别之外没有别的差别，所以考虑沿用思路。

简单来讲，考虑前缀和，发现前缀和数组没法存，但这实际上不难，因为 $(X,Y)$ 的前缀和本质上就是要求所有点中满足 $x_i\le X$ 且 $y_i\le Y$ 的点的权值之和，那么对 $x$ 进行排序，就是所有满足 $y_i\le Y$ 的权值之和，显然可以使用树状数组完成。因为值域较大，所以进行离散化（注意在询问时一并离散化）。

实现细节上，考虑以下数据：

显然，询问要求 $(1,1)$ 至 $(2,4)$ 内的点权之和，但如果你在处理完树状数组后再进行询问，就会将 $(3,3)$ 的权值考虑进去，显然这不是我们想要的，所以我们将询问拆成四个点与给出的所有点一并处理，这样才能保证询问时能正确算出前缀和。

具体的，点的结构体中除了坐标与权值之外，还有一个标记用来表示属于的询问。在坐标相同时，显然要将询问的点排在最后面，然后处理询问点时根据前缀和公式判一下正负号就做完了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll x,y,p,lx;
  //lx的绝对值为所属询问编号，lx的正负表示在前缀和公式中的正负
	bool operator <(const node &ano)const{
		if(x==ano.x){
			if(y==ano.y){
				return (lx==0)>(ano.lx==0);
			}
			return y<ano.y;
		}
		return x<ano.x;
	}
};
int n,m;
node nod[2000005];
int s[200005],s2[200005];
ll tre[200005];
ll ans[200005];
int lowbit(int x){
	return x&(-x);
}
void ins(int x,int y){
	if(x==0){
		return;
	}
	while(x<=n){
		tre[x]+=y;
		x+=lowbit(x);
	}
}
ll sum(int x){
	if(x==0){
		return 0;
	}
	ll ans=0;
	while(x){
		ans+=tre[x];
		x-=lowbit(x);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i]>>s2[i]>>nod[i].p;
		nod[i].x=s[i];
		nod[i].y=s2[i];
	}
	sort(s+1,s+n+1);
	for(int i=1;i<=n;i++){
		nod[i].x=lower_bound(s+1,s+n+1,nod[i].x)-s;
	}
	sort(s2+1,s2+n+1);
	for(int i=1;i<=n;i++){
		nod[i].y=lower_bound(s2+1,s2+n+1,nod[i].y)-s2;
	}
	int ji=n;
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		c--;//较那题的唯一改动
		d--;//较那题的唯一改动 
		a=lower_bound(s+1,s+n+1,a)-s;
		if(c>=s[n]){
			c=n;
		}
		else{
			c=upper_bound(s+1,s+n+1,c)-s-1;
		}
		b=lower_bound(s2+1,s2+n+1,b)-s2;
		if(d>=s2[n]){
			d=n;
		}
		else{
			d=upper_bound(s2+1,s2+n+1,d)-s2-1;
		}
		nod[++ji].x=c;
		nod[ji].y=d;
		nod[ji].lx=i;
		nod[++ji].x=a-1;
		nod[ji].y=b-1;
		nod[ji].lx=i;
		nod[++ji].x=a-1;
		nod[ji].y=d;
		nod[ji].lx=-i;
		nod[++ji].x=c;
		nod[ji].y=b-1;
		nod[ji].lx=-i;
	}
	n=ji;
	sort(nod+1,nod+n+1);
	for(int i=1;i<=n;i++){
		ins(nod[i].y,nod[i].p);
		ll nep=sum(nod[i].y);
		nod[i].p=nep;
		if(nod[i].lx!=0){
			ans[abs(nod[i].lx)]+=(nod[i].lx>0?nod[i].p:-nod[i].p);
		}
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}

0

qinkaiwen LV 10 MOD @ 2026-8-4 19:20:13

二维偏序板子。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
struct BIT{
	int c[N],n;
	void add(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
	int get(int x){int ans=0;for(;x;x-=x&-x)ans+=c[x];return ans;}
}tr;
struct node{int op,x,y1,y2,v,id;}a[N];int alen;
bool cmp(node n1,node n2){return n1.x!=n2.x?n1.x<n2.x:n1.op<n2.op;}
int b[N],blen,ans[N];
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		int x,y,c;cin>>x>>y>>c;
		a[++alen]={0,x,y,y,c,0};
		b[++blen]=y;
	}
	for(int i=1;i<=q;i++)
	{
		int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;
		x1--,x2--,y1--,y2--;
		a[++alen]={1,x1,y1,y2,-1,i};
		a[++alen]={1,x2,y1,y2,1,i};
		b[++blen]=y1;b[++blen]=y2;
	}
	sort(b+1,b+blen+1);int k=unique(b+1,b+blen+1)-b-1;
	tr.n=k;
	for(int i=1;i<=alen;i++)
	{
		a[i].y1=lower_bound(b+1,b+k+1,a[i].y1)-b;
		a[i].y2=lower_bound(b+1,b+k+1,a[i].y2)-b;		
	}
	sort(a+1,a+alen+1,cmp);
	for(int i=1;i<=alen;i++)
	{
		if(a[i].op==0)
			tr.add(a[i].y1,a[i].v);
		else 
			ans[a[i].id]+=(tr.get(a[i].y2)-tr.get(a[i].y1))*a[i].v;
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

0

Benny LV 10 MOD @ 2026-8-4 11:13:38

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q,lsh[1600010],ln,id;
struct N{
	int op,x,l,r,v,id;
}a[800010];
bool cmp(N a,N b){
	if(a.x!=b.x)return a.x<b.x;
	return a.op<b.op;
}
int lowbit(int x){
	return x&(-x);
} 
struct BIT{
	ll tr[1600010];
	void add(int x,int v){
		for(int i=x;i<=ln;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	ll find(int x){
		ll ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr;
ll ans[200010];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int x,y,v;
		cin>>x>>y>>v;
		a[++id]={0,x,y,y,v,0};
		lsh[++ln]=y;
	}
	for(int i=1;i<=q;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x1--;y1--;x2--;y2--;
		a[++id]={1,x1,y1,y2,-1,i};
		a[++id]={1,x2,y1,y2,1,i}; 
		lsh[++ln]=y1;lsh[++ln]=y2;
	}
	sort(lsh+1,lsh+1+ln);
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=id;i++){
		a[i].l=lower_bound(lsh+1,lsh+1+ln,a[i].l)-lsh;
		a[i].r=lower_bound(lsh+1,lsh+1+ln,a[i].r)-lsh;
	}
	sort(a+1,a+1+id,cmp);
	for(int i=1;i<=id;i++){
		if(a[i].op==0){
			tr.add(a[i].l,a[i].v);
		}
		else{
			ans[a[i].id]+=(tr.find(a[i].r)-tr.find(a[i].l))*a[i].v;
		}
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

4 条题解

基础手动二分

优化

信息

状态

开发

支持

关于

4 条题解

基础手动二分

优化

矩形求和（Rectangle Sum）

信息

状态

开发

支持

关于

还没有账户？

登录