本文共 2823 字，大约阅读时间需要 9 分钟。
昊昊喜欢运动
他N天内会参加M种运动(每种运动用一个[1,m]的整数表示)
现在有Q个操作，操作描述如下
输入两个数N, M (1≤N≤105, 1≤M≤100);
输入N个数ai(ai∈[1,m])表示在第i天昊昊做了第ai类型的运动;
输入一个数Q(1≤Q≤105);
输入Q行 每行描述以下两种操作
M l r x
Q l r
对于所有的Q操作，每一行输出一个数 表示昊昊在第l天到第r天一共做了多少种活动
5 31 2 3 2 34Q 1 4Q 2 4M 5 5 2Q 1 5
323
每一个节点开一个bitset维护就可以， 区间更新区间查询。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 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 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\n", 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 }
转载于:https://www.cnblogs.com/yohaha/p/5078083.html