CDOJ 1259 昊昊爱运动 II bitset+线段树

题目链接

昊昊喜欢运动

他

现在有

昊昊把第
问昊昊第

Input

输入两个数

输入

输入一个数

输入

形如M l r x，表示昊昊把第
形如Q l r，表示昊昊想知道他第

Output

对于所有的Q操作，每一行输出一个数表示昊昊在第

Sample input and output

Sample Input	Sample Output
5 3 1 2 3 2 3 4 Q 1 4 Q 2 4 M 5 5 2 Q 1 5	3 2 3

每一个节点开一个bitset维护就可以，区间更新区间查询。

  1 #include <iostream>
  2 #include <vector>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <map>
  8 #include <set>
  9 #include <string>
 10 #include <queue>
 11 #include <stack>
 12 #include <bitset>
 13 using namespace std;
 14 #define pb(x) push_back(x)
 15 #define ll long long
 16 #define mk(x, y) make_pair(x, y)
 17 #define lson l, m, rt<<1
 18 #define mem(a) memset(a, 0, sizeof(a))
 19 #define rson m+1, r, rt<<1|1
 20 #define mem1(a) memset(a, -1, sizeof(a))
 21 #define mem2(a) memset(a, 0x3f, sizeof(a))
 22 #define rep(i, n, a) for(int i = a; i<n; i++)
 23 #define fi first
 24 #define se second
 25 typedef pair<int, int> pll;
 26 const double PI = acos(-1.0);
 27 const double eps = 1e-8;
 28 const int mod = 1e9+7;
 29 const int inf = 1061109567;
 30 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 31 const int maxn = 1e5+5;
 32 int lazy[maxn<<2], a[maxn<<2];
 33 bitset <105> s[maxn<<2];
 34 void pushUp(int rt) {
 35     s[rt] = s[rt<<1]|s[rt<<1|1];
 36 }
 37 void pushDown(int rt) {
 38     if(lazy[rt]) {
 39         lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt];
 40         a[rt<<1] = a[rt<<1|1] = lazy[rt];
 41         s[rt<<1].reset();
 42         s[rt<<1|1].reset();
 43         s[rt<<1][lazy[rt]] = s[rt<<1|1][lazy[rt]] = 1;
 44         lazy[rt] = 0;
 45         return ;
 46     }
 47 }
 48 void build(int l, int r, int rt) {
 49     if(l == r) {
 50         scanf("%d", &a[rt]);
 51         lazy[rt] = 0;
 52         s[rt][a[rt]] = 1;
 53         return ;
 54     }
 55     int m = l+r>>1;
 56     build(lson);
 57     build(rson);
 58     pushUp(rt);
 59 }
 60 void update(int val, int L, int R, int l, int r, int rt) {
 61     if(L<=l&&R>=r) {
 62         a[rt] = val;
 63         s[rt].reset();
 64         s[rt][val] = 1;
 65         lazy[rt] = val;
 66         return ;
 67     }
 68     pushDown(rt);
 69     int m = l+r>>1;
 70     if(L<=m)
 71         update(val, L, R, lson);
 72     if(R>m)
 73         update(val, L, R, rson);
 74     pushUp(rt);
 75 }
 76 bitset<105> query(int L, int R, int l, int r, int rt) {
 77     if(L<=l&&R>=r) {
 78         return s[rt];
 79     }
 80     pushDown(rt);
 81     bitset<105> tmp;
 82     tmp.reset();
 83     int m = l+r>>1;
 84     if(L<=m)
 85         tmp |= query(L, R, lson);
 86     if(R>m)
 87         tmp |= query(L, R, rson);
 88     return tmp;
 89 }
 90 int main()
 91 {
 92     int q, n, m, x, y;
 93     char ch;
 94     cin>>n>>m;
 95     build(1, n, 1);
 96     cin>>q;
 97     while(q--) {
 98         scanf(" %c%d%d", &ch, &x, &y);
 99         if(ch == 'Q')
100             printf("%d
", query(x, y, 1, n, 1).count());
101         else {
102             int z;
103             scanf("%d", &z);
104             update(z, x, y, 1, n, 1);
105         }
106     }
107     return 0;
108 }