BZOJ_1798__Codevs_2216_[AHOI_2009]_行星序列_(線段樹)

描述

BZOJ: http://www.lydsy.com/JudgeOnline/problem.php?id=1798

Codevs: http://codevs.cn/problem/2216/

給出n和行星的質量,進行m次操作:

1.將[l,r]區間內所有行星質量*c.

2.將[l,r]區間內所有行星質量+c.

3.詢問[l,r]區間內行星質量和.

分析

雙標記線段樹,多加一個乘法的標記.a[k]位置的標記表示的是要傳給a[k]的子節點的值,乘法位置為a[k].f,加法為a[k].p,表示的是先乘后加.按照先乘后加的規定,當跟新值時,ax+b變為(ax+b)*c1+c2=axc1+bc1+c2=(axc1)+(bc1+c2),也就是標記向下傳遞(push_down)的時候,乘法位置要乘,加法位置要先乘后加.

之前一直wa,最后才發現數組沒開夠...

感覺好像把乘法轉化為加法也能做...但沒嘗試.

注意:

1.最好在確保扔給函數的參數都是取過模的,這樣不容易出錯.

2.可以不用long long定義,在乘法的時候強制轉換一下就好了.

  1 #include<cstdio>
  2 #include<algorithm>
  3 #define ll long long
  4 #define lson 2*k
  5 #define rson 2*k+1
  6 
  7 const int maxn=1e5+5;
  8 int n,m,mod;
  9 int w[maxn];
 10 struct node { int l,r,x,f,p; }a[3*maxn];
 11 
 12 void build_tree(int l,int r,int k)
 13 {
 14     a[k].l=l; a[k].r=r; a[k].f=1; a[k].p=0;
 15     if(l==r)
 16     {
 17         a[k].x=w[l]; 
 18         return; 
 19     }    
 20     int mid=l+(r-l)/2;
 21     build_tree(l,mid,lson);
 22     build_tree(mid+1,r,rson);
 23     a[k].x=(a[lson].x+a[rson].x)%mod;
 24 }
 25 
 26 inline void cal(int k,int f,int p)
 27 {
 28     a[k].x=(int)((((ll)a[k].x*(ll)f)%mod+((ll)(a[k].r-a[k].l+1)%mod)*(ll)p)%mod);
 29     a[k].f=(int)(((ll)a[k].f*(ll)f)%mod);
 30     a[k].p=(int)((((ll)a[k].p*(ll)f)%mod+p)%mod);
 31 }
 32 
 33 inline void push_down(int k)
 34 {
 35     cal(lson,a[k].f,a[k].p);
 36     cal(rson,a[k].f,a[k].p);
 37     a[k].f=1;
 38     a[k].p=0;
 39 }
 40 
 41 void update(int l,int r,int k,int f,int p)
 42 {
 43     if(a[k].l==l&&a[k].r==r)
 44     {
 45         cal(k,f,p);
 46         return;
 47     }
 48     if(a[k].f!=1||a[k].p)
 49     {
 50         push_down(k);
 51     }
 52     int mid=a[k].l+(a[k].r-a[k].l)/2;
 53     if(r<=mid)
 54     {
 55         update(l,r,lson,f,p);
 56     }
 57     else if(l>mid)
 58     {
 59         update(l,r,rson,f,p);
 60     }
 61     else
 62     {
 63         update(l,mid,lson,f,p);
 64         update(mid+1,r,rson,f,p);
 65     }
 66     a[k].x=(a[lson].x+a[rson].x)%mod;
 67 }
 68 
 69 int search(int l,int r,int k)
 70 {
 71     if(a[k].l==l&&a[k].r==r)
 72     {
 73         return a[k].x;
 74     }
 75     if(a[k].f!=1||a[k].p)
 76     {
 77         push_down(k);
 78     }
 79     int mid=a[k].l+(a[k].r-a[k].l)/2;
 80     if(r<=mid)
 81     {
 82         return (search(l,r,lson)%mod);
 83     }
 84     else if(l>mid)
 85     {
 86         return (search(l,r,rson)%mod);
 87     }
 88     else
 89     {
 90         return ((search(l,mid,lson)+search(mid+1,r,rson))%mod);
 91     }
 92 }
 93 
 94 int main()
 95 {
 96 #ifndef ONLINE_JUDGE
 97     freopen("star.in","r",stdin);
 98     freopen("star.out","w",stdout);
 99 #endif
100     scanf("%d%d",&n,&mod);
101     
102     for(int i=1;i<=n;i++)
103     {
104         scanf("%d",&w[i]);
105     }
106     build_tree(1,n,1);
107     scanf("%d",&m);
108     int qry,l,r,c;
109     for(int i=1;i<=m;i++)
110     {
111         scanf("%d%d%d",&qry,&l,&r);
112         switch(qry)
113         {
114             case 1:
115                 scanf("%d",&c);
116                 c%=mod;
117                 update(l,r,1,c,0);
118                 break;
119             case 2:
120                 scanf("%d",&c);
121                 c%=mod;
122                 update(l,r,1,1,c);
123                 break;
124             case 3:
125                 printf("%d\n",search(l,r,1));
126                 break;
127         }
128     }
129 #ifndef ONLINE_JUDGE
130     fclose(stdin);
131     fclose(stdout);
132     system("star.out");
133 #endif
134     return 0;
135 }

View Code

轉載于:https://www.cnblogs.com/Sunnie69/p/5436371.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/271873.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/271873.shtml
英文地址，請注明出處：http://en.pswp.cn/news/271873.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！