本文共 3144 字，大约阅读时间需要 10 分钟。
地址：
题目：
昊昊喜欢运动
他NN 天内会参加MM 种运动(每种运动用一个[1,m][1,m] 的整数表示)
现在有QQ 个操作，操作描述如下
输入两个数NN , MM (1≤N≤1051≤N≤105 , 1≤M≤1001≤M≤100 );
输入NN 个数aiai (ai∈[1,m]ai∈[1,m] )表示在第i天昊昊做了第aiai 类型的运动;
输入一个数QQ (1≤Q≤1051≤Q≤105 );
输入QQ 行 每行描述以下两种操作
M l r x
Q l r
5 31 2 3 2 34Q 1 4Q 2 4M 5 5 2Q 1 5
323
思路：
区间覆盖，区间查询
依旧线段树搞起，不过有pushup和pushdown操作，这要注意下
具体的就不说了，和前面的题目没啥区别
对了要用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 14 #define PI acos((double)-1) 15 #define E exp(double(1)) 16 #define K 100000 17 using namespace std; 18 int n,m; 19 int a[K+5]; 20 struct node 21 { 22 bitset<110>s; 23 int change,l,r; 24 }; 25 struct node tree[4*K+5]; 26 27 void pushdown(int id) 28 { 29 if(!tree[id].change) 30 return ; 31 tree[id*2+1].s=tree[id*2].s=tree[id].s; 32 tree[id*2+1].change=tree[id*2].change=1; 33 tree[id].change=0; 34 } 35 void build(int id,int l,int r) 36 { 37 tree[id].l=l;tree[id].r=r;tree[id].change=0; 38 if(l==r) 39 tree[id].s[a[l]]=1; 40 else 41 { 42 int mid=(tree[id].l+tree[id].r)>>1; 43 if(r <= mid) build(id*2,l,r); 44 else if(l > mid) build(id*2+1,l,r); 45 else 46 { 47 build(id<<1,l,mid); 48 build(id*2+1,mid+1,r); 49 } 50 tree[id].s=tree[id*2].s|tree[id*2+1].s; 51 } 52 } 53 void update(int id,int l,int r,int v) 54 { 55 if(tree[id].l==l && tree[id].r==r) 56 { 57 tree[id].change=1; 58 tree[id].s.reset(); 59 tree[id].s[v]=1; 60 } 61 else 62 { 63 pushdown(id); 64 int mid=(tree[id].l+tree[id].r)>>1; 65 if(r<=mid) update(id<<1,l,r,v); 66 else if(l>mid) update(id*2+1,l,r,v); 67 else 68 { 69 update(id<<1,l,mid,v); 70 update(id*2+1,mid+1,r,v); 71 } 72 tree[id].s=tree[id*2].s|tree[id*2+1].s; 73 } 74 } 75 76 bitset<110> query(int id,int l,int r) 77 { 78 if(tree[id].l == l && tree[id].r==r ) 79 return tree[id].s; 80 else 81 { 82 pushdown(id); 83 int mid=(tree[id].l+tree[id].r)>>1; 84 bitset<110>ret; 85 if(r<=mid) ret=ret|query(id*2,l,r); 86 else if(l>mid) ret=ret|query(id*2+1,l,r); 87 else 88 { 89 ret=ret|query(id*2,l,mid); 90 ret=ret|query(id*2+1,mid+1,r); 91 } 92 return ret; 93 } 94 } 95 int main(void) 96 { 97 cin>>n>>m; 98 for(int i=1;i<=n;i++) 99 scanf("%d",&a[i]);100 build(1,1,n);101 int q;102 cin>>q;103 while(q--)104 {105 char c;106 c=getchar();107 while(c==' ' || c=='\n')108 c=getchar();109 if(c=='M')110 {111 int l,r,v;112 scanf("%d%d%d",&l,&r,&v);113 update(1,l,r,v);114 }115 else116 {117 int l,r,num=0;118 scanf("%d%d",&l,&r);119 bitset<110> temp=query(1,l,r);120 for(int i=1;i<=m;i++)121 if(temp.test(i))122 num++;123 printf("%d\n",num);124 }125 }126 return 0;127 }
转载于:https://www.cnblogs.com/weeping/p/5456159.html
