HDU4117

离线处理线段树

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std ;

#pragma comment(linker, "/STACK:1024000000,1024000000")
#define KEY_TREE ch[ ch[root][1] ][0]
#define lson l , m , rt<<1
#define rson m+1 , r , rt<<1|1
#define lowbit(x)  (x&(-x))
#define pb push_back

template<typename T> T Max( T a , T b ) { return a > b ? a : b ; }
template<typename T> T Min( T a , T b ) { return a < b ? a : b ; }
template<typename T> T Abs( T A ) { return A > 0 ? A : -1*A ; }
template<typename T>void Swap( T &a , T &b) { T tmp = a ; a=b ; b = tmp ; }

typedef pair<int , int> pii ;
typedef long long llong ;

const llong LINF = 0x3FFFFFFFFFFFFFFLL ;
const int INF = 0X3FFFFFFF ;
const int MAXN = 1e5+10 ;

struct Node
{
    int l ;
    int r ;
    int h ;
    int id ;
    bool operator < (const Node &b) const
    {
        if ( h != b.h)
            return h < b.h ;
        if ( r != b.r )
            return r < b.r ;
        return l < b.r ;
    }
} nd[MAXN] ;

struct Hei
{
    int h ;
    int id ;
    bool operator < (const Hei &b) const
    {
        if ( h != b.h )
            return h < b.h ;
        return id < b.id ;
    }
} H[MAXN] ;

int res[MAXN] ;

int cnt[MAXN<<2] ;
void Build(int l , int r , int rt)
{
    cnt[rt] = 0 ;
    if (l == r) return ;
    int m = (l+r)>>1 ;
    Build(lson) ;
    Build(rson) ;
}

void Modify(int pos , int l , int r , int rt)
{
    if (l == r)
    {
        cnt[rt] = 1;
        return ;
    }
    int m = (l+r)>>1 ;
    if (pos <= m)
        Modify( pos , lson);
    else Modify(pos , rson);
    cnt[rt]++ ;
}

int Query( int left , int right , int l , int r , int rt)
{
    if ( left <= l && r <= right )
    {
        return cnt[rt] ;
    }
    int m = (l+r)>>1;
    int res = 0 ;
    if (left <= m) res += Query(left , right , lson) ;
    if (m < right) res += Query(left , right , rson) ;
    return res ;
}

int main()
{
    int T;
    scanf("%d", &T) ;
    for ( int nca = 1 ; nca <= T; nca++ )
    {
        int n , m ;
        scanf("%d%d", &n, &m) ;

        for ( int i = 0  ; i < n ; i++ )
            scanf("%d", &H[i].h) , H[i].id = i+1 ;
        sort(H , H+n) ;

        for ( int i = 0 ; i < m ; i++ )
            scanf("%d%d%d", &nd[i].l , &nd[i].r , &nd[i].h) ,nd[i].l++ , nd[i].r++ , nd[i].id = i+1 ;
        sort(nd , nd+m) ;

        Build(1, n , 1) ;

        int now_id = 0 ;
        for ( int i = 0 ; i < m;  i++ )
        {
            while ( H[now_id].h <= nd[i].h && now_id < n )
                Modify( H[now_id++].id , 1 , n , 1) ;

            res[ nd[i].id ] = Query( nd[i].l , nd[i].r , 1 , n , 1) ;

        }

        printf("Case %d:\n",  nca) ;
        for ( int i = 1 ; i <= m; i++ )
            printf("%d\n" , res[i]) ;

    }
    return 0 ;
}