HDU4578 Transformation (多操作线段树)

传送门

终于过了这道题。。

要注意标记之间的影响，和add操作时更新求和的顺序。

same 区间每个数设置为x标记

mult 区间每个数乘x标记

add 区间每个数加x标记

①：当打same标记时，mult标记和add标记就没用了，要初始化。

②：当打mult标记时，add标记也要乘相应的值。

---------------求和可以递推过来---------------

1次方求和就正常求和

即：sum1[rt]=sum1[rt]+(r-l+1)*val;

2次方可以由 (x+val)²= x²+val²+2*x*val

即：sum2[rt]=sum2[rt]+2*sum1[rt]*val+(r-l+1)*val*val;

3次方可以由 (x+val)³= x³+val³+3*x²*val+3*x*val²

即：sum3[rt]=sum3[rt]+(r-l+1)*val*val*val+3*sum2[rt]*val+3*sum1[rt]*val*val;

再次注意 add求和要按照sum3，sum2, sum1的顺序！

算是又对取模有了一点了解。。

a*b*c*d 取模为 (a*b%mod) * (c*d%mod) %mod

a+b*c*d+3*a*b*c*d 取模为 (a + (b*c)%mod*d + 3*((a*b)%mod)*((c*d)%mod)%mod)%mod

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int mod=;

 const int maxx=;

 ll add[maxx<<],mult[maxx<<],same[maxx<<];

 ll sum1[maxx<<],sum2[maxx<<],sum3[maxx<<];

 int n,m,sum;

 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]=same[rt]=;

     mult[rt]=;

     if(l==r) {

         sum1[rt]=sum2[rt]=sum3[rt]=;

         return;

     }

     int mid=(l+r)>>;

     build(l,mid,rt<<);

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

     pushup(rt);

 }

 void pushdown(int rt,int len) {  //下传标记

     if(same[rt]) {

         sum1[rt<<]=(len-(len>>))*same[rt]%mod;

         sum1[rt<<|]=(len>>)*same[rt]%mod;

         sum2[rt<<]=((len-(len>>))*same[rt]%mod)*same[rt]%mod;

         sum2[rt<<|]=((len>>)*same[rt]%mod)*same[rt]%mod;

         sum3[rt<<]=((len-(len>>))*same[rt]%mod)*(same[rt]*same[rt]%mod)%mod;

         sum3[rt<<|]=((len>>)*same[rt]%mod)*(same[rt]*same[rt]%mod)%mod;

         same[rt<<]=same[rt<<|]=same[rt];

         add[rt<<]=add[rt<<|]=;  //也需要改变

         mult[rt<<]=mult[rt<<|]=; //也需要改变

         same[rt]=;

     }

     if(mult[rt]!=) {

         mult[rt<<]=mult[rt<<]*mult[rt]%mod;

         mult[rt<<|]=mult[rt<<|]*mult[rt]%mod;

         add[rt<<]=add[rt<<]*mult[rt]%mod; //改变

         add[rt<<|]=add[rt<<|]*mult[rt]%mod;  //改变

         sum1[rt<<]=sum1[rt<<]*mult[rt]%mod;

         sum1[rt<<|]=sum1[rt<<|]*mult[rt]%mod;

         sum2[rt<<]=(sum2[rt<<]*mult[rt]%mod)*mult[rt]%mod;

         sum2[rt<<|]=(sum2[rt<<|]*mult[rt]%mod)*mult[rt]%mod;

         sum3[rt<<]=(sum3[rt<<]*mult[rt]%mod)*(mult[rt]*mult[rt]%mod)%mod;

         sum3[rt<<|]=(sum3[rt<<|]*mult[rt]%mod)*(mult[rt]*mult[rt]%mod)%mod;

         mult[rt]=;

     }

     if(add[rt]) {

         add[rt<<]=(add[rt<<]+add[rt])%mod;

         add[rt<<|]=(add[rt<<|]+add[rt])%mod;

         sum3[rt<<]=(sum3[rt<<]+*sum2[rt<<]*add[rt]%mod+*(sum1[rt<<]*add[rt]%mod)*add[rt]%mod+(add[rt]*add[rt]%mod)*(add[rt]*(len-(len>>))%mod))%mod;

         sum3[rt<<|]=(sum3[rt<<|]+*sum2[rt<<|]*add[rt]%mod+*(sum1[rt<<|]*add[rt]%mod)*add[rt]%mod+(add[rt]*add[rt]%mod)*(add[rt]*(len>>)%mod))%mod;

         sum2[rt<<]=(sum2[rt<<]+*sum1[rt<<]*add[rt]%mod+(add[rt]*add[rt]%mod)*(len-(len>>))%mod)%mod;

         sum2[rt<<|]=(sum2[rt<<|]+*sum1[rt<<|]*add[rt]%mod+(add[rt]*add[rt]%mod)*(len>>)%mod)%mod;

         sum1[rt<<]=(sum1[rt<<]+(len-(len>>))*add[rt]%mod)%mod;

         sum1[rt<<|]=(sum1[rt<<|]+(len>>)*add[rt]%mod)%mod;

         add[rt]=;

     }

 }

 void updata(int L,int R, int val,int op,int l,int r,int rt) {

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

         if(op==) {

             same[rt]=val;

             mult[rt]=;  //改变

             add[rt]=;   //改变

             sum1[rt]=(r-l+)*val%mod;

             sum2[rt]=((r-l+)*val%mod)*val%mod;

             sum3[rt]=((r-l+)*val%mod)*(val*val%mod)%mod;

         } else if(op==) {

             mult[rt]=mult[rt]*val%mod;

             add[rt]=add[rt]*val%mod; //改变

             sum1[rt]=sum1[rt]*val%mod;

             sum2[rt]=(sum2[rt]*val%mod)*val%mod;

             sum3[rt]=(sum3[rt]*val%mod)*(val*val%mod)%mod;

         } else if(op==) {

             add[rt]=(add[rt]+val)%mod;

             sum3[rt]=(sum3[rt]+*sum2[rt]*val%mod+*(sum1[rt]*val%mod)*val%mod+(((r-l+)*val%mod)*(val*val%mod)%mod))%mod;

             sum2[rt]=(sum2[rt]+*sum1[rt]*val%mod+((r-l+)*val%mod)*val%mod)%mod;

             sum1[rt]=(sum1[rt]+(r-l+)*val%mod)%mod;

         }

         return;

     }

     pushdown(rt,r-l+);

     int mid=(l+r)>>;

     if(L<=mid) updata(L,R,val,op,l,mid,rt<<);

     if(R>mid) updata(L,R,val,op,mid+,r,rt<<|);

     pushup(rt);

 }

 ll query(int L,int R,int val,int l,int r,int rt) {

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

         if(val==) {

             return sum1[rt]%mod;

         } else if(val==) {

             return sum2[rt]%mod;

         } else return sum3[rt]%mod;

     }

     ll sum=;

     pushdown(rt,r-l+);

     int mid=(l+r)>>;

     if(L<=mid) sum=(sum+query(L,R,val,l,mid,rt<<))%mod;

     if(R>mid) sum=(sum+query(L,R,val,mid+,r,rt<<|))%mod;

     return sum;

 }

 int main() {

     while(~scanf("%d%d",&n,&m)) {

         if(n==&&m==) break;

         build(,n,);

         while(m--) {

             int op,x,y,val;

             scanf("%d%d%d%d",&op,&x,&y,&val);

             if(op==) {

                 printf("%lld\n",query(x,y,val,,n,));

             }

             else updata(x,y,val,op,,n,);

         }

     }

 }

巴特西

HDU4578 Transformation (多操作线段树)

最新文章

热门文章