hdu4578[多标记]

链接:hdu4578[多标记]

题解

  • 非常裸的线段树,但是很麻烦,三个标记很多细节考虑
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define rep(i,x,y) for(register int i=x;i<=y;++i)
    #define repd(i,x,y) for(register int i=x;i>=y;--i)
    #define ll long long
    #define lson o<<1,l,mid
    #define rson o<<1|1,mid+1,r
    using namespace std;
    const int N=100000+5;
    const int p=10007;
    ll sum[3][N<<2],add[N<<2],st[N<<2],mul[N<<2];
    int n,m;
    inline void pushup(int o){rep(i,0,2)sum[i][o]=(sum[i][o<<1]+sum[i][o<<1|1])%p;}
    inline void pushdown(int o,int l,int r){
    int mid=l+r>>1;
    if(st[o]){
    add[o<<1]=add[o<<1|1]=0;
    mul[o<<1]=mul[o<<1|1]=1;
    st[o<<1]=st[o<<1|1]=st[o];
    rep(i,0,2){
    sum[i][o<<1]=(mid-l+1)*(ll)pow(st[o],i+1)%p;
    sum[i][o<<1|1]=(r-mid)*(ll)pow(st[o],i+1)%p;
    }
    st[o]=0;
    }
    if(mul[o]!=1){
    mul[o<<1]=mul[o<<1]*mul[o]%p;
    mul[o<<1|1]=mul[o<<1|1]*mul[o]%p;
    if(add[o<<1])add[o<<1]=add[o<<1]*mul[o]%p;
    if(add[o<<1|1])add[o<<1|1]=add[o<<1|1]*mul[o]%p;
    sum[2][o<<1]=sum[2][o<<1]*mul[o]%p*mul[o]%p*mul[o];
    sum[2][o<<1|1]=sum[2][o<<1|1]*mul[o]%p*mul[o]%p*mul[o];
    sum[1][o<<1]=sum[1][o<<1]*mul[o]%p*mul[o]%p;
    sum[1][o<<1|1]=sum[1][o<<1|1]*mul[o]%p*mul[o]%p;
    sum[0][o<<1]=sum[0][o<<1]*mul[o]%p;
    sum[0][o<<1|1]=sum[0][o<<1|1]*mul[o]%p;
    mul[o]=1;
    }
    if(add[o]){
    add[o<<1]+=add[o];
    add[o<<1|1]+=add[o];
    ll tp=add[o]*add[o]%p*add[o]%p;
    sum[2][o<<1]=(sum[2][o<<1]+tp*(mid-l+1)%p+3*add[o]*(sum[1][o<<1]+sum[0][o<<1]*add[o]%p)%p)%p;
    sum[2][o<<1|1]=(sum[2][o<<1|1]+tp*(r-mid)%p+3*add[o]*(sum[1][o<<1|1]+sum[0][o<<1|1]*add[o]%p)%p)%p;
    sum[1][o<<1]=(sum[1][o<<1]+2*sum[0][o<<1]*add[o]%p+add[o]*add[o]%p*(mid-l+1)%p)%p;
    sum[1][o<<1|1]=(sum[1][o<<1|1]+2*sum[0][o<<1|1]*add[o]%p+add[o]*add[o]%p*(r-mid)%p)%p;
    sum[0][o<<1]=(sum[0][o<<1]+add[o]*(mid-l+1))%p;
    sum[0][o<<1|1]=(sum[0][o<<1|1]+add[o]*(r-mid))%p;
    add[o]=0;
    }
    }
    inline void build(int o,int l,int r){
    add[o]=st[o]=0;mul[o]=1;
    if(l==r){rep(i,0,2)sum[i][o]=0;return ;}
    int mid=l+r>>1;
    build(lson);
    build(rson);
    pushup(o);
    }
    inline void update(int o,int l,int r,int L,int R,int op,int c){
    if(L<=l&&R>=r){
    if(op==3){
    st[o]=c;
    add[o]=0;mul[o]=1;
    sum[0][o]=(r-l+1)*c%p;
    sum[1][o]=(r-l+1)*c%p*c%p;
    sum[2][o]=(r-l+1)*c%p*c%p*c%p;
    }
    if(op==2){
    mul[o]=mul[o]*c%p;
    if(add[o])add[o]=(add[o]*c)%p;
    sum[0][o]=sum[0][o]*c%p;
    sum[1][o]=sum[1][o]*c%p*c%p;
    sum[2][o]=sum[2][o]*c%p*c%p*c%p;
    }
    if(op==1){
    add[o]+=c;
    ll tp=c*c%p*c%p;
    sum[2][o]=(sum[2][o]+tp*(r-l+1)%p+3*c*(sum[1][o]+c*sum[0][o]%p))%p;
    sum[1][o]=(sum[1][o]+c*c%p*(r-l+1)%p+2*c%p*sum[0][o]%p)%p;
    sum[0][o]=(sum[0][o]+c*(r-l+1))%p;
    }
    return ;
    }
    pushdown(o,l,r);
    int mid=l+r>>1;
    if(L<=mid)update(lson,L,R,op,c);
    if(R>mid)update(rson,L,R,op,c);
    pushup(o);
    }
    inline int query(int o,int l,int r,int L,int R,int op){
    if(L<=l&&R>=r)return sum[op-1][o]%p;
    pushdown(o,l,r);
    int mid=l+r>>1;
    ll ans=0;
    if(L<=mid)ans+=query(lson,L,R,op);
    if(R>mid)ans+=query(rson,L,R,op);
    return ans%p;
    }

    int main(){
    while(~scanf("%d%d",&n,&m)){
    if(!n&&!m)break;
    build(1,1,n);
    while(m--){
    int x,l,r,c;
    scanf("%d%d%d%d",&x,&l,&r,&c);
    if(x==4)printf("%d\n",query(1,1,n,l,r,c));
    else update(1,1,n,l,r,x,c);
    }
    }
    return 0;
    }