裸题...
依旧是写了BIT和线段树两种（才不是写完线段树后才想起来可以写BIT呢
怎么卡常数都挺大...QAQ ccz和yy的写法好快哇%%%
BIT：
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int maxn=500010,inf=1e9;
struct poi{int fir,sec,trd,ty,pos,w;}a[maxn];
int n,m,x,y,z,cnt,N,x1,x2,y1,y2;
int b[maxn];
ll tree[maxn],ans[maxn];
void read(int &k)
{
int f=1;k=0;char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
k*=f;
}
inline bool cmp(poi a,poi b){return a.fir==b.fir?a.ty<b.ty:a.fir<b.fir;}
inline int lowbit(int x){return x&-x;}
inline void add(int x,int delta){for(;x<=N;x+=lowbit(x))tree[x]+=delta;}
inline ll query(int x){ll sum=0;for(;x;x-=lowbit(x))sum+=tree[x];return sum;}
int main()
{
read(n);read(m);cnt=n;
for(int i=1;i<=n;i++)
{
read(x);read(y);read(z);
a[i].fir=x;a[i].sec=y;a[i].w=z;b[++N]=y;
}
for(int i=1;i<=m;i++)
{
read(x1);read(y1);read(x2);read(y2);
a[++cnt].fir=x1;a[cnt].sec=y1;a[cnt].trd=y2;a[cnt].ty=-1;a[cnt].pos=i;
a[++cnt]=a[cnt-1];a[cnt].fir=x2;a[cnt].ty=1;b[++N]=y1;b[++N]=y2;
}
sort(b+1,b+1+N);
for(int i=1;i<=n;i++)a[i].sec=lower_bound(b+1,b+1+N,a[i].sec)-b;
for(int i=n+1;i<=cnt;i+=2)
{
a[i].sec=a[i+1].sec=lower_bound(b+1,b+1+N,a[i].sec)-b;
a[i].trd=a[i+1].trd=lower_bound(b+1,b+1+N,a[i].trd)-b;
}
sort(a+1,a+1+cnt,cmp);
for(int i=1;i<=cnt;i++)
{
if(a[i].ty)
{
ll sum=query(a[i].trd)-query(a[i].sec-1);
ans[a[i].pos]+=(a[i].ty==1?sum:-sum);
}
else add(a[i].sec,a[i].w);
}
for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
return 0;
}
线段树：
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#define ll long long
using namespace std;
const int maxn=500010,inf=1e9;
struct poi{int fir,sec,trd,ty,pos,w;}a[maxn];
int n,m,x,y,z,cnt,N,x1,x2,y1,y2;
int b[maxn];
ll tree[maxn*4],ans[maxn];
void read(int &k)
{
int f=1;k=0;char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
k*=f;
}
inline bool cmp(poi a,poi b){return a.fir==b.fir?a.ty<b.ty:a.fir<b.fir;}
inline void pushup(int x){tree[x]=tree[x<<1]+tree[x<<1|1];}
inline void add(int x,int l,int r,int cx,int delta)
{
if(l==r){tree[x]+=delta;return;}
int mid=(l+r)>>1;
if(cx<=mid)add(x<<1,l,mid,cx,delta);
else add(x<<1|1,mid+1,r,cx,delta);
pushup(x);
}
inline ll query(int x,int l,int r,int cl,int cr)
{
if(cl<=l&&r<=cr)return tree[x];
int mid=(l+r)>>1;ll ret=0;
if(cl<=mid)ret+=query(x<<1,l,mid,cl,cr);
if(cr>mid)ret+=query(x<<1|1,mid+1,r,cl,cr);
return ret;
}
int main()
{
read(n);read(m);cnt=n;
for(int i=1;i<=n;i++)
{
read(x);read(y);read(z);
a[i].fir=x;a[i].sec=y;a[i].w=z;b[++N]=y;
}
for(int i=1;i<=m;i++)
{
read(x1);read(y1);read(x2);read(y2);
a[++cnt].fir=x1;a[cnt].sec=y1;a[cnt].trd=y2;a[cnt].ty=-1;a[cnt].pos=i;
a[++cnt]=a[cnt-1];a[cnt].fir=x2;a[cnt].ty=1;b[++N]=y1;b[++N]=y2;
}
sort(b+1,b+1+N);
for(int i=1;i<=n;i++)a[i].sec=lower_bound(b+1,b+1+N,a[i].sec)-b;
for(int i=n+1;i<=cnt;i+=2)
{
a[i].sec=a[i+1].sec=lower_bound(b+1,b+1+N,a[i].sec)-b;
a[i].trd=a[i+1].trd=lower_bound(b+1,b+1+N,a[i].trd)-b;
}
sort(a+1,a+1+cnt,cmp);
for(int i=1;i<=cnt;i++)
{
if(a[i].ty)
{
ll sum=query(1,1,N,a[i].sec,a[i].trd);
ans[a[i].pos]+=(a[i].ty==1?sum:-sum);
}
else add(1,1,N,a[i].sec,a[i].w);
}
for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
return 0;
}
在yy大爷的指导下卡了一波常...艹上了#7，但是写得丑还是写得丑比yy大爷还是慢不少
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<map> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int fir,sec,trd,ty,pos;}a[maxn]; int n,m,x,y,z,cnt,N,x1,x2,y1,y2; int b[maxn],w[maxn]; ll tree[maxn],ans[maxn]; char buf[10000007],*ptr=buf-1; int read() { int x=0,f=1,c=*++ptr; while(c<48)c=='-'&&(f=-1),c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x*f; } inline bool cmp(poi a,poi b){return a.fir==b.fir?a.ty<b.ty:a.fir<b.fir;} inline int lowbit(int x){return x&-x;} inline void add(int x,int delta){for(;x<=N;x+=lowbit(x))tree[x]+=delta;} inline ll query(int x){ll sum=0;for(;x;x-=lowbit(x))sum+=tree[x];return sum;} int main() { fread(buf,1,sizeof(buf),stdin)[buf]=0; n=read();m=read();cnt=n; for(int i=1;i<=n;i++) { x=read();y=read();w[i]=read(); a[i].fir=x;a[i].sec=y;a[i].pos=i;b[++N]=y; } for(int i=1;i<=m;i++) { x1=read();y1=read();x2=read();y2=read(); a[++cnt].fir=x1;a[cnt].sec=y1;a[cnt].trd=y2;a[cnt].ty=-1;a[cnt].pos=i; a[++cnt]=a[cnt-1];a[cnt].fir=x2;a[cnt].ty=1; } sort(b+1,b+1+N); for(int i=1;i<=n;i++)a[i].sec=lower_bound(b+1,b+1+N,a[i].sec)-b; for(int i=n+1;i<=cnt;i+=2) { a[i].sec=a[i+1].sec=lower_bound(b+1,b+1+N,a[i].sec)-b; a[i].trd=a[i+1].trd=upper_bound(b+1,b+1+N,a[i].trd)-b-1; } sort(a+1,a+1+cnt,cmp); for(int i=1;i<=cnt;i++) { if(a[i].ty) { ll sum=query(a[i].trd)-query(a[i].sec-1); ans[a[i].pos]+=(a[i].ty==1?sum:-sum); } else add(a[i].sec,w[a[i].pos]); } for(int i=1;i<=m;i++)printf("%lld ",ans[i]); return 0; }