问题 C: 校门外的树

问题 C: 校门外的树

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 12
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1688&pid=2

题目描述

校门外有很多树，如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树。

现有两个操作： 

K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同 
K=2，读入l,r表示询问l~r之间能见到多少种树。

注意：每个座位都可以重复种树。

输入

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

输出

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

样例输入

5 4

1 1 3

2 2 5

1 2 4

2 3 5

样例输出

1

2

原理：这里不是记录点数，要把C数组改一改，因为记录的是线段数，需要开2个数组去维护区间，去记录端点，用sum寻找r前有几个前缀端点，再用sum去寻找l-1前有几个后缀端点，减一减就为答案。

代码：

#include<bits/stdc++.h>

using namespace std;

#define maxn 1000000

int A[maxn], C1[maxn], C2[maxn];

int n, m;

int lowbit(int t)//t转换为二进制后，有末尾连续0共k个，返回2^k次方

{

    return t & -t;

}

void add(int x, int y, int *C)//单点修改

{

    for (int i = x; i <= n; i += lowbit(i))

    {

         C[i] += y;

    }

}

int sum(int x, int *C)//区间求和

{

    int ans = 0;

    for (int i = x; i > 0; i -= lowbit(i))

    {

         ans += C[i];

    }

    return ans;

}

int main()

{

    scanf("%d%d", &n, &m);

    while (m--)

    {

         int l, r, k;

         scanf("%d %d %d", &k, &l, &r);

         if (k == 1)

         {

             add(l, 1, C1);

             add(r, 1, C2);

         }

         else

         {

             printf("%d\n", sum(r, C1) - sum(l - 1, C2));

         }

    }

    return 0;

}