链接：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)
ac代码：
#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<string>
#include<stack>
#include<ctime>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<sstream>
#include<iostream>
#include<functional>
#include<algorithm>
#include<memory.h>
using namespace std;
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mp make_pair
#define pb push_back
#define mmm(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int maxn = 1e5 + ;
ll tree[maxn * ], lazy[maxn * ];
void pushdown(ll root) {
tree[root << ] |= lazy[root];
tree[root << | ] |= lazy[root];
lazy[root << ] |= lazy[root];
lazy[root << | ] |= lazy[root];
lazy[root] = ;
}
void update(ll l, ll r, ll L, ll R, ll root, ll clr) {
if (l <= L&&r >= R) {
tree[root] |= clr;
lazy[root] |= clr;
return;
}
ll mid = L + R >> ;
if (lazy[root])pushdown(root);
if (r <= mid)update(l, r, L, mid, root << , clr);
else if (l > mid)update(l, r, mid+, R, root << | , clr);
else {
update(l, mid, L, mid, root << , clr);
update(mid + , r, mid + , R, root << | , clr);
}
tree[root] = tree[root << ] | tree[root << | ]; }
ll query(ll l, ll r, ll L, ll R, ll root, ll clr) {
if (l <= L&&r >= R) { return tree[root];
}
ll mid = L + R >> ;
if (lazy[root])pushdown(root);
if (r <= mid)return query(l, r, L, mid, root << , clr);
else if (l > mid)return query(l, r, mid+ , R, root << | , clr);
else {
return query(l, mid, L, mid, root << , clr)| query(mid + , r, mid + , R, root << | , clr);; }
tree[root] = tree[root << ] | tree[root << | ]; }
int main()
{
ios::sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
mmm(tree, );
mmm(lazy, );
rep(i, , m) {
ll x, l, r, c;
cin >> x;
if (x == ) {
cin >> l >> r >> c;
update(l, r, , n, , 1ll << c); }
if (x == ) {
cin >> l >> r;
ll ans = query(l, r, , n,, );
int res = ;
while (ans) {
if (ans & )res++;
ans >>= ;
}
cout << res << endl;
}
}
} }
tle代码
#define _CRT_SECURE_NO_WARNINGS
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<cstdio>
#include<string>
#include<stack>
#include<ctime>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<sstream>
#include<iostream>
#include<functional>
#include<algorithm>
#include<memory.h>
//#define INF 0x3f3f3f3f
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
#define rep(i,t,n) for(int i =(t);i<=(n);++i)
#define per(i,n,t) for(int i =(n);i>=(t);--i)
#define mp make_pair
#define pb push_back
#define mmm(a,b) memset(a,b,sizeof(a))
//std::ios::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
void smain();
#define ONLINE_JUDGE
int main() {
// ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
long _begin_time = clock();
#endif
smain();
#ifndef ONLINE_JUDGE
long _end_time = clock();
printf("time = %ld ms.", _end_time - _begin_time);
#endif
return ;
}
#define _CRT_SECURE_NO_WARNINGS const int maxn = 1e5 + ;
int a[maxn], n, q, l, r, val;
typedef long long ll;
struct node {
int l, r;
long long sum, lazy;
void update(long long x) {
//sum += (ll)1 * (r - l + 1)*x;
//lazy += x;
sum |= x;
lazy |= x;
}
}tree[maxn * ];
void push_up(int x) {
//tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
tree[x].sum = tree[x << ].sum | tree[x << | ].sum;
}
void push_down(int x) {
int lazyval = tree[x].lazy;
if (lazyval) {
tree[x << ].update(lazyval);
tree[x << | ].update(lazyval);
tree->lazy = ;
}
}
void build(int x, int l, int r) {
tree[x].l = l; tree[x].r = r;
tree[x].sum = tree[x].lazy = ;
if (l == r) {
tree[x].sum = ;
}
else {
int mid = l + r >> ;
build(x << , l, mid);
build(x << | , mid + , r);
push_up(x);
}
}
void update(int x, int l, int r, long long val) {
int L = tree[x].l, R = tree[x].r;
if (l <= L&&r >= R) {
tree[x].update(val);
}
else {
push_down(x);
int mid = L + R >> ;
if (mid >= l)update(x << , l, r, val);
if (r > mid)update(x << | , l, r, val);
push_up(x);
}
}
long long query(int x, int l, int r) {
int L = tree[x].l, R = tree[x].r;
if (l <= L&&r >= R) {
return tree[x].sum;
}
else {
push_down(x);
long long ans = ;
int mid = L + R >> ;
if (mid >= l)ans |= query(x << , l, r);
if (r > mid)ans |= query(x << | , l, r);
push_up(x);
return ans;
}
} void Run() { } void smain() {
cin >> n >> q; {
build(, , n);
rep(i, , q) {
int x;
scanf("%d", &x);
//cin >> x;
if (x == ) {
int l, r, c;
scanf("%d%d%d", &l, &r,&c);
//cin >> l >> r >> c;
update(, l, r, << c); }
else {
int l, r; scanf("%d%d", &l, &r);
//cin >> l >> r;
ll res= query(, l, r);
int cnt=; while (res) {
if (res & )cnt++;
res >>= ;
}
printf("%d\n", cnt);
//cout << cnt << endl;
}
}
}
}