1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct BIT {
LL n,c[maxn*5];
#define Lowbit(x) x&(-x)
void init(LL n) {
this->n=n;
memset(c,0,sizeof(c));
}
void add(LL x,LL v) {
for(int i=x; i<=n; i+=Lowbit(i))c[i]+=v;
}
LL sum(LL x) {
LL ans=0;
for(int i=x; i; i-=Lowbit(i))ans+=c[i];
return ans;
}
} bit;
LL n,k,a[maxn*3],sum[maxn*3],cnt,tot;
map<LL,LL>M;
void Discretization() {
M.clear();
for(int i=1; i<=cnt; i++)M[a[i]]=1;
LL i=1;
for(map<LL,LL>::iterator it=M.begin(); it!=M.end(); it++,i++)it->second=i;
}
struct Point {
LL x,y,v,id,bj;
bool operator < (const Point& b) const {
return x<b.x||(x==b.x&&y<b.y);
}
} p[maxn*5];
int main() {
n=Get_Int();
k=Get_Int();
for(int i=1; i<=n; i++) {
p[i].x=Get_Int();
p[i].y=Get_Int();
p[i].v=Get_Int();
a[i]=p[i].y;
}
cnt=tot=n;
for(int i=1; i<=k; i++) {
LL xx=Get_Int(),yy=Get_Int(),x2=Get_Int(),y2=Get_Int();
p[++tot]={xx-1,yy-1,0,i,1};
p[++tot]={xx-1,y2,0,i,-1};
p[++tot]={x2,yy-1,0,i,-1};
p[++tot]={x2,y2,0,i,1};
a[++cnt]=yy-1;
a[++cnt]=y2;
}
sort(p+1,p+tot+1);
Discretization();
bit.init(cnt);
for(int i=1; i<=tot; i++) {
if(p[i].v)bit.add(M[p[i].y],p[i].v);
else sum[p[i].id]+=bit.sum(M[p[i].y])*p[i].bj;
}
for(int i=1; i<=k; i++)printf("%lld\n",sum[i]);
return 0;
}
|
