HDU P4578 Transformation

时间：2023-12-29 09:10:50
Problem Description
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. 
                                                         --by HDUoj
http://acm.hdu.edu.cn/showproblem.php?pid=4578
因为p<4,所以，直接线段树维护区间和，平方和，立方和，三棵树，打上乘法，加法，更改标记，注意down的顺序；
所以，会线段树的话，这题主要考代码能力......和信仰。
记得及时取模。
代码如下：
 #include<cstdio>

 #define mod 10007

 using namespace std;

 long long tree[][];

 long long mark1[],mark2[],mark3[];

 int n,m,L,R;

 long long a,b;

 void work();

 void build(int ,int ,int );

 void up(int );

 void down(int ,int ,int );

 void change(int ,int ,int );

 long long sum(int ,int ,int );

 int main()

 {

     while()

     {

         scanf("%d%d",&n,&m);

         if(n==&&m==)

             return ;

         work();

     }

 }

 void work()

 {

     int i;

     long long ans=;

     build(,n,);

     for(i=;i<=m;i++)

     {

         scanf("%d%d%d%d",&b,&L,&R,&a);

         if(b==)

         {

                 ans=sum(,n,);

                 printf("%lld\n",ans%mod);

         }

         else

             change(,n,);

     }

 }

 void build(int l,int r,int nu)

 {

     tree[][nu]=tree[][nu]=tree[][nu]=mark1[nu]=mark3[nu]=;

     mark2[nu]=;

     if(l==r)

         return ;

     int mid=(l+r)>>;

     build(l,mid,nu<<);

     build(mid+,r,nu<<|);

 }

 void up(int nu)

 {

     tree[][nu]=(tree[][nu<<]+tree[][nu<<|])%mod;

     tree[][nu]=(tree[][nu<<]+tree[][nu<<|])%mod;

     tree[][nu]=(tree[][nu<<]+tree[][nu<<|])%mod;

 }

 void down(int l,int r,int nu)

 {

     int mid=(l+r)>>;

     if(mark3[nu])

     {

         tree[][nu<<]=tree[][nu<<]=tree[][nu<<]=;

         mark1[nu<<]=;mark2[nu<<]=;

         mark3[nu<<]=mark3[nu];

         tree[][nu<<|]=tree[][nu<<|]=tree[][nu<<|]=;

         mark1[nu<<|]=;mark2[nu<<|]=;

         mark3[nu<<|]=mark3[nu];

     }

     tree[][nu<<]=(tree[][nu<<]*mark2[nu]*mark2[nu]*mark2[nu])%mod;

     tree[][nu<<]=(tree[][nu<<]*mark2[nu]*mark2[nu])%mod;

     tree[][nu<<]=(tree[][nu<<]*mark2[nu])%mod;

     tree[][nu<<]=(tree[][nu<<]+*tree[][nu<<]*mark1[nu]+*tree[][nu<<]*mark1[nu]*mark1[nu]+(mid-l+)*mark1[nu]*mark1[nu]*mark1[nu])%mod;

     tree[][nu<<]=(tree[][nu<<]+*mark1[nu]*tree[][nu<<]+(mid-l+)*mark1[nu]*mark1[nu])%mod;

     tree[][nu<<]=(tree[][nu<<]+mark1[nu]*(mid-l+))%mod;

     mark2[nu<<]=(mark2[nu<<]*mark2[nu])%mod;

     mark1[nu<<]=(mark1[nu<<]*mark2[nu]+mark1[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]*mark2[nu]*mark2[nu]*mark2[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]*mark2[nu]*mark2[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]*mark2[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]+*tree[][nu<<|]*mark1[nu]+*tree[][nu<<|]*mark1[nu]*mark1[nu]+(r-mid)*mark1[nu]*mark1[nu]*mark1[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]+*mark1[nu]*tree[][nu<<|]+(r-mid)*mark1[nu]*mark1[nu])%mod;

     tree[][nu<<|]=(tree[][nu<<|]+mark1[nu]*(r-mid))%mod;

     mark2[nu<<|]=(mark2[nu<<|]*mark2[nu])%mod;

     mark1[nu<<|]=(mark1[nu<<|]*mark2[nu]+mark1[nu])%mod;

     mark1[nu]=mark3[nu]=;mark2[nu]=;

 }

 void change(int l,int r,int nu)

 {

     if(L<=l&&r<=R)

     {

         if(b==)

         {

             mark1[nu]=a;

             mark2[nu]=;

             mark3[nu]=;

             tree[][nu]=a*(r-l+)%mod;

             tree[][nu]=(a*a*(r-l+))%mod;

             tree[][nu]=(a*a*a*(r-l+))%mod;

         }

         if(b==)

         {

             mark1[nu]=(mark1[nu]*a)%mod;

             mark2[nu]=(mark2[nu]*a)%mod;

             tree[][nu]=(tree[][nu]*a)%mod;

             tree[][nu]=(tree[][nu]*a*a)%mod;

             tree[][nu]=(tree[][nu]*a*a*a)%mod;

         }

         if(b==)

         {

             mark1[nu]=(mark1[nu]+a)%mod;

             tree[][nu]=(tree[][nu]+*tree[][nu]*a+*tree[][nu]*a*a+(r-l+)*a*a*a)%mod;

             tree[][nu]=(tree[][nu]+*a*tree[][nu]+(r-l+)*a*a)%mod;

             tree[][nu]=(tree[][nu]+a*(r-l+))%mod;

         }

         return;

     }

     down(l,r,nu);

     int mid=(l+r)>>;

     if(L<=mid)

         change(l,mid,nu<<);

     if(R>=mid+)

         change(mid+,r,nu<<|);

     up(nu);

 }

 long long sum(int l,int r,int nu)

 {

     long long su=;

     if(L<=l&&r<=R)

         return tree[a][nu];

     down(l,r,nu);

     int mid=(l+r)>>;

     if(L<=mid)

         su+=sum(l,mid,nu<<);

     if(R>=mid+)

         su+=sum(mid+,r,nu<<|);

     su=su%mod;

     return su;

 }
祝AC哟；

相关文章