链接：https://www.nowcoder.com/acm/contest/105/H
来源：牛客网
n个桶按顺序排列，我们用1~n给桶标号。有两种操作：
1 l r c 区间[l,r]中的每个桶中都放入一个颜色为c的球 (1≤l,r ≤n,l≤r,0≤c≤60)
2 l r 查询区间[l,r]的桶中有多少种不同颜色的球 (1≤l,r ≤n,l≤r)
1 l r c 区间[l,r]中的每个桶中都放入一个颜色为c的球 (1≤l,r ≤n,l≤r,0≤c≤60)
2 l r 查询区间[l,r]的桶中有多少种不同颜色的球 (1≤l,r ≤n,l≤r)
输入描述:
有多组数据，对于每组数据：
第一行有两个整数n,m(1≤n,m≤100000)
接下来m行，代表m个操作，格式如题目所示。
输出描述:
对于每个2号操作，输出一个整数，表示查询的结果。
输入例子:
10 10
1 1 2 0
1 3 4 1
2 1 4
1 5 6 2
2 1 6
1 7 8 1
2 3 8
1 8 10 3
2 1 10
2 3 8
输出例子:
2
3
2
4
3
-->
示例1
输入
10 10
1 1 2 0
1 3 4 1
2 1 4
1 5 6 2
2 1 6
1 7 8 1
2 3 8
1 8 10 3
2 1 10
2 3 8
输出
2
3
2
4
3 思路：
看到颜色<=60，摆明了用二进制。。写法跟poj2777差不多，只不过poj2777是覆盖颜色，这个是增加颜色。。
忘了 << 运算不支持long long范围。。找了半天错。。。直接用快速幂代替就好了
如果之前写过这种类型的题的话写起来就很简单了. 实现代码;
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
const ll M = 1e5+;
ll powl(ll n,ll m)
{
ll ans = ;
while(m > )
{
if(m & )ans = (ans * n);
m = m >> ;
n = (n * n);
}
return ans;
} ll n,w,e;
ll color[M*],lazy[M*];
void pushup(ll rt){
color[rt] = color[rt*]|color[rt*+];
} void build(ll l,ll r,ll rt){
if(l==r){
color[rt] = ;
return ;
}
ll m = (l+r)/;
build(l,m,rt*);
build(m+,r,rt*+);
pushup(rt);
} void pushdown(ll rt){
if(lazy[rt]){
lazy[rt*] |= lazy[rt];
lazy[rt*+] |= lazy[rt];
color[rt*] |= lazy[rt*];
color[rt*+] |= lazy[rt*+];
lazy[rt] = ;
}
} void update(ll L,ll R,ll l,ll r,ll x,ll rt){
if(L<=l&&r<=R){
lazy[rt] |= powl(,x-);
color[rt] |= powl(,x-);
return ;
}
pushdown(rt);
ll m = (l+r)/;
if(L<=m) update(L,R,l,m,x,rt*);
if(R>m) update(L,R,m+,r,x,rt*+);
pushup(rt);
} ll query(ll L,ll R,ll l,ll r,ll rt){
if(L<=l&&r<=R){
return color[rt];
}
ll ans1=,ans2=,ans;
ll m = (l+r)/;
pushdown(rt);
if(L<=m) ans1+=query(L,R,l,m,rt*);
if(R>m) ans2+=query(L,R,m+,r,rt*+);
ans = ans1|ans2;
return ans;
} void getsum(ll x){
ll ans = ;
while(x){
if(x%==) ans++;
x/=;
}
printf("%lld\n",ans);
} int main()
{
ll L,R,x;
int c;
while(scanf("%lld%lld",&n,&w)!=EOF){
memset(lazy,,sizeof(lazy));
build(,n,);
while(w--){
scanf("%lld",&c);
if(c==){
scanf("%lld%lld%lld",&L,&R,&x);
if(L>R) swap(L,R);
x++;
update(L,R,,n,x,);
}
else{
scanf("%lld%lld",&L,&R);
if(L>R) swap(L,R);
ll cnt = query(L,R,,n,);
//cout<<cnt<<endl;
getsum(cnt);
}
}
}
return ;
}