HDU4578 Transformation【线段树】

<题目链接>

<转载于 >>> >

题目大意：

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

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

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

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

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

解题分析：

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 typedef long long ll;
 7 const int mod=10007;
 8 const int M =1e5+5;
 9 
10 #define Lson rt<<1,l,mid
11 #define Rson rt<<1|1,mid+1,r
12 int n,m;
13 bool cnt[M<<2];
14 ll tr[M<<2];
15 void Pushdown(int rt){
16     if(cnt[rt]){
17         cnt[rt<<1]=cnt[rt<<1|1]=true;  
18         tr[rt<<1]=tr[rt<<1|1]=tr[rt];  
19     }
20 }
21 void Pushup(int rt){
22     if(!cnt[rt<<1]||!cnt[rt<<1|1])cnt[rt]=false; 
23     else if(tr[rt<<1]!=tr[rt<<1|1])cnt[rt]=false;
24     else cnt[rt]=true,tr[rt]=tr[rt<<1];
25 }
26 void update(int rt,int l,int r,int L,int R,int c,int type){
27     if(cnt[rt]&&L<=l&&r<=R){   
28         if(type==1)tr[rt]=(tr[rt]+c)%mod;     //分三种情况进行操作
29         else if(type==2)tr[rt]=(tr[rt]*c)%mod;
30         else tr[rt]=c;
31         return;
32     }
33     Pushdown(rt);
34     int mid=(l+r)>>1;
35     if(L<=mid)update(Lson,L,R,c,type);
36     if(R>mid)update(Rson,L,R,c,type);
37     Pushup(rt);
38 }
39 int query(int rt,int l,int r,int L,int R,int c){
40     if(cnt[rt]&&L<=l&&r<=R){
41         ll res=1;for(int i=1;i<=c;i++)res*=tr[rt];  //得到tr[rt]的c次方(因为c<=3，所以可以不用快速幂)
42         res=res*(r-l+1);   //乘上区间长度
43         return res%mod;
44     }
45     Pushdown(rt);
46     int mid=(l+r)>>1;
47     ll ans=0;
48     if(L<=mid)ans+=query(Lson,L,R,c);
49     if(R>mid)ans+=query(Rson,L,R,c);
50     return ans%mod;
51 }
52 int main(){
53     while(scanf("%d%d",&n,&m)!=EOF,n||m){
54         memset(tr,0,sizeof(tr));
55         memset(cnt,true,sizeof(cnt));
56         while(m--){
57             int op,x,y,c;
58             scanf("%d%d%d%d",&op,&x,&y,&c);
59             if(op>=1&&op<=3)update(1,1,n,x,y,c,op);
60             else printf("%d
",query(1,1,n,x,y,c));
61         }
62     }
63     return 0;
64 }

2018-09-25

HDU4578 Transformation【线段树】

相关推荐