首页 > ACM题库 > HDU-杭电 > HDU 4578-Transformation-线段树-[解题报告]HOJ
2015
09-16

HDU 4578-Transformation-线段树-[解题报告]HOJ

Transformation

问题描述 :

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

输入:

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.

输出:

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.

样例输入:

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

样例输出:

307
7489

题目链接

题目大意:n个数(初始为0)m个操作,操作类型有4中,操作1把区间的每个数+a,操作2把区间的每个数*a.,操作3把区间的每个数=a,操作4,查询区间每个数p次方的和(1<=p<=3)

这个跟hdu3397有点类似。更新操作我还是分成两类(1)=  (2)*和+。 查询操作:p只有三种可能,所以可以直接把次方,2次方,3次方的值存进去,一起更新

对于=更新操作:如果之前有*和+的标记,那可以忽略到*+操作,直接=操作,这个最简单,sum1=val,sum2=val*val,sum3=val*val*val;

对于*+操作:如果之前有=标记,就不能忽略了,所以pushdown优先考略=操作。 *+操作可以一起(a*x+c).

                       注意:在*操作更新时,要一起更新+操作,因为(x+c)*a;

                    然后对于 (ax+c)^3=a^3*x^3+3*a^2*c*x^2+3*a*c^2*x+c^3,也就是root[t].sum3=a^3*root[t].sum3+3*a^2*c*root[t].sum2+3*a*c^2*root[t].sum1+c^3*(root[t].r-roo[t].l+1);

                             同理 root[t].sum2=root[t].sum2*a^2+root[t].sum1*c*2+c^2*(root[t].r-root[t].l+1);

                                     root[t].sum1=root[t].sum1*a+c*(root[t].r-root[t].l+1);

                                   注意:sum3,sum2,sum1在这个操作中的顺序不能变。

struct node
{
    int l,r;
    int lazy1,lazy2,lazy3,p1,p2,p3;//lazy1加法,lazy2乘法,lazy3等于,p1一次方和,p2二次方和,p3三次方和;
}root[N*6];

Ps:一开始定义的long long ,结果TLE疯了,后来把long long 全改成int,就过了,据说long  long 比int 慢了一倍==

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
inline int input()
{
    int r=0;
    char c;
    c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') r=r*10+c-'0',c=getchar();
    return r;
}


#define N 100010
#define M 10007
struct node
{
    int l,r;
    int lazy1,lazy2,lazy3,p1,p2,p3;
}root[N*6];

inline void change_eq(int t,int val)
{
    int l=root[t].r-root[t].l+1;
    root[t].lazy1=0;
    root[t].lazy2=1;
    root[t].lazy3=val%M;
    root[t].p1=val*l%M;
    root[t].p2=val%M*val%M*l%M;
    root[t].p3=val%M*val%M*val%M*l%M;
}
inline void change_add_mut(int t,int v1,int v2)
{
    int l=root[t].r-root[t].l+1;
    root[t].lazy2=root[t].lazy2*(v2%M)%M;
    root[t].lazy1=(root[t].lazy1*v2%M+v1%M)%M;
    root[t].p3=(root[t].p3%M*v2%M*v2%M*v2%M+v1%M*v1%M*v1%M*l%M+3*v2%M*v2%M*v1%M*root[t].p2%M+3*v2%M*v1%M*v1%M*root[t].p1%M)%M;
    root[t].p2=(root[t].p2%M*v2%M*v2%M+v1%M*v1%M*l%M+2*v2%M*v1%M*root[t].p1%M)%M;
    root[t].p1 =(v2 *root[t].p1%M +v1%M*l%M)%M;
}

inline void pushup(int t)
{
    root[t].p1=(root[t*2].p1%M+root[t*2+1].p1%M)%M;
    root[t].p2=(root[t*2].p2%M+root[t*2+1].p2%M)%M;
    root[t].p3=(root[t*2].p3%M+root[t*2+1].p3%M)%M;
}
inline void pushdown_eq(int t)
{
    if(root[t].l==root[t].r) return;
    if(root[t].lazy3!=0)
    {
        change_eq(t*2,root[t].lazy3);
        change_eq(t*2+1,root[t].lazy3);
        root[t].lazy3=0;
    }
}
inline void pushdown_add_mut(int t)
{
    if(root[t].l==root[t].r) return;
    if(root[t].lazy1!=0||root[t].lazy2!=1)
    {
        change_add_mut(t*2,root[t].lazy1,root[t].lazy2);
        change_add_mut(t*2+1,root[t].lazy1,root[t].lazy2);
        root[t].lazy1=0;
        root[t].lazy2=1;
    }
}


inline void build_tree(int t,int x,int y)
{
    root[t].l=x;
    root[t].r=y;
    root[t].p1=root[t].p2=root[t].p3=0;
    root[t].lazy1=root[t].lazy3=0;
    root[t].lazy2=1;
    if(x==y) return;
    int m=(x+y)>>1;
    build_tree(t*2,x,m);
    build_tree(t*2+1,m+1,y);
}
inline void Modefiy_eq(int t,int x,int y,int val)
{
    int l=root[t].l;
    int r=root[t].r;
    if(l==x&&r==y)
    {
        change_eq(t,val);
        return;
    }
    pushdown_eq(t);
    pushdown_add_mut(t);
    int m=(l+r)>>1;
    if(x<=m) Modefiy_eq(t*2,x,min(m,y),val);
    if(y>m)  Modefiy_eq(t*2+1,max(x,m+1),y,val);
    pushup(t);
}
inline void Modefiy_add_mut(int t,int x,int y,int val,int op)
{
    int l=root[t].l;
    int r=root[t].r;
    if(l==x&&r==y)
    {
        val%=M;
        if(op==1)
        {
            int l=root[t].r-root[t].l+1;
            root[t].lazy1=(root[t].lazy1+val)%M;
            root[t].p3=(root[t].p3%M+3*val%M*root[t].p2%M+3*val%M*val%M*root[t].p1%M+val%M*val%M*val%M*l%M)%M;
            root[t].p2=(root[t].p2%M+root[t].p1%M*2*val%M+val%M*val%M*l%M)%M;
            root[t].p1=(root[t].p1+val*l%M)%M;
        }
        else if(op==2)
        {
            root[t].lazy1 =(root[t].lazy1*val%M)%M;
            root[t].lazy2 =(root[t].lazy2*val%M)%M;
            root[t].p1=(root[t].p1%M*val%M)%M;
            root[t].p2=(root[t].p2%M*val%M*val%M)%M;
            root[t].p3=(root[t].p3%M*val%M*val%M*val%M)%M;
        }
        return;
    }
    pushdown_eq(t);
    pushdown_add_mut(t);
    int m=(l+r)>>1;
    if(x<=m) Modefiy_add_mut(t*2,x,min(m,y),val,op);
    if(y>m)  Modefiy_add_mut(t*2+1,max(m+1,x),y,val,op);
    pushup(t);
}

inline int query(int t,int x,int y,int op)
{
    int l=root[t].l;
    int r=root[t].r;
    if(l==x&&r==y)
    {
        if(op==1) return root[t].p1%M;
        else if(op==2) return root[t].p2%M;
        else if(op==3) return root[t].p3%M;
    }
    pushdown_eq(t);
    pushdown_add_mut(t);
    int m=(l+r)>>1;
    int ans=0;
    if(x<=m) ans+=query(t*2,x,min(m,y),op),ans%=M;
    if(y>m)  ans+=query(t*2+1,max(x,m+1),y,op),ans%=M;
    return ans%M;
}

int n,m,op,x,y,z;
int main()
{
    while(1)
    {
        n=input(),m=input();
        if(n==0&&m==0) break;
        build_tree(1,1,n);
        while(m--)
        {
            op=input(),x=input(),y=input(),z=input();
            if(op==1) Modefiy_add_mut(1,x,y,z,1);
            else if(op==2) Modefiy_add_mut(1,x,y,z,2);
            else if(op==3) Modefiy_eq(1,x,y,z);
            else if(op==4) printf("%d\n",query(1,x,y,z));
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zhuhuangjian/article/details/9933903