Hdu 4578 Transformation （线段树 分类分析）

Transformation

Time Limit: 15000/8000 MS (Java/Others)    Memory Limit: 65535/65536 K (Java/Others)
Total Submission(s): 10082    Accepted Submission(s): 2609

Problem Description

Yuanfang is puzzled with the question below: 
There are n integers, a₁, a₂, …, a_n. The initial values of them are 0. There are four kinds of operations.
Operation 1: Add c to each number between a_x and a_y inclusive. In other words, do transformation a_k<---a_k+c, k = x,x+1,…,y.
Operation 2: Multiply c to each number between a_x and a_y inclusive. In other words, do transformation a_k<---a_k×c, k = x,x+1,…,y.
Operation 3: Change the numbers between a_x and a_y to c, inclusive. In other words, do transformation a_k<---c, k = x,x+1,…,y.
Operation 4: Get the sum of p power among the numbers between a_x and a_y inclusive. In other words, get the result of a_x^p+a_x+1^p+…+a_y ^p.
Yuanfang has no idea of how to do it. So he wants to ask you to help him. 

Input

There are no more than 10 test cases.
For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000.
Each the following m lines 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 p". (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3)
The input ends with 0 0.

Output

For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder 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

Source

2013ACM-ICPC杭州赛区全国邀请赛

题解

这道题有三种询问：set , add , mul。所以lazy标记要有三个，如果三个标记同时出现的处理方法——当更新set操作时，就把add标记和mul标记全部取消；当更新mul操作时，如果当前节点add标记存在，就把add标记改为：add * mul。这样的话就可以在PushDown()操作中先执行set，然后mul，最后add。

C++代码一

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn =  ;
#define left v<<1
#define right v<<1|1
#define mod  10007
struct node
{
    int l ,r , value ;
    int eq , add , mul ;
}tree[maxn<<];
void build(int l , int r  , int v)
{
    tree[v].l = l ;
    tree[v].r = r ;
    tree[v].add =  ; tree[v].mul =  ;tree[v].eq = - ;
    if(l == r)
    {tree[v].eq =  ; return  ;}
    int mid = (l + r) >>  ;
    build(l , mid , left) ;
    build(mid +  , r , right) ;
}
void push_down(int v)
{
    if(tree[v].l == tree[v].r)return ;
    if(tree[v].eq != -)
    {
        tree[left].eq = tree[right].eq = tree[v].eq ;
        tree[left].add = tree[right].add =  ;
        tree[left].mul = tree[right].mul = ;
        tree[v].eq = -;
        return  ;
    }
    if(tree[v].mul != )
    {
        if(tree[left].eq != -)
        tree[left].eq = (tree[left].eq*tree[v].mul)%mod ;
        else
        {
            push_down(left) ;
            tree[left].mul = (tree[left].mul*tree[v].mul)%mod ;
        }
        if(tree[right].eq != -)
        tree[right].eq = (tree[right].eq*tree[v].mul)%mod ;
        else
        {
            push_down(right) ;
            tree[right].mul = (tree[right].mul*tree[v].mul)%mod ;
        }
        tree[v].mul = ;
    }
    if(tree[v].add)
    {
        if(tree[left].eq != -)
        tree[left].eq = (tree[left].eq + tree[v].add)%mod ;
        else
        {
            push_down(left) ;
            tree[left].add = (tree[left].add + tree[v].add)%mod ;
        }
        if(tree[right].eq != -)
        tree[right].eq = (tree[right].eq + tree[v].add)%mod ;
        else
        {
            push_down(right) ;
            tree[right].add = (tree[right].add + tree[v].add)%mod ;
        }
        tree[v].add =  ;
    }
}
void update(int l , int r , int v , int op , int c)
{
    if(l <= tree[v].l && tree[v].r <= r)
    {
        if(op == )
        {
            tree[v].add =  ;tree[v].mul = ;
            tree[v].eq  = c ;
            return ;
        }
        if(tree[v].eq != -)
        {
            if(op == )tree[v].eq = (tree[v].eq + c)%mod ;
            else tree[v].eq = (tree[v].eq*c)%mod ;
        }
        else
        {
            push_down(v) ;
            if(op == )tree[v].add = (tree[v].add + c)%mod ;
            else tree[v].mul = (tree[v].mul*c)%mod ;
        }
        return ;
    }
    push_down(v) ;
    int mid = (tree[v].l + tree[v].r) >>  ;
    if(l <= mid)update(l , r ,left , op , c) ;
    if(r > mid)update(l , r , right , op , c) ;
}
int query(int l , int r , int v , int q)
{
    if(tree[v].l >= l && tree[v].r <= r && tree[v].eq != -)
    {
        int ans = ;
        for(int i = ;i <= q;i++)
        ans = (ans * tree[v].eq)%mod ;
        return (ans*((tree[v].r - tree[v].l + )%mod))%mod ;
    }
    push_down(v) ;
    int mid = (tree[v].l  + tree[v].r) >>  ;
    if(l > mid)return query(l , r , right, q) ;
    else if(r <= mid)return query(l , r ,left ,q) ;
    else return (query(l , mid , left , q) + query(mid +  , r , right , q))%mod ;
}
int main()
{
    //freopen("in.txt" ,"r" , stdin) ;
    int n , m ;
    while(scanf("%d%d" , &n , &m) &&(n+m))
    {
        int op , x ,  y , c;
        build( , n , ) ;
        while(m--)
        {
            scanf("%d%d%d%d" , &op , &x , &y , &c) ;
            if(op == )
            printf("%d\n" , (query(x, y ,  , c)%mod)) ;
            else update(x , y ,  , op , c) ;
        }
    }
    return   ;
}

C++代码二

解释

　　平方和这样来推：(a + c)^{2 =} a^{2 +} c² + 2ac  , 即sum2[rt] = sum2[rt] + (r - l + 1) * c * c + 2 * sum1[rt] * c；

　　立方和这样推：(a + c)^{3 =} a³ + c³ + 3a(a² + ac) , 即sum3[rt] = sum3[rt] + (r - l + 1) * c * c * c + 3 * c * (sum2[rt] + sum1[rt] * c)；

　　几个注意点：add标记取消的时候是置0，mul标记取消的时候是置1；在PushDown()中也也要注意取消标记，如set操作中取消add和mul，mul操作中更新add； 在add操作中要注意sum3 , sum2 , sum1的先后顺序，一定是先sum3 , 然后sum2 , 最后sum1； int容易爆，还是用LL要保险一点； 最后就是运算较多，不要漏掉东西。

当然这种方法有取巧的成分

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
typedef long long ll;
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = ;
const int maxn =  + ;
const int N = ;
ll add[maxn << ] , set[maxn << ] , mul[maxn << ];
ll sum1[maxn << ] , sum2[maxn << ] , sum3[maxn << ];
void PushUp(int rt)
{
    sum1[rt] = (sum1[rt << ] + sum1[rt <<  | ]) % MOD;
    sum2[rt] = (sum2[rt << ] + sum2[rt <<  | ]) % MOD;
    sum3[rt] = (sum3[rt << ] + sum3[rt <<  | ]) % MOD;
}
void build(int l , int r , int rt)
{
    add[rt] = set[rt] = ;
    mul[rt] = ;
    if(l == r) {
        sum1[rt] = sum2[rt] = sum3[rt] = ;
        return;
    }
    int m = (l + r) >> ;
    build(lson);
    build(rson);
    PushUp(rt);
}
void PushDown(int rt , int len)
{
    if(set[rt]) {
        set[rt << ] = set[rt <<  | ] = set[rt];
        add[rt << ] = add[rt <<  | ] = ;    //注意这个也要下放
        mul[rt << ] = mul[rt <<  | ] = ;
        ll tmp = ((set[rt] * set[rt]) % MOD) * set[rt] % MOD;
        sum1[rt << ] = ((len - (len >> )) % MOD) * (set[rt] % MOD) % MOD;
        sum1[rt <<  | ] = ((len >> ) % MOD) * (set[rt] % MOD) % MOD;
        sum2[rt << ] = ((len - (len >> )) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
        sum2[rt <<  | ] = ((len >> ) % MOD) * ((set[rt] * set[rt]) % MOD) % MOD;
        sum3[rt << ] = ((len - (len >> )) % MOD) * tmp % MOD;
        sum3[rt <<  | ] = ((len >> ) % MOD) * tmp % MOD;
        set[rt] = ;
    }
    if(mul[rt] != ) {    //这个就是mul[rt] != 1 ， 当时我这里没注意所以TLE了
        mul[rt << ] = (mul[rt << ] * mul[rt]) % MOD;
        mul[rt <<  | ] = (mul[rt <<  | ] * mul[rt]) % MOD;
        if(add[rt << ])    //注意这个也要下放
            add[rt << ] = (add[rt << ] * mul[rt]) % MOD;
        if(add[rt <<  | ])
            add[rt <<  | ] = (add[rt <<  | ] * mul[rt]) % MOD;
        ll tmp = (((mul[rt] * mul[rt]) % MOD * mul[rt]) % MOD);
        sum1[rt << ] = (sum1[rt << ] * mul[rt]) % MOD;
        sum1[rt <<  | ] = (sum1[rt <<  | ] * mul[rt]) % MOD;
        sum2[rt << ] = (sum2[rt << ] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
        sum2[rt <<  | ] = (sum2[rt <<  | ] % MOD) * ((mul[rt] * mul[rt]) % MOD) % MOD;
        sum3[rt << ] = (sum3[rt << ] % MOD) * tmp % MOD;
        sum3[rt <<  | ] = (sum3[rt <<  | ] % MOD) * tmp % MOD;
        mul[rt] = ;
    }
    if(add[rt]) {
        add[rt << ] += add[rt];    //add是+= ， mul是*=
        add[rt <<  | ] += add[rt];
        ll tmp = (add[rt] * add[rt] % MOD) * add[rt] % MOD;        //注意sum3 , sum2 , sum1的先后顺序
        sum3[rt << ] = (sum3[rt << ] + (tmp * (len - (len >> )) % MOD) +  * add[rt] * ((sum2[rt << ] + sum1[rt << ] * add[rt]) % MOD)) % MOD;
        sum3[rt <<  | ] = (sum3[rt <<  | ] + (tmp * (len >> ) % MOD) +  * add[rt] * ((sum2[rt <<  | ] + sum1[rt <<  | ] * add[rt]) % MOD)) % MOD;
        sum2[rt << ] = (sum2[rt << ] + ((add[rt] * add[rt] % MOD) * (len - (len >> )) % MOD) + ( * sum1[rt << ] * add[rt] % MOD)) % MOD;
        sum2[rt <<  | ] = (sum2[rt <<  | ] + (((add[rt] * add[rt] % MOD) * (len >> )) % MOD) + ( * sum1[rt <<  | ] * add[rt] % MOD)) % MOD;
        sum1[rt << ] = (sum1[rt << ] + (len - (len >> )) * add[rt]) % MOD;
        sum1[rt <<  | ] = (sum1[rt <<  | ] + (len >> ) * add[rt]) % MOD;
        add[rt] = ;
    }
}
void update(int L , int R , int c , int ch , int l , int r , int rt)
{
    if(L <= l && R >= r) {
        if(ch == ) {
            set[rt] = c;
            add[rt] = ;
            mul[rt] = ;
            sum1[rt] = ((r - l + ) * c) % MOD;
            sum2[rt] = ((r - l + ) * ((c * c) % MOD)) % MOD;
            sum3[rt] = ((r - l + ) * (((c * c) % MOD) * c % MOD)) % MOD;
        } else if(ch == ) {
            mul[rt] = (mul[rt] * c) % MOD;
            if(add[rt])
                add[rt] = (add[rt] * c) % MOD;
            sum1[rt] = (sum1[rt] * c) % MOD;
            sum2[rt] = (sum2[rt] * (c * c % MOD)) % MOD;
            sum3[rt] = (sum3[rt] * ((c * c % MOD) * c % MOD)) % MOD;
        } else if(ch == ) {
            add[rt] += c;
            ll tmp = (((c * c) % MOD * c) % MOD * (r - l + )) % MOD;    //(r - l + 1) * c^3
            sum3[rt] = (sum3[rt] + tmp +  * c * ((sum2[rt] + sum1[rt] * c) % MOD)) % MOD;
            sum2[rt] = (sum2[rt] + (c * c % MOD * (r - l + ) % MOD) +  * sum1[rt] * c) % MOD;
            sum1[rt] = (sum1[rt] + (r - l + ) * c) % MOD;
        }
        return;
    }
    PushDown(rt , r - l + );
    int m = (l + r) >> ;
    if(L > m)
        update(L , R , c , ch , rson);
    else if(R <= m)
        update(L , R , c , ch , lson);
    else {
        update(L , R , c , ch , lson);
        update(L , R , c , ch , rson);
    }
    PushUp(rt);
}
ll query(int L , int R , int p , int l , int r , int rt)
{
    if(L <= l && R >= r) {
        if(p == )
            return sum1[rt] % MOD;
        else if(p == )
            return sum2[rt] % MOD;
        else
            return sum3[rt] % MOD;
    }
    PushDown(rt , r - l + );
    int m = (l + r) >> ;
    if(L > m)
        return query(L , R , p , rson);
    else if(R <= m)
        return query(L , R , p , lson);
    else
        return (query(L , R , p , lson) + query(L , R , p , rson)) % MOD;
}
int main()
{
    int n , m;
    int a , b , c , ch;
    while(~scanf("%d %d" , &n , &m))
    {
        if(n ==  && m == )
            break;
        build( , n , );
        while(m--) {
            scanf("%d %d %d %d" , &ch , &a , &b , &c);
            if(ch != ) {
                update(a , b , c , ch ,  , n , );
            } else {
                printf("%lld\n" , query(a , b , c ,  , n , ));
            }
        }
    }
    return ;
}