1 条题解
-
0Guest LV 0 MOD
-
0
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cmath> using namespace std; int getint() { int i=0,f=1;char c; for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar()); if(c=='-')f=-1,c=getchar(); for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0'; return i*f; } const int N=1e5+5; int n,m,tot,cnt,b[N*6]; long long bit[N*6],ans[N]; struct point { int x,y,val; bool operator <(const point &a)const { return x==a.x?y<a.y:x<a.x; } }a[N]; struct question { int x1,x2,y1,y2; }q[N]; struct halfquestion { int x,y1,y2,pos,k; halfquestion(){} halfquestion(int _x,int _y1,int _y2,int _pos,int _k): x(_x),y1(_y1),y2(_y2),pos(_pos),k(_k){} bool operator <(const halfquestion &a)const { return x<a.x; } }g[N<<1]; void lsh() { sort(b+1,b+cnt+1); cnt=unique(b+1,b+cnt+1)-b-1; for(int i=1;i<=n;i++) { a[i].x=lower_bound(b+1,b+cnt+1,a[i].x)-b; a[i].y=lower_bound(b+1,b+cnt+1,a[i].y)-b; } for(int i=1;i<=m;i++) { q[i].x1=lower_bound(b+1,b+cnt+1,q[i].x1)-b; q[i].y1=lower_bound(b+1,b+cnt+1,q[i].y1)-b; q[i].x2=lower_bound(b+1,b+cnt+1,q[i].x2)-b; q[i].y2=lower_bound(b+1,b+cnt+1,q[i].y2)-b; } } void update(int x,int val) { for(int i=x;i<=cnt;i+=i&(-i)) bit[i]+=val; } long long query(int x) { long long res=0; for(int i=x;i>0;i-=i&(-i)) res+=bit[i]; return res; } int main() { //freopen("lx.in","r",stdin); n=getint(),m=getint(); for(int i=1;i<=n;i++) { b[++cnt]=a[i].x=getint(); b[++cnt]=a[i].y=getint(); a[i].val=getint(); } for(int i=1;i<=m;i++) { b[++cnt]=q[i].x1=getint(),b[++cnt]=q[i].y1=getint(); b[++cnt]=q[i].x2=getint(),b[++cnt]=q[i].y2=getint(); } lsh(); for(int i=1;i<=m;i++) { g[++tot]=halfquestion(q[i].x1-1,q[i].y1,q[i].y2,i,-1); g[++tot]=halfquestion(q[i].x2,q[i].y1,q[i].y2,i,1); } sort(a+1,a+n+1); sort(g+1,g+tot+1); for(int i=1,j=1;i<=tot;i++) { while(j<=n&&a[j].x<=g[i].x) update(a[j].y,a[j].val),j++; ans[g[i].pos]+=(query(g[i].y2)-query(g[i].y1-1))*g[i].k; } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0; }
- 1
信息
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 7
- 已通过
- 2
- 通过率
- 29%
- 上传者