(未完待续)
题目链接:Vijos P1448/LibreOJ 10115/TYVJ 1473(Joyoi)/信息学奥赛一本通 T1537。
题目
题目描述
校门外有很多树,学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两种操作:
- $K=1$,读入 $l,r$ 表示在 $l$ 到 $r$ 之间种上一种树,每次操作种的树的种类都不同;
- $K=2$,读入 $l,r$ 表示询问 $l$ 到 $r$ 之间有多少种树。
注意:每个位置都可以重复种树。
题解
思路
两个树状数组就可以解决这道题。
代码
#include<cstdio>
typedef long long ll;
//以上为头文件
const int MAXN=100000+5;//N的最大范围
const int MAXM=100000+5;//M的最大范围
struct TreeArray{//树状数组模板
#define lowbit(x) ( (x)&( - (x) ) )
ll n;
ll unit[MAXN];
void Update(ll ID,ll val){
while(ID<=n){
unit[ID]+=val;
ID+=lowbit(ID);
}
return;
}
ll Query(ll x){
register ll ans=0;
while(x){
ans+=unit[x];
x-=lowbit(x);
}
return ans;
}
ll Query(ll x,ll y){
return Query(y)-Query(x-1);
}
};
ll n,m;
TreeArray T1,T2;//两个树状数组
int main(void){
register ll i;
scanf("%lld%lld",&n,&m);
T1.n=T2.n=n;
for(i=1;i<=m;++i){
static ll k,a,b;
scanf("%lld%lld%lld",&k,&a,&b);
if(k==1){
T1.Update(a,1);
T2.Update(b,1);
}
if(k==2)
printf("%lld\n",T1.Query(b)-T2.Query(a-1));
}
return 0;
}
I blog quite often and I truly thank you for your content.
This article has truly peaked my interest. I’m going to book mark your blog
and keep checking for new details about once a week. I opted in for your Feed as well.