DZY 's BLOG

题意：给定n个点，m个询问。每次询问一个矩形内有几个点。坐标范围10^7。

一眼看上去就很水啊。。坐标肯定是要离散化的。。询问跟着一起离散化。。然后以y为第一关键字，x为第二关键字排序。树状数组统计每个点左下角有多少个点。然后加加减减。。

离散化的细节貌似很恶心。。调着调着就A了。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

char buf[20000000],*pt=buf,*o=buf;

inline int getint(){
    int s=0,f=1; while((*pt!='-')&&(*pt<'0'||*pt>'9'))pt++;
    if(*pt=='-')f=-1,pt++; while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48; return s*f;
}
inline void print(int x){
    char str[30],*p=str; if(!x)*o++=48;
    else{ while(x) *p++=x%10+48,x/=10; while(p--!=str)*o++=*p;}
}

struct point{
    int x,y,id;
    point(){
        id = -1;
    };
    point(int _x,int _y,int _id){
        x = _x, y = _y, id = _id;
    }
}p[2800010];

bool cmp(point a,point b){
    if(a.y == b.y){
        if(a.x == b.x)  return a.id < b.id;
        else    return a.x < b.x;
    }
    return a.y < b.y;
}

int n,m,N,P,pc = 0;
int X[810000],Y[810000],bx[810000],by[810000],bit[2800000],cnt[2800000];

void upd(int x){
    for(;x <= N;x += x & -x)    bit[x] ++;
}
int query(int x){
    int r = 0;
    for(;x;x -= x & -x) r += bit[x];
    return r;
}

int main(){
    fread(buf,1,20000000,stdin);
    n = getint(); m = getint();
    bx[0] = by[0] = 0;
    N = n + 1;
    P = (m << 2) + n;
    bx[N] = by[N] = 12345678;
    
    for(int i = 1;i <= n;i ++){
        X[i] = getint();
        Y[i] = getint();
        bx[i] = ++ X[i];  
        by[i] = ++ Y[i];
    }
    sort(bx + 1, bx + n + 1);
    sort(by + 1, by + n + 1);
    int cx = unique(bx , bx + n + 2) - bx -1;
    int cy = unique(by , by + n + 2) - by -1;
    for(int i = 1;i <= n;i ++){
        p[(m << 2) + i - 1].x = upper_bound(bx,bx + cx,X[i]) - bx;
        p[(m << 2) + i - 1].y = upper_bound(by,by + cy,Y[i]) - by;
    }
    int x1,y1,x2,y2,X1,X2,X3,Y1,Y2,Y3;
    for(int i = 1;i <= m;i ++){
        x1=  getint(); y1=getint();x2=getint();y2=getint();
        X1 = upper_bound(bx,bx + cx,x1) - bx;
        X2 = upper_bound(bx,bx + cx,x2) - bx;
        X3 = upper_bound(bx,bx + cx,x2 + 1) - bx;
        Y1 = upper_bound(by,by + cy,y1) - by;
        Y2 = upper_bound(by,by + cy,y2) - by;
        Y3 = upper_bound(by,by + cy,y2 + 1) - by;
        p[pc] = point(X3,Y3,pc ++);
        p[pc] = point(X1,Y3,pc ++);
        p[pc] = point(X3,Y1,pc ++);
        p[pc] = point(X1,Y1,pc ++);
    }
    
    sort(p,p + P,cmp);
    for(int i = 0;i < P;i ++){
        if(~ p[i].id)   cnt[p[i].id] = query(p[i].x);
        else    upd(p[i].x);
    }
    
    for(int i = 1;i <= m;i ++)
       print(cnt[i - 1 << 2] - cnt[(i - 1 << 2) + 1] - cnt[(i - 1 << 2) + 2] + cnt[(i - 1 << 2) + 3]),*o++='\n';
        
    return fwrite(buf,1,o-buf,stdout),0;
}