喵喵

题目大意

题意

分析

因为每次投喂的猫粮是不同种类

那么对于操作 11 我们可以看作是建立一个线段[l,r][l,r]

对于操作 22 可以看作是查询有多少个已经建立的线段与线段 [l,r][l,r] 重合

转化完问题后

我们发现对于查询有多少个线段重合问题比较难以解决

那么我们就求有多少个线段与要查询的线段不重合

那么我们只需要建立两个树状数组维护左右端点的值就可以了

Code

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
int n,m;
int idx = 0;
int tr[100005][2];
int lwb(int x){
    return x & -x;
}

void upd(int l,int r){
    for(int i = l;i <= n;i+=lwb(i)) tr[i][0]++;
    for(int i = r;i <= n;i+=lwb(i)) tr[i][1]++;
}


int ask(int l,int r){
    int res = 0;
    for(int i = l-1;i;i-=lwb(i)) res += tr[i][1];
    for(int i = n;i;i-=lwb(i)) res += tr[i][0];
    for(int i = r;i;i-=lwb(i)) res -= tr[i][0];
    return idx - res; 
}
signed main()
{
    cin >> n >> m;
    while(m--){
        int p,l,r;
        cin >> p >> l >> r;
        if(p == 1){
            idx++;
            upd(l,r);
        }
        else{
            cout << ask(l,r) << endl;
        }
    }
    return 0;
}