首页 > 代码库 > cdoj 1259 昊昊爱运动 II 线段树+bitset

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

2024-08-11 22:14:30   219人阅读

昊昊爱运动 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 InputSample 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


联系
我们