BZOJ1935: [Shoi2007]Tree 园丁的烦恼【树状数组+离散化】

dzy posted @ 2013年7月30日 16:42 in BZOJ with tags BZOJ 树状数组 离散化 , 1972 阅读

题意:给定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;
}
Avatar_small
Digital Ali 说:
2021年9月06日 17:07

I visit your blog regularly and recommend it to all of those who wanted to enhance their knowledge with ease. The style of writing is excellent and also the content is top-notch. Thanks for that shrewdness you provide the readers! 123movies.com


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter