昊昊喜欢运动
他N天内会参加M种运动(每种运动用一个[1,m]的整数表示)
现在有Q个操作，操作描述如下
- 昊昊把第l天到第r天的运动全部换成了x(x∈[1,m])
- 问昊昊第l天到第r天参加了多少种不同的运动
Input
输入两个数N, M (1≤N≤105, 1≤M≤100);
输入N个数ai(ai∈[1,m])表示在第i天昊昊做了第ai类型的运动;
输入一个数Q(1≤Q≤105);
输入Q行 每行描述以下两种操作
- 形如
M l r x，表示昊昊把第l天到第r天的运动全部换成了x(x∈[1,m]) - 形如
Q l r，表示昊昊想知道他第l天到第r天参加了多少种不同的运动
Output
对于所有的Q操作，每一行输出一个数 表示昊昊在第l天到第r天一共做了多少种活动
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 3 |
3 |
每一个节点开一个bitset维护就可以， 区间更新区间查询。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 1e5+;
int lazy[maxn<<], a[maxn<<];
bitset <> s[maxn<<];
void pushUp(int rt) {
s[rt] = s[rt<<]|s[rt<<|];
}
void pushDown(int rt) {
if(lazy[rt]) {
lazy[rt<<] = lazy[rt<<|] = lazy[rt];
a[rt<<] = a[rt<<|] = lazy[rt];
s[rt<<].reset();
s[rt<<|].reset();
s[rt<<][lazy[rt]] = s[rt<<|][lazy[rt]] = ;
lazy[rt] = ;
return ;
}
}
void build(int l, int r, int rt) {
if(l == r) {
scanf("%d", &a[rt]);
lazy[rt] = ;
s[rt][a[rt]] = ;
return ;
}
int m = l+r>>;
build(lson);
build(rson);
pushUp(rt);
}
void update(int val, int L, int R, int l, int r, int rt) {
if(L<=l&&R>=r) {
a[rt] = val;
s[rt].reset();
s[rt][val] = ;
lazy[rt] = val;
return ;
}
pushDown(rt);
int m = l+r>>;
if(L<=m)
update(val, L, R, lson);
if(R>m)
update(val, L, R, rson);
pushUp(rt);
}
bitset<> query(int L, int R, int l, int r, int rt) {
if(L<=l&&R>=r) {
return s[rt];
}
pushDown(rt);
bitset<> tmp;
tmp.reset();
int m = l+r>>;
if(L<=m)
tmp |= query(L, R, lson);
if(R>m)
tmp |= query(L, R, rson);
return tmp;
}
int main()
{
int q, n, m, x, y;
char ch;
cin>>n>>m;
build(, n, );
cin>>q;
while(q--) {
scanf(" %c%d%d", &ch, &x, &y);
if(ch == 'Q')
printf("%d\n", query(x, y, , n, ).count());
else {
int z;
scanf("%d", &z);
update(z, x, y, , n, );
}
}
return ;
}