hdu 4417 Super Mario (线段树+离线)

题意：

n个砖块，第i个砖块的高度是hi。

m个query，每个query的格式：L R H （输出[L，R]中有多少个hi小于等于H【即玛里奥能跳过多少块砖】）

数据范围：

1 <= n <=10^5, 1 <= m <= 10^5

Next line contains n integers, the height of each brick, the range is [0, 1000000000].

( 0 <= L <= R < n 0 <= H <= 1000000000.)

思路:

对于每个query的H，我只要将n个砖块中比H小的都标记好，然后判断在[L，R]中的标注记好的有多少个即可。

顺着这个思路，将m个query按H降序排列，将n个砖块按h降序排列。

比H小的都根据排序前的id在原数组中的相应位置打上标记，用数状数组统计。

看代码。

代码：

int const maxn=1e5+5;

struct node1{
    int h,p;
}brick[maxn];
struct node2{
    int L,R,H,p;
}Q[maxn];

int T,n,m;
int C[maxn];
int ans[maxn];


bool cmp1(node1 a,node1 b){
    return a.h>b.h;
}
bool cmp2(node2 a,node2 b){
    return a.H>b.H;
}

void add(int p){
    for(int i=p;i<=n;i+=lowbit(i)) C[i]++;
}
int sum(int p){
    int ret=0;
    for(int i=p;i>0;i-=lowbit(i)) ret+=C[i];
    return ret;
}

int main(){
    //freopen("test.in","r",stdin);
    cin>>T;
    rep(t,1,T){
        scanf("%d%d",&n,&m);
        rep(i,1,n){
            scanf("%d",&brick[i].h);
            brick[i].p=i;
        }
        rep(i,1,m){
            scanf("%d%d%d",&Q[i].L,&Q[i].R,&Q[i].H);
            Q[i].p=i;
        }
        sort(brick+1,brick+1+n,cmp1);
        sort(Q+1,Q+1+m,cmp2);


        mem(C,0);

        printf("Case %d:
",t);

        int _p=1;
        rep(i,1,m){
            while(_p<=n && brick[_p].h>Q[i].H){
                add(brick[_p].p);
                ++_p;
            }
            ans[Q[i].p]=Q[i].R-Q[i].L+1-(sum(Q[i].R+1)-sum(Q[i].L));
        }
        rep(i,1,m) printf("%d
",ans[i]);
    }
    //fclose(stdin);
}