Transformation

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

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杭州赛区全国邀请赛

题目大意：开始有n数全为0的序列。

现在让你进行区间操作，操作1：给区间ui,vi每个数加wi。

　　　　　　　　　　　操作2：给区间ui,vi每个数乘wi

　　　　　　　　　　　操作3：给区间ui,vi每个数赋值为wi

　　　　　　　　　　　操作4：查询区间ui,vi的ci次方和。　　　　　　　ci取值1，2,3　结果取模。

解题思路：很明显是线段树操作，但是这个线段树比较复杂。。。（TM写了1天半，弱就是弱）。首先我们考虑由于需要有三种不同的结果，1次方，2次方，3次方，所以我们需要维护出来3个结果，sum1，sum2，sum3分别表示1次方和，2次方和，3次方和。如果上面的更新操作只有一个，次方和是可以很容易得到的。但是现在有赋值，有加和，有乘积，而且这些操作的顺序也不确定，不同的顺序的结果也不相同。所以应该确定下放标记的优先级别，我们首先应该知道，如果赋值操作，那么前边的所有加和操作与乘积操作就应该无效了，所以下放赋值操作应该优先考虑。然后就是乘积和加和操作的优先级了，这里我们考虑将每一个数表示成multi*x+add的形式，初始时multi为1，x为0，add为0。如果我们首先给一段区间加一个数b，那么让这个区间内所有的add变为b，如果我们又给这个区间乘上一个a，那么这个区间每个数都变成了a*x+b*a。如果我们首先给一段区间乘上一个数a，那么这个区间内所有的multi变为a，如果我们又给这个区间加上一个b，那么这个区间的每个数都变成了a*x+b。可以看出，两种下放顺序造成的影响在于add的不同，所以我们想让这个结果达到一个统一就应该首先让让乘积标记下放，然后左右儿子的add变为左右儿子的add*当前节点的multi+当前节点的add。左右儿子的multi变为左右儿子的multi*当前节点的multi。次方和需要经过简单推导得出。

二次方和：sigma((ai*y+w)^2) = y*y*sigma(ai^2) + 2*w*y*sigma(ai) + sigma(w^2)。

三次方和：sigma((ai*y+w)^3) = y^3*sigma(ai^3) + sigma(w^3) + 3*w*y^2*sigma(ai^2) + 3*w^2*y*sigma(ai)。

#include<bits/stdc++.h>

using namespace std;

#define mid (L+R)/2

#define lson rt*2,L,mid

#define rson rt*2+1,mid+1,R

typedef long long INT;

const int maxn = 120000;

const int mod = 10007;

struct SegTree{

    int add,multi,setv;

    int sum1,sum2,sum3;

}segs[maxn*4];

void PushUp(int rt,int L,int R){

    segs[rt].sum1 = (segs[rt*2].sum1 + segs[rt*2+1].sum1)% mod;

    segs[rt].sum2 = (segs[rt*2].sum2 + segs[rt*2+1].sum2)% mod;

    segs[rt].sum3 = (segs[rt*2].sum3 + segs[rt*2+1].sum3)% mod;

}

void buildtree(int rt,int L,int R){

    segs[rt].multi = 1;

    segs[rt].add = segs[rt].setv = 0;

    segs[rt].sum1 = segs[rt].sum2 = segs[rt].sum3 = 0;

    if(L == R){

        return ;

    }

    buildtree(lson);

    buildtree(rson);

}

void PushDown(int rt,int L,int R){

    if(segs[rt].setv){  //考虑下放赋值标记

        segs[rt*2].setv = segs[rt*2+1].setv = segs[rt].setv;

        segs[rt*2].add = segs[rt*2+1].add = 0;

        segs[rt*2].multi = segs[rt*2+1].multi = 1;

        segs[rt*2].sum1 = (mid-L+1)*segs[rt].setv % mod;

        segs[rt*2].sum2 = (mid-L+1)*segs[rt].setv %mod *segs[rt].setv % mod;

        segs[rt*2].sum3 = (mid-L+1)*segs[rt].setv %mod *segs[rt].setv % mod *segs[rt].setv % mod;

        segs[rt*2+1].sum1 = (R-mid)*segs[rt].setv % mod;

        segs[rt*2+1].sum2 = (R-mid)*segs[rt].setv % mod *segs[rt].setv % mod;

        segs[rt*2+1].sum3 = (R-mid)*segs[rt].setv % mod *segs[rt].setv % mod *segs[rt].setv % mod;

        segs[rt].setv = 0;

    }

    if(segs[rt].multi != 1 || segs[rt].add){//如果有加和标记或者乘积标记

        segs[rt*2].add = (segs[rt].multi * segs[rt*2].add %mod + segs[rt].add) % mod;

        segs[rt*2].multi = segs[rt].multi * segs[rt*2].multi % mod;

        int sum1, sum2 ,sum3;

        //一次方和

        sum1 = (segs[rt*2].sum1*segs[rt].multi %mod + (mid-L+1)*segs[rt].add %mod) % mod;

        //平方和

        sum2 = (segs[rt*2].sum2*segs[rt].multi %mod *segs[rt].multi %mod + 2*segs[rt].add * segs[rt].multi %mod *segs[rt*2].sum1 %mod + (mid-L+1)*segs[rt].add %mod *segs[rt].add %mod ) % mod;

        //三次方和

        sum3 = segs[rt*2].sum3*segs[rt].multi %mod *segs[rt].multi %mod *segs[rt].multi %mod;

        sum3 = (sum3 + 3*segs[rt].add*segs[rt].multi %mod *segs[rt].multi %mod *segs[rt*2].sum2 %mod) % mod;

        sum3 = (sum3 + 3*segs[rt].add*segs[rt].add %mod *segs[rt].multi %mod *segs[rt*2].sum1 %mod ) % mod;

        sum3 = (sum3 + (mid-L+1)*segs[rt].add %mod *segs[rt].add %mod *segs[rt].add %mod ) % mod;

        segs[rt*2].sum1 = sum1;

        segs[rt*2].sum2 = sum2;

        segs[rt*2].sum3 = sum3;

        //同理，更新右儿子

        segs[rt*2+1].add = (segs[rt*2+1].add*segs[rt].multi %mod + segs[rt].add) % mod;

        segs[rt*2+1].multi = segs[rt*2+1].multi * segs[rt].multi % mod;

        sum1 = (segs[rt*2+1].sum1*segs[rt].multi %mod + (R-mid)*segs[rt].add %mod) % mod;

        sum2 = (segs[rt*2+1].sum2*segs[rt].multi %mod *segs[rt].multi %mod + 2*segs[rt].add*segs[rt].multi %mod *segs[rt*2+1].sum1 %mod + (R-mid)*segs[rt].add %mod *segs[rt].add %mod) % mod;

        sum3 = segs[rt*2+1].sum3*segs[rt].multi %mod *segs[rt].multi %mod *segs[rt].multi %mod;

        sum3 = (sum3 + 3*segs[rt].add*segs[rt].multi %mod *segs[rt].multi %mod *segs[rt*2+1].sum2 %mod) % mod;

        sum3 = (sum3 + 3*segs[rt].add*segs[rt].add %mod *segs[rt].multi %mod *segs[rt*2+1].sum1 %mod ) % mod;

        sum3 = (sum3 + (R-mid)*segs[rt].add %mod *segs[rt].add %mod *segs[rt].add %mod ) % mod;

        segs[rt*2+1].sum1 = sum1;

        segs[rt*2+1].sum2 = sum2;

        segs[rt*2+1].sum3 = sum3;

        segs[rt].add = 0;

        segs[rt].multi = 1;

    }

}

void Update(int rt,int L,int R,int l_ran,int r_ran,int c,int typ){

    if(l_ran <= L&&R <= r_ran){

        if(typ == 1){   //加和

            segs[rt].add = (segs[rt].add + c)%mod;

            segs[rt].sum3 = (segs[rt].sum3 + (R-L+1)*c %mod *c %mod *c %mod + 3*c %mod *segs[rt].sum2 %mod   + 3*c %mod *c %mod *segs[rt].sum1 %mod ) % mod;

            segs[rt].sum2 = (segs[rt].sum2 + (R-L+1)*c %mod *c %mod + 2*segs[rt].sum1 %mod *c %mod ) % mod;

            segs[rt].sum1 = ((R-L+1)*c %mod + segs[rt].sum1) % mod;

        }else if(typ == 2){ //乘积

            //乘积对当前节点的和跟乘都有影响

            segs[rt].add =  segs[rt].add * c % mod;

            segs[rt].multi = segs[rt].multi * c % mod;

            segs[rt].sum1 = segs[rt].sum1 * c % mod;

            segs[rt].sum2 = segs[rt].sum2 * c %mod *c %mod;

            segs[rt].sum3 = segs[rt].sum3 *c %mod *c %mod *c % mod;

        }else{  //赋值

            segs[rt].setv = c;

            segs[rt].multi = 1;

            segs[rt].add = 0;

            segs[rt].sum1 = c*(R-L+1) % mod;

            segs[rt].sum2 = c*(R-L+1) % mod*c % mod;

            segs[rt].sum3 = c*(R-L+1) % mod*c % mod *c %mod ;

        }

        return ;

    }

    PushDown(rt,L,R);

    if(l_ran <= mid)

        Update(lson,l_ran,r_ran,c,typ);

    if(r_ran > mid)

        Update(rson,l_ran,r_ran,c,typ);

    PushUp(rt,L,R);

}

int query(int rt,int L,int R,int l_ran,int r_ran,int pw){

    if(l_ran <= L&&R <= r_ran){

        if(pw == 1){

            return segs[rt].sum1;

        }else if(pw == 2){

            return segs[rt].sum2;

        }else{

            return segs[rt].sum3;

        }

    }

    PushDown(rt,L,R);

    int ret = 0;

    if(l_ran <= mid){

        ret = (ret + query(lson,l_ran,r_ran,pw)) % mod;

    }

    if(r_ran > mid){

        ret = (ret + query(rson,l_ran,r_ran,pw)) % mod;

    }

    return ret;

}

int main(){

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){

        int c,u,v,w;

        buildtree(1,1,n);

        for(int i = 1; i <= m; i++){

            scanf("%d%d%d%d",&c,&u,&v,&w);

            if(c == 4){

                int res = query(1,1,n,u,v,w);

                printf("%d\n",res);

            }else {

                 Update(1,1,n,u,v,w,c);

            }

        }

    }

    return 0;

}

巴特西

HDU 4578——Transformation——————【线段树区间操作、确定操作顺序】

Transformation

最新文章

热门文章