VIJOS 1448

树状数组

VIJOS

大概就是用树状数组来维护。

每次用区间 $[1,r]$ ，中的树的种类数减去 $[1,l-1]$ 中完全在这个区间中的种类数就是答案了。

那么每次维护两个树状数组，一个维护左端点的个数，一个维护右端点的个数。

#include <iostream>
#include <cstdio>
const int MAXN = 5e4 + 5;
int N, M;
int BIT[2][MAXN];
inline int read()
{
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void Modify(int t, int x)
{
    while(x <= N)
    {
        ++BIT[t][x];
        x += x & (-x);
    }
}
inline int Query(int t, int x)
{
    int res = 0;
    while(x > 0)
    {
        res += BIT[t][x];
        x -= x & (-x);
    }
    return res;
}
int main()
{
    N = read();
    M = read();
    while(M--)
    {
        int opt = read(), l = read(), r = read();
        if(opt == 1)
        {
            Modify(0, l);
            Modify(1, r);   
        }
        else printf("%d\n", Query(0, r) - Query(1, l - 1));
    }
    return 0;
}