Trans formation-HDU 4578-線分樹

Trans formation-HDU 4578-線分樹
テーマの説明:
_; Yual fang is puzled with the question below:
_; The e re re re n integers,a 1,a 2,…,a n.The initial values of them are 0.The are four kids of operation.
_; Operation 1:Add c to each number between a x and a y inclusive.In other wods,dotranformation a k
_; Operation 2:Multiplly c to each numben a x and a y inclusive.In other wods,dotranformation a k
  Operation 3:Change the numbers between a x and a y to c、inclusive.In other wods、dotranformation a k
_; Operation 4:Get the sum of p power among the numbers between a x and a y inclusive.In other wods,get theres of a x+a x+1 p++a y.p.
  Yual fang hasのidea of how to dot.So he wants to ask you to help him.Input  The e re no more than 10 test cases.
_; For each case,the first line contains two numbers n and m,meaning that there re re n integers and m operations.1<=n,m<=100,000.
_; Each the follwing m lineas contains an operation.Operation 1 to 3 is in this format:“1 x y c”or“2 x y c”or“3 x y c”.Operation 4 is in this format:“4 x y”.
The input ends with 0.Outputユントパイアa single integer in one line representing the result.The answer may be quite large.You just need calculate the remander of the answer when divided by 10007.Sample Input

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3
0 0

Sample Output

307
7489

  題意:n個を0の数に初期化して、m個の操作をしてあげます.各行の操作は4つの整数type u v num、4種類の操作タイプに対応しています.
  type=1:区間[u,v]の全部の数を+numにします.
  type=2:区間[u,v]の全部の数を全部***numにします.
  type=3:区間[u,v]の全部の数をnumとして与えます.
  type=4:出力区間[u,v]の全数のnum乗と(1<=num<=3).
更新する時は、二種類または三種類のマークが同時に存在する場合、どう処理しますか?
  ここでは優先的な処理を選択します.一区間が賦値操作を行ったら、addマークとmultマークは自然に0になります.
次に加算と乗算の前後の問題です.ここでは乗算の中に小さな処理を加えることを選択します.現在の区間を処理する過程で、加算マークaddが存在することを発見したら、addマークをadd*numにして、乗算を行います.
このようにすれば、pushdown()過程では、必ず最初にsameを処理し、次にmultiを処理し、最後にaddとなります.
  WAはたくさんの髪を送りましたが、検査の結果、ただモデルを忘れただけです.心理状態が崩れ去った
  にACコードを添付します.

//
//  main.cpp
//  L
//
//  Created by LucienShui on 2017/6/2.
//  Copyright © 2017  LucienShui. All rights reserved.
//

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define memset(a,b,n) memset(a,b,n*sizeof(a[0]))
#define il inline
#define ll long long
#define ull unsigned long long

using namespace std;

#define ls (u<<1)
#define rs (u<<1|1)
#define lson u<<1,l,mid
#define rson u<<1|1,mid+1,r
#define MOD 10007
#define maxn 100007

int add[maxn<<2],mult[maxn<<2],same[maxn<<2],sum[maxn<<2][4],sz[maxn<<2],sum1,sum2,sum3,tmp2,tmp3;
//add    ，mult    ，same    ，sum     ，sz           
void fun_add(int u, int num) {
    add[u] = (add[u]+num)%MOD;
    sum1 = sum[u][1],sum2 = sum[u][2],sum3 = sum[u][3];
    sum[u][1] += (num*sz[u])%MOD;//       
    sum[u][1] %= MOD;
    tmp2 = (num * num)%MOD;
    sum[u][2] += sum1*num*2%MOD + (tmp2*sz[u])%MOD;//               
    sum[u][2] %= MOD;
    tmp3 = (tmp2 * num)%MOD;
    sum[u][3] += (3*tmp2*sum1)%MOD + (3*sum2*num)%MOD + (tmp3*sz[u])%MOD;//                
    sum[u][3] %= MOD;
}

void fun_mult(int u,int num) {
    if(mult[u]) mult[u] = (mult[u]*num)%MOD;
    else mult[u] = num;
    add[u] = (add[u]*num)%MOD;//            ，     add*num
    sum1 = sum[u][1],sum2 = sum[u][2],sum3 = sum[u][3];
    sum[u][1] = (sum1*num)%MOD;
    tmp2 = (num*num)%MOD;
    sum[u][2] = (sum2*tmp2)%MOD;
    tmp3 = (tmp2*num)%MOD;
    sum[u][3] = (sum3*tmp3)%MOD;
}

void fun_same(int u, int num) {
    same[u] = num;
    add[u] = mult[u] = 0;
    sum[u][1] = (num*sz[u])%MOD;
    tmp2 = (num*num)%MOD;
    sum[u][2] = (tmp2*sz[u])%MOD;
    tmp3 = (tmp2*num)%MOD;
    sum[u][3] = (tmp3*sz[u])%MOD;
}

void pushup(int u) {//        
    sum[u][1] = (sum[ls][1] + sum[rs][1])%MOD;
    sum[u][2] = (sum[ls][2] + sum[rs][2])%MOD;
    sum[u][3] = (sum[ls][3] + sum[rs][3])%MOD;
}

void pushdown(int u) {//    lazy  
    if(same[u]) {
        fun_same(ls,same[u]);
        fun_same(rs,same[u]);
        same[u]=0;
    }
    if(mult[u]) {
        fun_mult(ls,mult[u]);
        fun_mult(rs,mult[u]);
        mult[u]=0;
    }
    if(add[u]) {
        fun_add(ls,add[u]);
        fun_add(rs,add[u]);
        add[u]=0;
    }
}

void build(int u, int l, int r) {//    
    if(l==r) {
        add[u] = mult[u] = same[u] = 0;
        sum[u][1] = sum[u][2] = sum[u][3] = 0;
        sz[u] = 1;
        return ;
    }
    add[u] = mult[u] = same[u] = 0;
    sum[u][1] = sum[u][2] = sum[u][3] = 0;
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
    sz[u] = sz[ls] + sz[rs];//      sz  
}

void update(int u, int l, int r, int b, int e, int num, int type) {
    if(b <= l && r <= e) {
        if(type==1) fun_add(u,num);
        else if(type==2) fun_mult(u,num);
        else fun_same(u,num);
        return ;
    }
    pushdown(u);
    int mid = (l+r)>>1;
    if(b<=mid) update(lson,b,e,num,type);
    if(e>mid) update(rson,b,e,num,type);
    pushup(u);
}

int query(int u, int l, int r, int b, int e, int pow) {
    if(b <= l && r<=e) return sum[u][pow];
    pushdown(u);
    int mid = (l+r)>>1;
    if(e<=mid) return query(lson,b,e,pow)%MOD;//   MOD
    else if(b>mid) return query(rson,b,e,pow)%MOD;
    return (query(lson,b,e,pow)+query(rson,b,e,pow))%MOD;
}

int main ()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
    int n,m;
    while(scanf("%d%d",&n,&m),n!=0&&m!=0) {
        int type,b,e,num;
        build(1,1,n);
        for(int i=1 ; i<=m ; i++) {
            scanf("%d%d%d%d",&type,&b,&e,&num);
            if(type==4) printf("%d
",query(1,1,n,b,e,num));
            else update(1,1,n,b,e,num,type);
        }
    }
    return 0;
}