vijos 1448/SSL 1502_校门外的树_树状数组

发布于 2019-05-15  10 次阅读


题目描述

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


思路

这题是一条条线段,所以我们可以用线段树之类的东东来实现,然后感觉树状数组写起来简单一点所以就打了
开两个数组来存一个是开始的点的数量,一个是结束的
然后随便搞一下,最后输出就可以了


#include 
int a[10001],f[10001],fl[10001];
int n,m;
int add(int x,int y)
{
    while (x<=n)
    {
        f[x]+=y;
        x+=x&(-x);
    }
}
int add1(int x,int y)
{
    while (x<=n)
    {
        fl[x]+=y;
        x+=x&(-x);
    }
}
int count(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=f[x];
        x-=(x&(-x));
    }
    return ans;
}
int count1(int x)
{
    int ans=0;
    while (x>0)
    {
        ans+=fl[x];
        x-=(x&(-x));
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&z,&x,&y);
        if (z==1)
        {
            add(x,1);
            add1(y,1);
        }
        else 
        {
            printf("%d\n",count(y)-count1(x-1));
        }
    }
}
]]>