Q - 昊昊爱运动 II

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

昊昊喜欢运动

他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

Sample input and output

Sample Input	Sample Output
5 3 1 2 3 2 3 4 Q 1 4 Q 2 4 M 5 5 2 Q 1 5	3 2 3

思路：

区间覆盖，区间查询

依旧线段树搞起，不过有pushup和pushdown操作，这要注意下

具体的就不说了，和前面的题目没啥区别

对了要用bitset记录，，差点忘了、

 #include <iostream>

 #include <algorithm>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <queue>

 #include <stack>

 #include <map>

 #include <vector>

 #include <cstdlib>

 #include <string>

 #include <bitset>

 #define PI acos((double)-1)

 #define E exp(double(1))

 #define K 100000

 using namespace std;

 int n,m;

 int a[K+];

 struct node

 {

     bitset<>s;

     int change,l,r;

 };

 struct node tree[*K+];

 void pushdown(int id)

 {

     if(!tree[id].change)

         return ;

     tree[id*+].s=tree[id*].s=tree[id].s;

     tree[id*+].change=tree[id*].change=;

     tree[id].change=;

 }

 void build(int id,int l,int r)

 {

     tree[id].l=l;tree[id].r=r;tree[id].change=;

     if(l==r)

             tree[id].s[a[l]]=;

     else

     {

         int mid=(tree[id].l+tree[id].r)>>;

         if(r <= mid) build(id*,l,r);

         else if(l > mid) build(id*+,l,r);

         else

         {

             build(id<<,l,mid);

             build(id*+,mid+,r);

         }

         tree[id].s=tree[id*].s|tree[id*+].s;

     }

 }

 void update(int id,int l,int r,int v)

 {

     if(tree[id].l==l && tree[id].r==r)

     {

         tree[id].change=;

         tree[id].s.reset();

         tree[id].s[v]=;

     }

     else

     {

         pushdown(id);

         int mid=(tree[id].l+tree[id].r)>>;

         if(r<=mid) update(id<<,l,r,v);

         else if(l>mid) update(id*+,l,r,v);

         else

         {

             update(id<<,l,mid,v);

             update(id*+,mid+,r,v);

         }

         tree[id].s=tree[id*].s|tree[id*+].s;

     }

 }

 bitset<> query(int id,int l,int r)

 {

     if(tree[id].l == l && tree[id].r==r )

         return tree[id].s;

     else

     {

         pushdown(id);

         int mid=(tree[id].l+tree[id].r)>>;

         bitset<>ret;

         if(r<=mid) ret=ret|query(id*,l,r);

         else if(l>mid) ret=ret|query(id*+,l,r);

         else

         {

             ret=ret|query(id*,l,mid);

             ret=ret|query(id*+,mid+,r);

         }

         return ret;

     }

 }

 int main(void)

 {

     cin>>n>>m;

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     build(,,n);

     int q;

     cin>>q;

     while(q--)

     {

         char c;

         c=getchar();

         while(c==' ' || c=='\n')

             c=getchar();

         if(c=='M')

         {

             int l,r,v;

             scanf("%d%d%d",&l,&r,&v);

             update(,l,r,v);

         }

         else

         {

             int l,r,num=;

             scanf("%d%d",&l,&r);

             bitset<> temp=query(,l,r);

             for(int i=;i<=m;i++)

                 if(temp.test(i))

                     num++;

             printf("%d\n",num);

         }

     }

     return ;

 }

巴特西

cdojQ - 昊昊爱运动 II

Q - 昊昊爱运动 II

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Input

Output

Sample input and output

最新文章

热门文章