首页 > 代码库 > cdoj 1259 昊昊爱运动 II 线段树+bitset
cdoj 1259 昊昊爱运动 II 线段树+bitset
昊昊爱运动 II
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
昊昊喜欢运动
他NN天内会参加MM种运动(每种运动用一个[1,m][1,m]的整数表示)
现在有QQ个操作,操作描述如下
- 昊昊把第ll天到第rr天的运动全部换成了xx(x∈[1,m]x∈[1,m])
- 问昊昊第ll天到第rr天参加了多少种不同的运动
Input
输入两个数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
,表示昊昊把第ll天到第rr天的运动全部换成了xx(x∈[1,m]x∈[1,m]) - 形如
Q l r
,表示昊昊想知道他第ll天到第rr天参加了多少种不同的运动
Output
对于所有的Q操作,每一行输出一个数 表示昊昊在第ll天到第rr天一共做了多少种活动
Sample input and output
Sample Input | Sample Output |
---|---|
5 31 2 3 2 34Q 1 4Q 2 4M 5 5 2Q 1 5 | 323 |
Source
咦。。。
#include<bits/stdc++.h>using namespace std;#define ll long long#define pi (4*atan(1.0))const int N=1e5+10,M=4e6+10,inf=1e9+10;struct is{ int l,r; int lazy; bitset<110>b;}tree[N<<2];int a[N];void pushup(int pos){ tree[pos].b=tree[pos<<1].b|tree[pos<<1|1].b;}void pushdown(int pos){ if(tree[pos].lazy) { tree[pos<<1].lazy=tree[pos].lazy; tree[pos<<1|1].lazy=tree[pos].lazy; tree[pos<<1].b.reset(); tree[pos<<1].b.set(tree[pos].lazy); tree[pos<<1|1].b.reset(); tree[pos<<1|1].b.set(tree[pos].lazy); tree[pos].lazy=0; }}void build(int l,int r,int pos){ tree[pos].l=l; tree[pos].r=r; tree[pos].lazy=0; tree[pos].b.reset(); if(l==r) { tree[pos].b.set(a[l]); return; } int mid=(l+r)>>1; build(l,mid,pos<<1); build(mid+1,r,pos<<1|1); pushup(pos);}void update(int l,int r,int change,int pos){ if(tree[pos].l==l&&tree[pos].r==r) { tree[pos].b.reset(); tree[pos].b.set(change); tree[pos].lazy=change; return; } pushdown(pos); int mid=(tree[pos].l+tree[pos].r)/2; if(r<=mid) update(l,r,change,pos<<1); else if(mid<l) update(l,r,change,pos<<1|1); else { update(l,mid,change,pos<<1); update(mid+1,r,change,pos<<1|1); } pushup(pos);}bitset<110> query(int l,int r,int pos){ if(tree[pos].l==l&&tree[pos].r==r) return tree[pos].b; pushdown(pos); int mid=(tree[pos].l+tree[pos].r)>>1; if(r<=mid) return query(l,r,pos<<1); else if(l>mid) return query(l,r,pos<<1|1); else return query(l,mid,pos<<1)|query(mid+1,r,pos<<1|1);}char ch[10];int main(){ int n,m,i; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); int q; scanf("%d",&q); while(q--) { int l,r,p; scanf("%s%d%d",ch,&l,&r); if(ch[0]==‘Q‘) printf("%d\n",query(l,r,1).count()); else scanf("%d",&p),update(l,r,p,1); } return 0;}
cdoj 1259 昊昊爱运动 II 线段树+bitset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。