BZOJ-1935: [Shoi2007]Tree 园丁的烦恼（

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=1935

首先二维前缀和是无力的，明显O( n^2 )，在线的二维BIT或SGT就更慢了，所以考虑离线。

明显每个询问都可以拆成前缀和的形式，首先把所有点按y排序，然后从小到大扫一遍，每次将新的点加入到BIT中，顺便处理完这一层y的寻问，然后就没了。。。

代码：

3b292df5e0fe9925124bb52636a85edf8db17105.jpg.png

#include <cstdio>

#include <algorithm>

#include <cstring>

 

using namespace std ;

 

#define MAXN 500010

#define lowbit( x )((- x )& x )

 

void getint(int&t ){

    int ch ;

    for( ch =getchar(  );!( ch >='0'&& ch <='9'); ch =getchar(  ));

    t = ch -'0';

    for( ch =getchar(  ); ch >='0'&& ch <='9'; ch =getchar(  )) t *=10, t += ch -'0';

}

       

void putint(int t ){

    if(! t )putchar('0')

    ;else{

        int ans[20];

        ans[0]=0;

        for(; t ; t /=10) ans[++ ans[0]]= t %10;

        for(int i = ans[0]; i ; i --)putchar('0'+ ans[ i ]);

    }

    putchar('\n');

}

 

struct Bit{

    int a[ MAXN *5], N ;

    

    void Init(int _N ){

        N = _N ;

        for(int i =0; i <= N ; i ++) a[ i ]=0;

    }

    

    void Add(int x ,int y ){

        for(int i = x ; i <= N ; i +=lowbit( i )) a[ i ]+= y ;

    }

    

    int Presum(int x ){

        int rec =0;

        for(int i = x ; i ; i -=lowbit( i )) rec += a[ i ];

        return rec ;

    }

    

    int Sum(int l ,int r ){

        return Presum( r )-Presum( l -1);

    }

    

} bit ;

 

struct point{

    int x , y ;

} loc[ MAXN ];

 

bool cmp( point x , point y ){

    return x.y < y.y ;

}

 

int n , m , que[ MAXN ][4];

int cx[ MAXN *5], cy[ MAXN *5], bx[ MAXN *5], by[ MAXN *5], Vx =0, Vy =0, Nx =0, Ny =0;

 

bool Cmp(int x ,int y ){

    return x < y ;

}

 

int Searchx(int x ){

    int l =1, r = Nx ;

    if( x == bx[ l ])return l ;

    if( x == bx[ r ])return r ;

    while(1){

        int mid =( l + r )>>1;

        if( bx[ mid ]== x )return mid ;

        if( x < bx[ mid ]) r = mid ;else l = mid ;

    }

}

 

int Searchy(int y ){

    int l =1, r = Ny ;

    if( y == by[ l ])return l ;

    if( y == by[ r ])return r ;

    while(1){

        int mid =( l + r )>>1;

        if( by[ mid ]== y )return mid ;

        if( y < by[ mid ]) r = mid ;else l = mid ;

    }

}

 

struct node{

    node *next ;

    int l , r , t , k ;

}*head[ MAXN *5];

 

void Insert(int y ,int l ,int r ,int t ,int k ){

    node *p =new( node );

    p -> l = l , p -> r = r , p -> t = t , p -> k = k , p -> next = head[ y ];

    head[ y ]= p ;

}

 

int ans[ MAXN ][2];

 

int main(  ){

    getint( n ),getint( m );

    for(int i =0; i ++< n ;)getint( loc[ i ].x ),getint( loc[ i ].y );

    sort( loc +1, loc + n +1, cmp );

    for(int i =0; i ++< n ;){

        cx[++ Vx ]= loc[ i ].x , cy[++ Vy ]= loc[ i ].y ;

    }

    for(int i =0; i ++< m ;){

        getint( que[ i ][0]),getint( que[ i ][1]),getint( que[ i ][2]),getint( que[ i ][3]);

        cx[++ Vx ]= que[ i ][0], cx[++ Vx ]= que[ i ][2];

        cy[++ Vy ]= que[ i ][1]-1, cy[++ Vy ]= que[ i ][3];

    }

    sort( cx +1, cx + Vx +1, Cmp ),sort( cy +1, cy + Vy +1, Cmp );

    for(int i =0; i ++< Vx ;)if( i ==1|| cx[ i ]!= cx[ i -1]){

        bx[++ Nx ]= cx[ i ];

    }

    for(int i =0; i ++< Vy ;)if( i ==1|| cy[ i ]!= cy[ i -1]){

        by[++ Ny ]= cy[ i ];

    }

    memset( head ,0,sizeof( head ));

    for(int i =0; i ++< m ;){

        Insert(Searchy( que[ i ][1]-1), que[ i ][0], que[ i ][2], i ,0);

        Insert(Searchy( que[ i ][3]), que[ i ][0], que[ i ][2], i ,1);

    }

    bit.Init( Nx );

    int j =1;

    for(int i =0; i ++< Ny ;){

        for(; j <= n && loc[ j ].y <= by[ i ]; j ++) bit.Add(Searchx( loc[ j ].x ),1);

        for( node *p = head[ i ]; p ; p = p -> next ) ans[ p -> t ][ p -> k ]= bit.Sum(Searchx( p -> l ),Searchx( p -> r ));

    }

    for(int i =0; i ++< m ;)putint( ans[ i ][1]- ans[ i ][0]);

    return 0;

}