7 条题解
-
1
离散化+树状数组解：
首先对于范围查询，很容易想到二维前缀和，所以考虑离散化后前缀和。
但这样是过不了全部数据的，毕竟很容易就能造出离散化后仍有 个不同的 与 坐标的数据。
我们思考：对于每一个点，它的前缀和即所有 与 均小于它的点的权值之和加上它自身的权值。 显然可以排序处理，那么目标就是再扫到每一个点时记录前面有多少个 小于自己的点，显然这可以使用树状数组求解。
对于询问，我们找到每一个矩形实际所覆盖的所有点中的左下角与右上角两个点（假设分别为 和 ），那么答案即为 因为进行了离散化，在 与 之间不会存在别的点，所以将上述四个点一同插入到树状数组中并记录答案。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node{ ll x,y,p,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[1000005]; int s[100005],s2[100005]; ll tre[100005]; ll ans[100005]; 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; 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; } -
1
离线二位数点板子
#include<bits/stdc++.h> #define int ll using namespace std; typedef long long ll; int n,m,lsh[1000010],ln; struct N{ int x,y; ll v; }a[1000010]; struct Q{ ll op,x,y1,y2,v,id; }q[1000010]; bool cmp(Q a,Q b){ if(a.x!=b.x)return a.x<b.x; return a.op<b.op; } ll ans[1000010]; int lowbit(int x){ return x&(-x); } struct BIT{ ll tr[1000010]; 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; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y>>a[i].v; lsh[i]=a[i].y; } for(int i=1;i<=m;i++){ int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; lsh[i+n]=y1; lsh[i+n+m]=y2; q[i]={1,x1-1,y1,y2,-1,i}; q[i+m]={1,x2,y1,y2,1,i}; } sort(lsh+1,lsh+1+n+m+m); ln=unique(lsh+1,lsh+1+n+m+m)-lsh-1; for(int i=1;i<=n;i++){ a[i].y=lower_bound(lsh+1,lsh+1+ln,a[i].y)-lsh; q[i+m+m]={0,a[i].x,a[i].y,0,a[i].v,i}; } for(int i=1;i<=m+m;i++){ q[i].y1=lower_bound(lsh+1,lsh+1+ln,q[i].y1)-lsh; q[i].y2=lower_bound(lsh+1,lsh+1+ln,q[i].y2)-lsh; } sort(q+1,q+1+n+m+m,cmp); for(int i=1;i<=n+m+m;i++){ if(q[i].op==0){ tr.add(q[i].y1,q[i].v); } else{ ans[q[i].id]+=q[i].v*(tr.find(q[i].y2)-tr.find(q[i].y1-1)); } } for(int i=1;i<=m;i++){ cout<<ans[i]<<'\n'; } return 0; } -
1
CDQ分治的题解好少啊，明明是二维偏序，为啥楼下CDQ硬是求了个三维
由于所有基站都是在一开始给出，相当于修改操作的时间戳都在询问前面(即每个基站都有可能对询问产生贡献)，这样其实就可以省略时间戳，直接做二维偏序
具体来说就是，x,y坐标分别为一二关键字排序，遇到相同坐标令询问排后面
询问拆成四个的老套路就不讲了，二维偏序不用树状数组，所以也不用离散化，最后注意要开long long
#include<iostream> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef long long lt; lt read() { lt f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return f*x; } const int maxn=1000010; int n,m,tot; struct node{lt x,y,p,opt,k,id,ans;}a[maxn],b[maxn]; lt ans[maxn]; bool cmp(node a,node b) { if(a.x!=b.x) return a.x<b.x; else if(a.y!=b.y) return a.y<b.y; else return a.opt<b.opt; } void CDQ(int ll,int rr) { if(ll==rr) return; int mid=ll+rr>>1; CDQ(ll,mid); CDQ(mid+1,rr); int t1=ll,t2=mid+1,p=ll; lt cnt=0; while(t2<=rr) { while(a[t1].y<=a[t2].y&&t1<=mid){ if(a[t1].opt==1) cnt+=a[t1].p; b[p++]=a[t1++]; } if(a[t2].opt==2) a[t2].ans+=cnt; b[p++]=a[t2++]; } while(t1<=mid) b[p++]=a[t1++]; while(t2<=rr) b[p++]=a[t2++]; for(int i=ll;i<=rr;++i) a[i]=b[i]; } int main() { n=read();m=read(); for(int i=1;i<=n;++i) { int x=read(),y=read();lt p=read(); a[++tot]=(node){x,y,p,1,0,0,0}; } for(int i=1;i<=m;++i) { int aa=read(),b=read(),c=read(),d=read(); a[++tot]=(node){c,d,0,2,1,i,0}; a[++tot]=(node){aa-1,b-1,0,2,1,i,0}; a[++tot]=(node){aa-1,d,0,2,-1,i,0}; a[++tot]=(node){c,b-1,0,2,-1,i,0}; } sort(a+1,a+1+tot,cmp); CDQ(1,tot); for(int i=1;i<=tot;++i) if(a[i].opt==2) ans[a[i].id]+=a[i].k*a[i].ans; for(int i=1;i<=m;++i) printf("%lld\n",ans[i]); return 0; } -
0
taojinghua LV 9 @ 2026-7-17 16:08:21
可持久线段树+离散化+二分
舒适码风版：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e5+10; #define mid ((l+r)>>1) struct node { ll x,y,k; node(ll x1=0,ll y1=0):x(x1),y(y1){} }a[N]; bool cmp(node a,node b){return a.x<b.x;} 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前必须加上& { 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+n+1,cmp); 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); 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; } -
0
提示：可参考 C99 CDQ 分治+前缀和 P3755 [CQOI2017] 老C的任务 。
#include<bits/stdc++.h> #define int long long using namespace std; constexpr int N=1e6+10; int n,m,tot,ans[N]; struct node{ int x,y,p,opt,k,id,ans; bool operator <(const node&A){ return x<A.x||(x==A.x&&(y<A.y||(y==A.y&&opt<A.opt))); } }a[N],b[N]; inline void dfs(int l,int r){//CDQ分治 if(l==r)return; int m=l+r>>1; //分裂 dfs(l,m); dfs(m+1,r); int t1=l,t2=m+1,p=l,cnt=0; while(t2<=r){ while(a[t1].y<=a[t2].y&&t1<=m){ if(a[t1].opt==1)cnt+=a[t1].p; b[p++]=a[t1++]; } if(a[t2].opt==2)a[t2].ans+=cnt; b[p++]=a[t2++]; } while(t1<=m)b[p++]=a[t1++]; while(t2<=r)b[p++]=a[t2++]; for(int i=l;i<=r;i++)a[i]=b[i];//按y排序 } signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ int x,y,p; cin>>x>>y>>p; a[++tot]={x,y,p,1,0,0,0}; } for(int i=1;i<=m;i++){//拆分为4个点 int k,l,m,n; cin>>k>>l>>m>>n; a[++tot]={m,n,0,2,1,i,0}; a[++tot]={k-1,l-1,0,2,1,i,0}; a[++tot]={k-1,n,0,2,-1,i,0}; a[++tot]={m,l-1,0,2,-1,i,0}; } sort(a+1,a+tot+1);//按x排序 dfs(1,tot);//CDQ分治 for(int i=1;i<=tot;i++) if(a[i].opt==2) ans[a[i].id]+=a[i].k*a[i].ans; for(int i=1;i<=m;i++)//统计答案 cout<<ans[i]<<"\n"; return 0; } -
-1
70分代码,做法二分,时间复杂度n*m,记得关闭同步流
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct node{int x,y,p;}a[N]; int cmp(node x, node y){return x.x==y.x?x.y<y.y:x.x<y.x;} signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m;cin>>n>>m; for (int i=1;i<=n;i++)cin>>a[i].x>>a[i].y>>a[i].p; sort(a+1,a+n+1,cmp); while(m--) { int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2; int l=0,r=n+1,ans=0; while(l+1<r) { int mid=(l+r)/2; if (a[mid].x>=x1){ r=mid; } else { l=mid; } } ans=r; l=0,r=n+1; int ans1=0; while (l+1<r) { int mid=(l+r)/2; if(a[mid].x<=x2) { l=mid; } else { r=mid; } } ans1=l; long long sum=0; for(int i=ans;i<=ans1;i++) { int t=a[i].y; if(t>=y1&&t<=y2)sum+=a[i].p; } cout<<sum<<"\n"; } return 0; } -
-1
huangzheng
LV 6
@ 2025-10-8 17:11:45
C60 可持久化线段树+离散化+二分 P3755 [CQOI2017] 老C的任务
#include <iostream> #include <cstring> #include <algorithm> using namespace std; void read(int &x){ //快读 x=0;int f=1;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-'0',c=getchar();} x*=f; } typedef long long ll; const int N=100005; #define mid ((l+r)>>1) struct node{ int x,y,p; //p:权值 node(int x1=0,int y1=0):x(x1),y(y1){} bool operator<(const node &b)const{return x<b.x;} }a[N]; int n,m,y[N]; int root[N],tot; //根节点,开点个数 int ls[N*20],rs[N*20]; ll sum[N*20]; //sum:区间权值的前缀和 void change(int &u,int v,int l,int r,int y,int 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(int u,int l,int r,int x,int 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(){ read(n);read(m); int x1,y1,x2,y2; for(int i=1;i<=n;i++) read(a[i].x),read(a[i].y),read(a[i].p); for(int i=1;i<=n;i++) y[i]=a[i].y; sort(y+1,y+1+n); int yn=unique(y+1,y+1+n)-y-1; for(int i=1;i<=n;i++) //y值离散化 a[i].y=lower_bound(y+1,y+1+yn,a[i].y)-y; sort(a+1,a+1+n); //按x排序 for(int i=1;i<=n;i++) //持久树:版本对应x的下标 change(root[i],root[i-1],1,yn,a[i].y,a[i].p); while(m--){ read(x1),read(y1),read(x2),read(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)); } }
- 1
