此题本来是一个很好的二维线段树模板题，然而居然卡空间（至少洛谷上是的）。
以下是二维线段树写法（大概70分）：
#include <bits/stdc++.h> #define gc getchar() #define N 100009 #define M 16000009 #define mp make_pair #define pb push_back #define sz(x) (int)x.size() #define root 1,1,MaxN #define Root rt[cur],1,MaxM #define NOW int cur,int l,int r #define Now int &cur,int l,int r #define mid (l+r>>1) #define lc cur<<1 #define rc lc|1 #define lson lc,l,mid #define rson rc,mid+1,r #define Lson ls[cur],l,mid #define Rson rs[cur],mid+1,r #define ll long long using namespace std; ll p[N],sum[M]; int n,m,x[N],y[N],MaxN,MaxM,rt[N<<2],ls[M],rs[M],cnt; vector<int> X,Y; int read() { char ch; int x=1; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } void Ins(Now,int y,ll p) { if (!cur) cur=++cnt; sum[cur]+=p; if (l==r) return; if (y<=mid) Ins(Lson,y,p); else Ins(Rson,y,p); } void ins(NOW,int x,int y,ll p) { Ins(Root,y,p); if (l==r) return; if (x<=mid) ins(lson,x,y,p); else ins(rson,x,y,p); } ll Qry(Now,int L,int R) { if (!cur) return 0; if (L<=l&&R>=r) return sum[cur]; ll ans=0; if (L<=mid) ans+=Qry(Lson,L,R); if (R>mid) ans+=Qry(Rson,L,R); return ans; } ll qry(NOW,int l1,int r1,int l2,int r2) { if (l1>r1||l2>r2||r1==0||r2==0||l1==MaxN+1||l2==MaxM+1) return 0ll; if (l1<=l&&r1>=r) return Qry(Root,l2,r2); ll ans=0; if (l1<=mid) ans+=qry(lson,l1,r1,l2,r2); if (r1>mid) ans+=qry(rson,l1,r1,l2,r2); return ans; } int main() { n=read(),m=read(); for (int i=1;i<=n;i++) { x[i]=read(),y[i]=read(),p[i]=read(); X.pb(x[i]),Y.pb(y[i]); } sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); X.erase(unique(X.begin(),X.end()),X.end()); Y.erase(unique(Y.begin(),Y.end()),Y.end()); MaxN=sz(X),MaxM=sz(Y); for (int i=1;i<=n;i++) { x[i]=lower_bound(X.begin(),X.end(),x[i])-X.begin()+1; y[i]=lower_bound(Y.begin(),Y.end(),y[i])-Y.begin()+1; ins(root,x[i],y[i],p[i]); } for (int i=1;i<=m;i++) { int x1=read(),y1=read(),x2=read(),y2=read(); x1=lower_bound(X.begin(),X.end(),x1)-X.begin()+1; y1=lower_bound(Y.begin(),Y.end(),y1)-Y.begin()+1; x2=upper_bound(X.begin(),X.end(),x2)-X.begin(); y2=upper_bound(Y.begin(),Y.end(),y2)-Y.begin(); printf("%lld\n",qry(root,x1,x2,y1,y2)); } return 0; }然后另外一种显然就是离线拆询问+扫描线+树状数组啦： #include <bits/stdc++.h> #define gc getchar() #define N 100009 #define M 16000009 #define mp make_pair #define pb push_back #define sz(x) (int)x.size() #define root 1,1,MaxN #define Root rt[cur],1,MaxM #define NOW int cur,int l,int r #define Now int &cur,int l,int r #define mid (l+r>>1) #define lc cur<<1 #define rc lc|1 #define lson lc,l,mid #define rson rc,mid+1,r #define Lson ls[cur],l,mid #define Rson rs[cur],mid+1,r #define ll long long using namespace std; ll p[N],sum[M],ans[N]; int n,m,x[N],y[N],MaxN,MaxM,cnt; vector<int> X,Y; struct coordinate { int x,y; ll p; coordinate(int x=0,int y=0,ll p=0):x(x),y(y),p(p){} }point[N]; bool operator <(const coordinate &a,const coordinate &b) { return a.x<b.x; } struct node { int x,l,r,pos; node(int x=0,int l=0,int r=0,int pos=0):x(x),l(l),r(r),pos(pos){} }q[N<<1]; bool operator <(const node &a,const node &b) { return a.x<b.x; } int read() { char ch; int x=1; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } int lowbit(int x) { return x&(-x); } void add(int x,ll y) { for (;x<=n;x+=lowbit(x)) sum[x]+=y; } ll qry(int x) { ll ans=0; for (;x;x-=lowbit(x)) ans+=sum[x]; return ans; } int main() { n=read(),m=read(); for (int i=1;i<=n;i++) { x[i]=read(),y[i]=read(),p[i]=read(); X.pb(x[i]),Y.pb(y[i]); } sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); X.erase(unique(X.begin(),X.end()),X.end()); Y.erase(unique(Y.begin(),Y.end()),Y.end()); MaxN=sz(X),MaxM=sz(Y); for (int i=1;i<=n;i++) { x[i]=lower_bound(X.begin(),X.end(),x[i])-X.begin()+1; y[i]=lower_bound(Y.begin(),Y.end(),y[i])-Y.begin()+1; point[i]=coordinate(x[i],y[i],p[i]); } sort(point+1,point+n+1); for (int i=1;i<=m;i++) { int x1=read(),y1=read(),x2=read(),y2=read(); x1=lower_bound(X.begin(),X.end(),x1)-X.begin()+1; y1=lower_bound(Y.begin(),Y.end(),y1)-Y.begin()+1; x2=upper_bound(X.begin(),X.end(),x2)-X.begin(); y2=upper_bound(Y.begin(),Y.end(),y2)-Y.begin(); q[++cnt]=node(x1-1,y1,y2,i); q[++cnt]=node(x2,y1,y2,i); } sort(q+1,q+cnt+1); int now=1; for (int i=1;i<=cnt;i++) { while (point[now].x<=q[i].x&&now<=n) add(point[now].y,point[now].p),now++; if (!ans[q[i].pos]) ans[q[i].pos]=qry(q[i].r)-qry(q[i].l-1); else ans[q[i].pos]=qry(q[i].r)-qry(q[i].l-1)-ans[q[i].pos]; } for (int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; } （就不能开512MB的空间吗？？？）