SPOJ--K-query （线段树离线）离线操作解决一些问题

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　K-query

Given a sequence of n numbers a₁, a₂, ..., a_n and a number of k- queries. A k-query is a triple (i, j, k) (1 ≤ i ≤ j ≤ n). For each k-query (i, j, k), you have to return the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j.

Input

Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
Line 3: q (1 ≤ q ≤ 200000), the number of k- queries.
In the next q lines, each line contains 3 numbers i, j, k representing a k-query (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ 10⁹).

Output

For each k-query (i, j, k), print the number of elements greater than k in the subsequence a_i, a_i+1, ..., a_j in a single line.

Example

Input

5

5 1 2 3 4

3

2 4 1

4 4 4

1 5 2 

Output

2

0

3 

题意：给定 一个数组， q次询问， 每次询问区间[L, R]内大于k的数字有多少个。

这题算是比较老比较水的题目了， 但是感觉 离线可以处理 很多 大量询问的问题。 其中思想很值得挖掘学习。
比如这题，先考虑线段树，这棵线段树的叶子都是1，  先把 所有询问按k的大小从小到大排序， 然后对于 每个询问可以把 小于当前询问k的数字的位置在线段树里置0，那么结果就是线段树的区间 求和问题来了。  这样Q次询问， 最终所有数字都加进来了 复杂度 并不高 O( N + Q * log N）

 const int MAXN = 3e4+;

 const int MAXQ = 2e5+;

 struct Node{

     int L, R, k, idx;

     Node (int L = , int R = , int k = , int idx = ):

         L(L), R(R), k(k), idx(idx){}

     bool operator < (const Node &rhs)const{

         return k < rhs.k;

     }

 }Q[MAXQ];

 int sum[MAXN << ];

 void build (int l, int r, int pos){

     if (l == r){

         sum[pos] = ;

         return;

     }

     int mid = (l + r) >> ;

     build(l, mid, pos<<);

     build(mid+, r, pos<<|);

     sum[pos] = sum[pos<<] + sum[pos<<|];

 }

 void update (int l, int r, int pos, int x, int val){

     if (l == r){

         sum[pos] = val;

         return;

     }

     int mid = (l + r) >> ;

     if (x <= mid){

         update(l, mid, pos<<, x, val);

     }else{

         update(mid+, r, pos<<|, x, val);

     }

     sum[pos] = sum[pos<<] + sum[pos<<|];

 }

 int query (int l, int r, int pos, int ua, int ub){

     if (ua <= l && ub >= r){

         return sum[pos];

     }

     int mid = (l + r) >> ;

     int res = ;

     if (ua <mid){

         res += query(l, mid, pos<<, ua, ub);

     }

     if (ub > mid){

         res += query(mid+, r, pos<<|, ua, ub);

     }

     return res;

 }

 int ans[MAXQ], IDX[MAXN], val[MAXN];

 bool cmp(int i, int j){

     return val[i] < val[j];

 }

 int main() {     int n, q;

     while (~ scanf ("%d", &n)){

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

             scanf ("%d", val+i);

             IDX[i] = i;

         }

         sort (IDX, IDX+n, cmp);

         scanf ("%d", &q);

         for (int i = ; i < q; i++){

             int ua, ub, k;

             scanf ("%d%d%d", &ua, &ub, &k);

             Q[i] = Node(ua, ub, k, i);

         }

         sort (Q, Q+q);

         build(, n, );

         int p = ;

         for (int i = ; i < q; i++){

             while (p < n && val[IDX[p]] <= Q[i].k){

                 update(, n, , IDX[p]+, );

                 p++;

             }

             ans[Q[i].idx] = query(, n, , Q[i].L, Q[i].R);

         }

         for (int i = ; i < q; i++){

             printf("%d\n", ans[i]);

         }

     }

     return ;

 }

再来看15年编程之美复赛的一道题。

你正在和小冰玩一个猜数字的游戏。小冰首先生成一个长为N的整数序列A1, A2, …, AN。在每一轮游戏中，小冰会给出一个区间范围[L, R]，然后你要猜一个数K。如果K在AL, AL+1, …, AR中，那么你获胜。

在尝试了几轮之后，你发现这个游戏太难（无聊）了。小冰决定给你一些提示，你每猜一次，小冰会告诉你K与AL, AL+1, …, AR中最接近的数的绝对差值，即min(|Ai - K|), L ≤ i ≤ R。

也是一个数组，多次询问，每次求区间内与k最接近的数字。 
这题 可以可持久化线段树做， 但是代码量大， 除此之外还可以 离线+线段树， 最接近k的值 要么比k小 要么比k大。
先考虑比k小的时候， 首先 把 所有数字和询问放到一起排序，按值排序， 把询问和数字 分开， 然后 从小到大加入到线段树， 那么对于某次询问[L, R]此时线段树的区间[L, R]最大值就是比k小的最接近的k的值， 同理可以求出比k大的最接近k的值。然后两者比较即可。 代码略。

巴特西

SPOJ--K-query （线段树离线）离线操作解决一些问题

Input

Output

Example

最新文章

热门文章

巴特西

SPOJ--K-query （线段树离线） 离线操作解决一些问题

Input

Output

Example

最新文章

热门文章

SPOJ--K-query （线段树离线）离线操作解决一些问题