Transformation HDU – 4578 (延迟标记)

对延迟标记要有深入的理解。。。多个标记同时存在时要考虑顺序

参考:http://www.cfzhao.com/2019/04/03/hdu-4578-transformation/

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int SIZE = 100005;
const int MOD = 10007;
int n, q;

struct SegmentTree {
  int l, r;
  int sum,sum2,sum3;
  int lazy_add,lazy_mul,lazy_assign;
 #define l(x) tree[x].l
 #define r(x) tree[x].r
 #define sum(x) tree[x].sum
 #define sum2(x) tree[x].sum2
 #define sum3(x) tree[x].sum3
 #define lazy_add(x) tree[x].lazy_add
 #define lazy_mul(x) tree[x].lazy_mul
 #define lazy_assign(x) tree[x].lazy_assign
} tree[SIZE * 4];

void pushup(int p){
  sum(p)=(sum(p<<1|1)+sum(p<<1))%MOD;
  sum2(p)=(sum2(p<<1|1)+sum2(p<<1))%MOD;
  sum3(p)=(sum3(p<<1|1)+sum3(p<<1))%MOD;
}

void spread(int p){
  if(lazy_assign(p)){
    int s1=lazy_assign(p)%MOD,s2=s1*lazy_assign(p)%MOD,s3=s2*lazy_assign(p)%MOD;
    sum(p<<1|1)=s1*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=s1*(r(p<<1)-l(p<<1)+1)%MOD;
    sum2(p<<1|1)=s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum2(p<<1)=s2*(r(p<<1)-l(p<<1)+1)%MOD;
    sum3(p<<1|1)=s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum3(p<<1)=s3*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_assign(p<<1|1)=lazy_assign(p<<1)=lazy_assign(p);
    lazy_add(p<<1|1)=lazy_add(p<<1)=0;
    lazy_mul(p<<1|1)=lazy_mul(p<<1)=1;
    lazy_assign(p)=0; 
  }
  if(lazy_mul(p)!=1){
    int s1=lazy_mul(p)%MOD,s2=s1*lazy_mul(p)%MOD,s3=s2*lazy_mul(p)%MOD;
    sum(p<<1|1)=sum(p<<1|1)*s1%MOD;
    sum(p<<1)=sum(p<<1)*s1%MOD;
    sum2(p<<1|1)=sum2(p<<1|1)*s2%MOD;
    sum2(p<<1)=sum2(p<<1)*s2%MOD;
    sum3(p<<1|1)=sum3(p<<1|1)*s3%MOD;
    sum3(p<<1)=sum3(p<<1)*s3%MOD;
    lazy_mul(p<<1|1)=lazy_mul(p<<1|1)*lazy_mul(p)%MOD;
    lazy_mul(p<<1)=lazy_mul(p<<1)*lazy_mul(p)%MOD;
    lazy_add(p<<1|1)=lazy_add(p<<1|1)*lazy_mul(p)%MOD;
    lazy_add(p<<1)=lazy_add(p<<1)*lazy_mul(p)%MOD;
    lazy_mul(p)=1;
  }
  if(lazy_add(p)!=0){
    int s1=lazy_add(p)%MOD,s2=s1*lazy_add(p)%MOD,s3=s2*lazy_add(p)%MOD;
    sum3(p<<1|1)=(sum3(p<<1|1)+3*s1%MOD*sum2(p<<1|1)%MOD+3*s2%MOD*sum(p<<1|1)%MOD+s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum3(p<<1)=(sum3(p<<1)+3*s1%MOD*sum2(p<<1)%MOD+3*s2%MOD*sum(p<<1)%MOD+s3*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum2(p<<1|1)=(sum2(p<<1|1)+2*s1%MOD*sum(p<<1|1)%MOD+s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum2(p<<1)=(sum2(p<<1)+2*s1%MOD*sum(p<<1)%MOD+s2*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum(p<<1|1)=sum(p<<1|1)+lazy_add(p)*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=sum(p<<1)+lazy_add(p)*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_add(p<<1|1)=(lazy_add(p<<1|1)+lazy_add(p))%MOD;
    lazy_add(p<<1)=(lazy_add(p<<1)+lazy_add(p))%MOD;
    lazy_add(p)=0;
  }

}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  lazy_add(p)=0,lazy_assign(p)=0,lazy_mul(p)=1;
  if (l == r) {
    sum(p)=sum2(p)=sum3(p)=0;
    return ;
  }
  int mid = (l + r) >>1;
  build(p<<1, l, mid);
  build(p <<1 | 1, mid + 1, r);
  pushup(p);
}

void change(int p, int L,int R, int c,int d) {
  if(L<=l(p) && r(p)<=R){
    ll s1=d%MOD,s2=s1*d%MOD,s3=s2*d%MOD;
    if(c==1){
     sum3(p)=(sum3(p)+3*s1%MOD*sum2(p)%MOD+3*s2%MOD*sum(p)%MOD+s3*(r(p)-l(p)+1)%MOD)%MOD;
     sum2(p)=(sum2(p)+2*s1%MOD*sum(p)%MOD+s2*(r(p)-l(p)+1)%MOD)%MOD;
     sum(p)=(sum(p)+s1*(r(p)-l(p)+1)%MOD)%MOD;
     lazy_add(p)=(lazy_add(p)+d)%MOD;
    }
    if(c==2){
      sum(p)=s1*sum(p)%MOD;
      sum2(p)=s2*sum2(p)%MOD;
      sum3(p)=s3*sum3(p)%MOD;
      lazy_mul(p)=lazy_mul(p)*d%MOD;
      lazy_add(p)=lazy_add(p)*d%MOD;
    }
    if(c==3){
      sum(p)=s1*(r(p)-l(p)+1)%MOD;
      sum2(p)=s2*(r(p)-l(p)+1)%MOD;
      sum3(p)=s3*(r(p)-l(p)+1)%MOD;
      lazy_assign(p)=d;
      lazy_add(p)=0;
      lazy_mul(p)=1;
    }
    return;
  } 
  spread(p);
  int mid=(l(p)+r(p))>>1;
  if(L<=mid) change(p<<1,L,R,c,d);
  if(R>mid) change(p<<1|1,L,R,c,d);
  pushup(p);
} 

int ask(int p,int l,int r,int c){
    if(l<=l(p) && r(p)<=r){
      if(c==1) return sum(p);
      if(c==2) return sum2(p);
      if(c==3) return sum3(p);
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    int val=0;
    if(l<=mid)  val+=ask(p<<1,l,r,c);
    if(r>mid)  val+=ask(p<<1|1,l,r,c);
    return val%MOD;
} 

int main() {
  int T,kase=0;
  while(~scanf("%d%d",&n,&q)&&n&&q){
    build(1,1,n);
    while(q--){
      int a,x,y,c;
      scanf("%d%d%d%d",&a,&x,&y,&c);
      if(a!=4) change(1,x,y,a,c);
      else{
        printf("%d\n",ask(1,x,y,c));
      }
    }

  }
  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注