超级玛丽

Description

玛丽是世界著名的水管工。他的“魁梧”的身材和惊人的跳跃能力，在我们的记忆中想起。现在可怜的公主又陷入了困境，玛丽需要拯救他的情人。我们把城堡的道路作为一条线（长度是n），在每一个整数点上有一个高Hi的砖块。现在的问题是，在道路[ L，R ]区间马里奥可以跳过的砖块有多少，如果他能跳的最大高度是H。

Input

第一行一个整数T，测试数据的数量。 对于每个测试数据： 第一行包含两个整数n和m，n是路的长度，m是查询的个数。 下一行包含n个整数，每一块砖的高度，范围是[ 0，1000000000 ] 下一个m行，每行包含三个整数L，R，H，如题意。

Output

对每组数据输出”Case X: “（X是从1开始的数据组编号） 其次是M行，每行包含一个整数。第i个整数是第i次查询，玛丽可以跳过的砖头数。

Sample Input

1 10 10 0 5 2 7 5 4 3 8 7 7 2 8 6 3 5 0 1 3 1 1 9 4 0 1 0 3 5 5 5 5 1 4 6 3 1 5 7 5 7 3

Sample Output

Case 1: 4 0 0 3 1 2 0 1 5 1

Hint

1 <= n <=10^5, 1 <= m <= 10^5 0 <= L <= R < n 0 <= H <= 1000000000

题解

可以用主席树水过去，但是不大好写，考虑一种树状数组的离线做法。 将询问按照h排序，遍历一遍每个询问，按照顺序将高度小于等于h的石块的下标加入树状数组，每次的下标[l,r]的区间和就是该询问的答案。 当然离散化是必须的。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define nd(x) (nil + (x)) using namespace std; const int N = 100000 + 10; struct Query{ int l, r, h, pos; int ans; bool operator < (const Query x)const{ return pos < x.pos; } }qry[N]; inline bool cmp(Query a, Query b) { return a.h < b.h; } struct Node{ int h, pos; bool operator < (const Node x)const{ return h < x.h || h == x.h && pos < x.pos; } }a[N]; int n, m; int b[N], c[N]; inline void add(int x){ while(x <= n){ c[x]++; x += x&-x; } } inline int sum(int x){ int cnt = 0; while(x){ cnt += c[x]; x -= x&-x; } return cnt; } inline void in(int &x){ int f = 1; x = 0; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} x *= f; } void init(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) in(a[i].h), b[i] = a[i].h, a[i].pos = i; sort(b+1, b+n+1); b[0] = unique(b+1, b+n+1) - b - 1; for(int i = 1; i <= n; i++) a[i].h = lower_bound(b+1, b+b[0]+1, a[i].h) - b; sort(a+1, a+n+1); int x, t; for(int i = 1; i <= m; i++){ in(qry[i].l); in(qry[i].r); qry[i].l++; qry[i].r++; in(x); t = lower_bound(b+1, b+b[0]+1, x) - b; qry[i].h = x == b[t] ? t : t - 1; qry[i].pos = i; qry[i].ans = 0; } sort(qry+1, qry+m+1, cmp); } void work(){ int tot = 1; for(int i = 1; i <= m; i++){ while(tot <= n && a[tot].h <= qry[i].h) add(a[tot++].pos); qry[i].ans = sum(qry[i].r) - sum(qry[i].l-1); } sort(qry+1, qry+m+1); for(int i = 1; i <= m; i++) printf("%d\n", qry[i].ans); } int main(){ freopen("supermario.in", "r", stdin); freopen("supermario.out", "w", stdout); int t; in(t); for(int i = 1; i <= t; i++){ memset(c, 0, sizeof(c)); printf("Case %d:\n", i); init(); work(); } return 0; }