UPC 2224 Boring Counting ★(山东省第四届ACM程序设计竞赛 tag:线段树)

[题意]给定一个长度为N的数列，M个询问区间[L,R]内大于等于A小于等于B的数的个数.

[题目链接]http://acm.upc.edu.cn/problem.php?id=2224

省赛的时候脑抽想了10min没想出来就看别的题去了= =，赛后又想了10min想出来了并且1Y。。。真嫌弃自己= =。。。

[分析]如果做过询问区间[L,R]内小于H的个数的那道线段树题(HDU 4417 2012年杭州赛区网络赛)那么这题就好想了。那在这里再说一下做法：｛将所有的询问离线读入之后，按H从小到大排序。对于所有的区间数也按从小到大排序，然后根据查询的H，将比H小的点加入到线段树，然后就是一个区间和｝。

那么这题也就简单了。。。按上面方法分别求出区间[L,R]内大于等于A的个数num1和小于等于B的个数num2，然后res = num1 + num2 - [L,R].

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define MID(x,y) ((x+y)>>1)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int MAXN = 50002;
struct Segment_Tree{
    int sum[MAXN n2.a;
}
bool cmp2(queries n1, queries n2){
    return n1.b = 0 && A[j].value >= q[i].a){
                S.update(A[j].position, 1, 1, n, 1);
                j --;
            }
            q[i].num_greater_a = S.query(q[i].l, q[i].r, 1, n, 1);
        }
        sort(q, q+m, cmp2);
        j = 0;
        S.build();
        for (int i = 0; i