vijos 1448 校门外的树 树状数组

描述

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）

格式

输入格式

第一行n,m表示道路总长为n，共有m个操作
接下来m行为m个操作

输出格式

对于每个k=2输出一个答案

样例1

样例输入1

 

样例输出1

 

限制

1s

提示

范围：20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000

题意：每次使一段区间种一种树，查询一段区间不同树的个数。

思路：开始使用线段树区间染色，发现怎么过都过不了，后来仔细读了题意思是说，一段区间可以重复种树，而且不会覆盖=x=
然后怒而使用树状数组

/** @Date    : 2016-12-13-22.42

  * @Author  : Lweleth ([email protected])

  * @Link    : https://github.com/

  * @Version :

  */

#include<bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int t[50010];

int a[50010];

int n, k;

void add(int x, int *t)

{

    while(x <= n)

    {

        t[x]++;

        x += (-x) & x;

    }

}

int sum(int x, int *t)

{

    int ans = 0;

    while(x)

    {

        ans += t[x];

        x -= (-x) & x;

    }

    return ans;

}

int main()

{

    cin >> n >> k;

    MMF(t);

    MMF(a);

    while(k--)

    {

        int s, x, y;

        cin >> s >> x >> y;

        if(s == 1)

        {

            add(x, a);

            add(y, t);

        }

        else

            printf("%d\n", sum(y, a) - sum(x - 1,t));

    }

    return 0;

}