(luogu2184) 贪婪大陆

发表于 分类于 ， ，

[原题链接](luogu.com.cn/problem/P2184

思路:

题目中的操作 1 即为添加一个区间 \([l,r]\), 操作 2 即询问有多少个区间与查询区间 \([l',r']\) 相交.

区间相交的条件即为 \(l \le r' \land r \ge l'\), 计数的时候只需要把 \(l \le r'\) 的区间数量减去 \(r < l'\) 的区间数量即可.

设 \(dl_x\) 表示左端点在 \(x\) 处的区间数量，\(dr_x\) 表示右端点在 \(x\) 处的区间数量，\(cl_x, cr_x\) 分别为 \(dl_x, dr_x\) 的前缀和， 则所求的区间数量为 \(cl_{r'} - cr_{l'-1}\).

\(cl, cr\) 使用树状数组维护即可.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
const int Mn(100500);
inline int lb(int x) {  //lowbit
    return x&(-x);
}

int cl[Mn],cr[Mn];  //树状数组
void add(int c[],int n,int p,int x) {   //修改操作
    while(p<=n) {
        c[p] += x;
        p += lb(p);
    }
}
int sum(int c[],int p) {    //求前缀和
    int ret(0);
    while(p) {
        ret += c[p];
        p -= lb(p);
    }
    return ret;
}

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    while(m--) {
        int q,l,r;
        scanf("%d %d %d",&q,&l,&r);
        if(q==1) {  //修改
            add(cl,n,l,1);
            add(cr,n,r,1);
        } else {    //查询
            printf("%d\n",sum(cl,r)-sum(cr,l-1));
        }
    }
    return 0;
}