~~%%%%%%%%~~
by thhhty @ 2018-10-19 08:30:14
文文一层cdq也不需要树状数组啊。。您怎么写的。。
```cpp
#include<cstdio>
#include<algorithm>
const int maxn = 3e6+10;
struct qwq {
int x,y,type,ind;
}query[maxn],tmp[maxn];
bool cmp (qwq a,qwq b) {
if(a.x==b.x) {
if(a.y==b.y) {
return a.type<b.type;
}
return a.y<b.y;
}
return a.x<b.x;
}
int n,m;
int cnt = 0;
int ans[maxn];
inline void add(int x,int y,int type,int ind) {
query[cnt].x=x;
query[cnt].y=y;
query[cnt].type=type;
query[cnt].ind=ind;
++cnt;
}
void cdq(int L,int R) {
if(R-L<=1) return;
int M = (R+L)>>1;
cdq(L,M);cdq(M,R);
int q = L,p = M,o=0;
int sum=0;
while(q<M&&p<R) {
if(query[q].y<=query[p].y) {
if(query[q].type==0)
++sum;
tmp[o++]=query[q++];
}
else {
if(query[p].type==1) {
ans[query[p].ind]-=sum;
}else if(query[p].type==2) {
ans[query[p].ind]+=sum;
}
tmp[o++]=query[p++];
}
}
while(q<M) {
tmp[o++]=query[q++];
}
while(p<R) {
if(query[p].type==1) {
ans[query[p].ind]-=sum;
}else if(query[p].type==2) {
ans[query[p].ind]+=sum;
}
tmp[o++]=query[p++];
}
for(int i = 0;i<o;++i) {
query[i+L]=tmp[i];
}
return;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 0;i<n;++i) {
scanf("%d%d",&query[cnt].x,&query[cnt].y);
query[cnt].type=0;
++cnt;
}
for(int i = 0;i<m;++i) {
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add(x1-1,y1-1,2,i);
add(x2,y2,2,i);
add(x1-1,y2,1,i);
add(x2,y1-1,1,i);
}
std::sort(query,query+cnt,cmp);
cdq(0,cnt);
for(int i = 0;i<m;++i) printf("%d\n",ans[i]);
return 0;
}
```
@[敌敌畏](/space/show?uid=65602)
by 文文殿下 @ 2018-12-10 14:07:43
谢谢,仔细观察发现自己看错题了QAQ。
以后刷题的时候做回吧
by 爱喝敌敌畏 @ 2018-12-11 13:02:32