贪婪大陆

题目链接

Solution

类似差分的思想。

设要询问的区间是 ([i,j])，我们需要知道 (j) 之前有多少个开头（(s_1)），(i) 之前有多少个结尾（(s_2)），用 (s_1-s_2)，就得到了这个区间有多少种地雷。

这样可以开头和结尾分开维护。至于修改，就维护开头 (+1)，结尾 (+1)，到最后求和即可。

Code

#include <iostream>
#include <cstdio>
#define lowbit(x) (x & (-x))
using namespace std;

int n, m, Q, L, R, tree[2][2333333];
void add(int x, int k) { while(x <= n) tree[k][x]++, x += lowbit(x); }
int query(int x, int k)
{
    int res = 0;
    while(x) res += tree[k][x], x -= lowbit(x);
    return res;
}

int main()
{
    cin >> n >> m;
    while(m--)
    {
        cin >> Q >> L >> R;
        if(Q == 1) add(L, 0), add(R, 1);
        else printf("%d
", query(R, 0) - query(L - 1, 1));
    }
    return 0;
}