Time Limit: 20 Sec
Memory Limit: 256 MB
http://acm.uestc.edu.cn/#/problem/show/1259
昊昊喜欢运动
他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
5 3
1 2 3 2 3
4
Q 1 4
Q 2 4
M 5 5 2
Q 1 5
Sample Output
3
2
3
题意
题解：
线段树+bitset维护就好了
每一个节点塞进去一个bitset
代码：
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <cmath> #include <vector> #include <stack> #include <map> #include <set> #include <queue> #include <iomanip> #include <string> #include <ctime> #include <list> #include <bitset> typedef unsigned char byte; #define pb push_back #define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0) #define local freopen("in.txt","r",stdin) #define pi acos(-1) using namespace std; typedef int SgTreeDataType; struct treenode { int L , R ; SgTreeDataType sum , lazy; bitset<120> S; void updata(SgTreeDataType v) { if(v){ S.reset(); S[v]=1; lazy=v; } } }; treenode tree[150000*4]; inline void push_down(int o) { SgTreeDataType lazyval = tree[o].lazy; if(lazyval){ tree[2*o].updata(lazyval) ; tree[2*o+1].updata(lazyval); tree[o].lazy = 0; } } inline void push_up(int o) { tree[o].S = tree[2*o].S | tree[2*o+1].S; } inline void build_tree(int L , int R , int o) { tree[o].L = L , tree[o].R = R, tree[o].lazy = 0; tree[o].S.reset(); if (R > L) { int mid = (L+R) >> 1; build_tree(L,mid,o*2); build_tree(mid+1,R,o*2+1); } } inline void updata(int QL,int QR,SgTreeDataType v,int o) { int L = tree[o].L , R = tree[o].R; if (QL <= L && R <= QR){ tree[o].S.reset(); tree[o].updata(v); } else { push_down(o); int mid = (L+R)>>1; if (QL <= mid) updata(QL,QR,v,o*2); if (QR > mid) updata(QL,QR,v,o*2+1); push_up(o); } } inline bitset<120> query(int QL,int QR,int o) { int L = tree[o].L , R = tree[o].R; if (QL <= L && R <= QR) return tree[o].S; else { push_down(o); int mid = (L+R)>>1; bitset<120> res;res.reset(); if (QL <= mid) res |= query(QL,QR,2*o); if (QR > mid) res |= query(QL,QR,2*o+1); push_up(o); return res; } } int main(int argc,char *argv[]) { int n,m; scanf("%d%d",&n,&m); build_tree(1,n,1); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); updata(i,i,x,1); } char s[10]; int A,B,C; int q;scanf("%d",&q); for(int i=1;i<=q;i++) { scanf("%s%d%d",s,&A,&B); if(s[0]==‘Q‘) { printf("%d\n",query(A,B,1).count()); } else { scanf("%d",&C); updata(A,B,C,1); } } return 0; }
原文：http://www.cnblogs.com/qscqesze/p/5027990.html