(luogu2184)贪婪大陆

发表于 | 分类于 ， ，

原题链接

思路:

题目中的操作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;
}