4105.   

Lines Counting

---

Time Limit: 2.0 Seconds   

Memory Limit: 150000K

Total Runs: 152   

Accepted Runs: 47

---

On the number axis, there are N lines. The two endpoints L and R of each line are integer. Give you M queries, each query contains two intervals: [L1,R1] and [L2,R2], can you count how many lines satisfy this property: L1≤L≤R1 and L2≤R≤R2?

Input

First line will be a positive integer N (1≤N≤100000) indicating the number of lines. Following the coordinates of the N lines' endpoints L and R will be given (1≤L≤R≤100000). Next will be a positive integer M (1≤M≤100000) indicating the number of queries. Following the four numbers L1,R1,L2 and R2 of the M queries will be given (1≤L1≤R1≤L2≤R2≤100000).

Output

For each query output the corresponding answer.

Sample Input

31 32 43 521 2 3 41 4 5 6

Sample Output

21

 

 

题目链接：

题意就是在给你N条在X轴上的线段，求左端点在L1~R1且右端点在L2~R2的线段条数，其实这题跟NBUT上一道题很像，问你在区间L1~R1中，值在L2~R2中有几个数，只是这题在起点计数回退时可能多退几个位子，因为线段的起点和终点坐标可能有重复的，都不能算进去，因此要用while语句来操作。离线树状数组是什么个意思呢？就是要满足区间减法，这样的话就可以这样计数：在遇到询问左端点时时减去$[起点,询问区间左端点-1]$对该询问产生的影响值count1，在遇到询问右端点时加上$[起点,询问区间右端点]$对该询问的影响值count2，这样可以发现count1其实是count2的子集，一加一减一定会把count1抵消掉，只留下刚好符合询问区间的答案了。画了个图助于理解

代码：

#include 
     
      #include 
      
       using namespace std;#define INF 0x3f3f3f3f#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)#define CLR(arr,val) memset(arr,val,sizeof(arr))#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);typedef pair
       
         pii;typedef long long LL;const double PI = acos(-1.0);const int N = 100010;struct Line{    int l, r;    bool operator<(const Line &rhs)const    {        if (l != rhs.l)            return l < rhs.l;        return r < rhs.r;    }};struct query{    int k, r1, r2, flag, id;    query(int _k = 0, int _r1 = 0, int _r2 = 0, int _flag = 0, int _id = 0): k(_k), r1(_r1), r2(_r2), flag(_flag), id(_id) {}    bool operator<(const query &rhs)const    {        return k < rhs.k;    }};Line line[N];query Q[N << 1];int T[N], ans[N];void init(){    CLR(T, 0);    CLR(ans, 0);}void add(int k, int v){    while (k < N)    {        T[k] += v;        k += (k & -k);    }}int getsum(int k){    int ret = 0;    while (k)    {        ret += T[k];        k -= (k & -k);    }    return ret;}int main(void){    int n, m, i;    while (~scanf("%d", &n))    {        init();        for (i = 0; i < n; ++i)            scanf("%d%d", &line[i].l, &line[i].r);        sort(line, line + n);        scanf("%d", &m);        int qcnt = 0;        for (i = 0; i < m; ++i)        {            int l1, r1, l2, r2;            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);            Q[qcnt++] = query(l1, l2, r2, 0, i);            Q[qcnt++] = query(r1, l2, r2, 1, i);        }        sort(Q, Q + qcnt);        int x = 0;        for (i = 0; i < qcnt; ++i)        {            while (line[x].l <= Q[i].k && x < n)                add(line[x++].r, 1);            if (Q[i].flag)                ans[Q[i].id] += getsum(Q[i].r2) - getsum(Q[i].r1 - 1);            else            {                while (line[x - 1].l >= Q[i].k && x - 1 >= 0)                {                    add(line[x - 1].r, -1);                    --x;                }                ans[Q[i].id] -= getsum(Q[i].r2) - getsum(Q[i].r1 - 1);                while (line[x].l <= Q[i].k && x < n)                {                    add(line[x].r, 1);                    ++x;                }            }        }        for (i = 0; i < m; ++i)            printf("%d\n", ans[i]);    }    return 0;}