一道线段树。lazy标记+位运算……（第一次写这个什么lazy标记，抄了一发题解）

我们发现：“或”操作在这里用正合适。

原题请戳

// by Sirius_Ren#include 
     
      #include 
      
       #define N 100010using namespace std;int l,t,o,xx,yy,zz;char jy;struct segtree{
    int left,right,num,lazy;}tree[N*4];void build(int l,int r,int pos){    tree[pos].left=l,tree[pos].right=r,tree[pos].num=2,tree[pos].lazy=false;    if(l==r)return;    int mid=(l+r)/2;    build(l,mid,pos*2),build(mid+1,r,pos*2+1);}void push_down(int pos){    tree[pos*2].lazy=tree[pos*2+1].lazy=true;    tree[pos*2+1].num=tree[pos*2].num=tree[pos].num;    tree[pos].lazy=false;}void add(int pos){    if(tree[pos].left>=xx&&tree[pos].right<=yy){        tree[pos].lazy=true;        tree[pos].num=(1<
       
        mid)add(pos*2+1);    tree[pos].num=tree[pos*2].num|tree[pos*2+1].num;}int query(int pos){    if(tree[pos].left>=xx&&tree[pos].right<=yy)return tree[pos].num;    if(tree[pos].lazy)push_down(pos);    int mid=(tree[pos].left+tree[pos].right)/2;    if(xx>mid)return query(pos*2+1);    else if(yy<=mid)return query(pos*2);    else return query(pos*2+1)|query(pos*2); }int split(){    int sum=query(1),ans=0;    while(sum/=2)if(sum%2)ans++;    return ans;}int main(){    scanf("%d%d%d",&l,&t,&o);    build(1,l,1);    for(int i=1;i<=o;i++){        scanf("\n%c%d%d",&jy,&xx,&yy);        if(xx>yy)swap(xx,yy);        if(jy=='C')scanf("%d",&zz),add(1);        else printf("%d\n",split());    }}
       
      
     

晚上又写了一遍

很可惜，只刷到了Code Length第三… 省了一步建树。

#include 
     
      #include 
      
       #include 
       
        using namespace std;int L,o,xx=1,yy,zz=1,t[400001];char jy;bitset<400001>B;void pd(int p){t[p*2]=t[p*2+1]=t[p];B[p*2]=B[p*2+1]=true;B[p]=false;}void add(int l,int r,int p){    if(l>=xx&&r<=yy){B[p]=1;t[p]=1<
        
         m)add(m+1,r,p*2+1);    t[p]=t[p*2]|t[p*2+1];}int q(int l,int r,int p){    if(xx<=l&&yy>=r)return t[p];    if(B[p])pd(p);    int m=(l+r)/2;    if(m
         
          =yy)return q(l,m,p*2);    else return q(l,m,p*2)|q(m+1,r,p*2+1);}int main(){    scanf("%d%d%d",&L,&jy,&o);    yy=L,add(1,L,1);    while(o--){        scanf("\n%c%d%d",&jy,&xx,&yy);        if(xx>yy)swap(xx,yy);        if(jy=='C')scanf("%d",&zz),add(1,L,1);        else{            int s=q(1,L,1),a=0;            while(s){
    if(s%2)a++;s/=2;}            printf("%d\n",a);        }    }}