线段树，懒惰标记

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 #define N 400010 5 int sum[N],lazy[N]; 6 void pushup(int root){ 7     sum[root]=sum[root*2]+sum[root*2+1]; 8 } 9 void pushdown(int root,int x){10     if(lazy[root] != -1) {11         lazy[root*2] = lazy[root*2+1] = lazy[root];12         sum[root*2]=(x-x/2)*lazy[root];13         sum[root*2+1]=x/2*lazy[root];14         lazy[root]=-1;15     }16 }17 void build(int l,int r,int root){18     lazy[root]=-1,sum[root]=1;19     if(l==r)return ;20     int mid=(l+r)/2;21     build(l,mid,root*2);22     build(mid+1,r,root*2+1);23     pushup(root);24 }25 26 void query(int x,int y,int l,int r,int root,int a){27     if(x<=l&&y>=r){28         lazy[root] = a;29          sum[root] = a*(r-l+1);30          return;31     }32     pushdown(root,r-l+1);33     int mid=(r+l)/2;34     if(x<=mid)query(x,y,l,mid,root*2,a);35     if(y>mid)query(x,y,mid+1,r,root*2+1,a);36     pushup(root);37 }38 int main(){39     //freopen("test.txt","r",stdin);40     int t,n,q,x,y,z,case1=0;41     scanf("%d",&t);42     while(t--){43         case1++;44         scanf("%d%d",&n,&q);45         build(1,n,1);46         for(int i=0;i