2016 UESTC Training for Data Structures Q – 昊昊爱运动 II 线段树+延迟操作+bitset

Source

2016 UESTC Training for Data Structures  Problem Q

My Solution

每次把一个区间变为一个定值

线段树+延迟操作+bitset

延迟操作，在查询或者改造的时候再向下传并标记好

先用memset全部标记为false表示值没有传下去；

在建树的时候就要一次把标记改为true了

然后改造的时候重新标记为false， 向下传的时候把false改为true，然后false也传下去；

返回的时候维护

另外每个节点用bitset维护，

push_up的时候 Top[Ind]=Top[Ind<<1] | Top[(Ind<<1)+1];     //这样自然就把原来的Top[Ind]去掉了

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 100000+8;

bitset<101> Top[4*maxn];
bool Cover[4*maxn];             //lazy[maxn]
bitset<101> findans;

int size;


void _Query(int a,int b,int l,int r,int Ind){
    if(a <= l && b >= r) {findans |= Top[Ind]; return;}
    int mid = (l+r)>>1;
    if(!Cover[Ind]){Top[Ind<<1] = Top[Ind];Top[(Ind<<1)+1] = Top[Ind];Cover[Ind] = true;Cover[Ind<<1] = false;Cover[(Ind<<1)+1] = false;}
    if(a <= mid) { _Query(a, b, l, mid, Ind<<1);} if(b > mid) { _Query(a, b, mid+1,r,(Ind<<1)+1);}


}

void _Modify(int a,int b,int l,int r,int Ind, int d){
    if(a <= l && b >= r) {Top[Ind].reset(); Top[Ind][d] = 1; Cover[Ind] = false; return;}
    int mid = (l+r)>>1;
    if(!Cover[Ind]){Top[Ind<<1] = Top[Ind];Top[(Ind<<1)+1] = Top[Ind];Cover[Ind] = true;Cover[Ind<<1] = false;Cover[(Ind<<1)+1] = false;}
    if(a <= mid) { _Modify(a, b, l, mid, Ind<<1, d);} if(b > mid) { _Modify(a, b, mid+1, r,(Ind<<1)+1, d);}
    Top[Ind]=Top[Ind<<1] | Top[(Ind<<1)+1];     //这样自然就把原来的Top[Ind]去掉了
}

void _Build(int a,int l,int r,int Ind,int d){
    if(l == r && l == a){
        Top[Ind][d] = 1;
        Cover[Ind] = false;
        //cout<<Top[Ind]<<endl; return; } int mid = (l+r)>>1;
    if(a <= mid) _Build(a,l,mid,Ind<<1,d);
    else _Build(a,mid+1,r,(Ind<<1)+1,d);
    Top[Ind]=Top[Ind<<1] | Top[(Ind<<1)+1];     //这样自然就把原来的Top[Ind]去掉了
    Cover[Ind] = true;//!!!!!!这里加了句就对了☺☺ ，不然样例都过不了，(因为初始化为 false 了)这个区间的bitset会被传下去
}


void Query(int a,int b) {return _Query(a,b,1,size,1);}
void Modify(int a,int b,int d){return _Modify(a,b,1,size,1,d);}
void Build(int a,int d) {return _Build(a,1,size,1,d);}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    memset(Top, 0, sizeof Top);
    memset(Cover, false, sizeof Cover);
    int  n, m, q, val;
    scanf("%d%d", &n, &m); size = n;
    for(int i = 1; i <= n; i++){
        scanf("%d", &val);
        Build(i, val);
    }

    char op;
    int l, r, x;
    scanf("%d", &q);getchar();
    while(q--){
        scanf("%c", &op);// printf("%cn", op);
        if(op == 'M'){
            scanf("%d%d%d", &l, &r, &x);
            Modify(l, r, x);
        }
        else {
            findans.reset();
            scanf("%d%d", &l, &r);
            Query(l,r);

            printf("%dn", int(findans.count()));
        }
        getchar();
    }
    return 0;
}
/*关于bitset获得1的个数
// bitset::count
#include 
#include 
#include 
using namespace std;

int main ()
{
  bitset<8> myset (string("10110011"));

  cout << "myset has " << int(myset.count()) << " ones ";
  cout << "and " << int(myset.size()-myset.count()) << " zeros.n";

  return 0;
}
//Output:
//myset has 5 ones, and 3 zeros

*/

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx