HDU4578 Transformation【线段树】

<题目链接>

<转载于 >>> >

题目大意：

有一个序列，有四种操作：

1：区间[l，r]内的数全部加c。

2：区间[l，r]内的数全部乘c。

3：区间[l，r]内的数全部初始为c。

4：询问区间[l，r]内所有数的P次方之和。

解题分析：

不可能全部查询的节点，最好的情况就是查询到一段[l，r]，这段区间内所有的值都相等，那么返回（r-l+1）*val 的值即可。只要标记区间内的所有数是否相同，并记录下区间内所有数相同的区间的值即可。每次询问时查询到区间内所有值相同的区间即可。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const int mod=;

 const int M =1e5+;

 #define Lson rt<<1,l,mid

 #define Rson rt<<1|1,mid+1,r

 int n,m;

 bool cnt[M<<];

 ll tr[M<<];

 void Pushdown(int rt){

     if(cnt[rt]){

         cnt[rt<<]=cnt[rt<<|]=true;

         tr[rt<<]=tr[rt<<|]=tr[rt];

     }

 }

 void Pushup(int rt){

     if(!cnt[rt<<]||!cnt[rt<<|])cnt[rt]=false;

     else if(tr[rt<<]!=tr[rt<<|])cnt[rt]=false;

     else cnt[rt]=true,tr[rt]=tr[rt<<];

 }

 void update(int rt,int l,int r,int L,int R,int c,int type){

     if(cnt[rt]&&L<=l&&r<=R){

         if(type==)tr[rt]=(tr[rt]+c)%mod;     //分三种情况进行操作

         else if(type==)tr[rt]=(tr[rt]*c)%mod;

         else tr[rt]=c;

         return;

     }

     Pushdown(rt);

     int mid=(l+r)>>;

     if(L<=mid)update(Lson,L,R,c,type);

     if(R>mid)update(Rson,L,R,c,type);

     Pushup(rt);

 }

 int query(int rt,int l,int r,int L,int R,int c){

     if(cnt[rt]&&L<=l&&r<=R){

         ll res=;for(int i=;i<=c;i++)res*=tr[rt];  //得到tr[rt]的c次方(因为c<=3，所以可以不用快速幂)

         res=res*(r-l+);   //乘上区间长度

         return res%mod;

     }

     Pushdown(rt);

     int mid=(l+r)>>;

     ll ans=;

     if(L<=mid)ans+=query(Lson,L,R,c);

     if(R>mid)ans+=query(Rson,L,R,c);

     return ans%mod;

 }

 int main(){

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

         memset(tr,,sizeof(tr));

         memset(cnt,true,sizeof(cnt));

         while(m--){

             int op,x,y,c;

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

             if(op>=&&op<=)update(,,n,x,y,c,op);

             else printf("%d\n",query(,,n,x,y,c));

         }

     }

     return ;

 }

2018-09-25

巴特西

HDU4578 Transformation【线段树】

最新文章

热门文章