博客

Description

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……

如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：

K=1，读入l,r表示在l~r之间种上的一种树

K=2，读入l,r表示询问l~r之间能见到多少种树

（l,r>0）

Input

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

接下来m行为m个操作

Output

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

Sample Input

5 4
1 1 3
2 2 5
1 2 4
2 3 5

Sample Output

1
2

Hint

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

60%的数据保证，n <=1000,m<=50000

100%的数据保证，n,m<=50000

分析

这题也是模板题，貌似可以用线段树做，但是我用了树状数组。

这题要开两个树状数组，分别写两个操作函数，表示修改权值和前缀和。

分别修改l域和r域

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef long long ll;
using namespace std;
int n,m,k,l,r,c[100001],a[100001];
int lowbit(int x)
{
	return x&(-x);
}
void change(int x)
{
	for(;x<=n;x+=lowbit(x))
	{
		c[x]++;
	}
}
int ask(int x)
{
	int ans=0;
	for(;x>0;x-=lowbit(x))
	{
		ans+=c[x];
	}
	return ans;
}
void change2(int x)
{
	for(;x<=n;x+=lowbit(x))
	{
		a[x]++;
	}
}
int ask2(int x)
{
	int ans=0;
	for(;x>0;x-=lowbit(x))
	{
	    ans+=a[x];
	}
	return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>k>>l>>r;
    	if(k==1)
    	{
    		change(l);
    		change2(r+1);
    	}
    	else if(k==2)
    	{
    		cout<<ask(r)-ask2(l)<<endl;
    	}
    }
	return 0;
}