zoj 2706 Thermal Death of the Universe (線段樹區間更新，區間求和)

zoj 2706 Thermal Death of the Universe (線段樹區間更新，區間求和)

/*
 題意：給n個數，m個操作，每次把區間[l,r]的數用它們的平均值替代，
   如果平均值不是整數，且當前n個數的和小於原先的和就向上round，不然就向下round;
*/
#include 
# include 
using namespace std;
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
///lson和rson分別表示結點的左兒子和右兒子
///rt表示當前子樹的根(root),也就是當前所在的結點
const int maxn =30010;
///maxn是題目給的最大區間,而節點數要開4倍,確切的來說節點數要開大於maxn的最小2x的兩倍
long long  sum[maxn<<2];///求和
long long col[maxn<<2];///用來標記每個節點，為0則表示沒有標記，否則為標記
long long str[maxn];
void PushUP(long long rt)///PushUP(int rt)是把當前結點的信息更新到父結點
{
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(long long  rt,long long m)///pushDown(int rt)是把當前結點的信息更新給兒子結點，m為分區間的長度
{
    ///對某一個區間進行改變，如果被標記了，在查詢的時候就得把改變傳給子節點，因為查詢的並不一定是當前區間
    if (col[rt])///被標記過，說明區間改變了
    {
        col[rt<<1] = col[rt<<1|1] = col[rt];
         /*此處用add[rt]乘以區間長度，不是add[rt<<1], 因為rt的兒子節點如果被多次標記，之前被標記時，
          就已經對sum[rt<<1]更新過了。
        */
        sum[rt<<1] = (m - (m >> 1)) * col[rt];///更新左兒子的和
        sum[rt<<1|1] = (m >> 1) * col[rt];///更新右兒子的和
        col[rt] = 0;///將標記向兒子節點移動後，父節點的延遲標記去掉
        ///傳遞後，當前節點標記域清空
    }
}
void build(long long l,long long r,long long  rt)///建樹
{
    col[rt] = 0;
    if (l == r)
    {
        scanf("%lld",&sum[rt]);
        return ;
    }
    long long  m = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(long long L,long long  R,long long c,long long l,long long r,long long rt)///區間更新
{
    if (L <= l && r <= R)
    {
        col[rt] = c;
        sum[rt] = c * (r - l + 1);
        return ;
    }
    /*當要對被延遲標記過的這段區間的兒子節點進行更新時，先要將延遲標記向兒子節點移動
    當然，如果一直沒有對該段的兒子節點更新，延遲標記就不需要向兒子節點移動，這樣就使
    更新操作的時間復雜度仍為O（logn），也是使用延遲標記的原因。
    */
    PushDown(rt , r - l + 1);///延遲標志域向下傳遞
    long long m = (l + r) >> 1;
    if (L <= m) update(L , R , c , lson);
    if (R > m) update(L , R , c , rson);
    PushUP(rt);///向上傳遞更新和
}
long long query(long long L,long long R,long long l,long long r,long long rt)///區間求和
{
    if (L <= l && r <= R)
    {
        return sum[rt];
    }
    PushDown(rt , r - l + 1);///要取rt子節點的值時，也要先把rt的延遲標記向下移動
    long long  m = (l + r) >> 1;
    long long ret = 0;
    if (L <= m) ret += query(L , R , lson);
    if (m < R) ret += query(L , R , rson);
    return ret;
}

int main()
{
    long long  t,n,i;
    long long a,b;
    long double ave;
    long long sum,sum1;
    while(~scanf("%lld%lld",&n,&t))
    {
        build(1 , n , 1);
        sum=query(1,n,1,n,1);
        while(t--)
        {

            scanf("%lld%lld",&a,&b);
            sum1=query(a,b,1,n,1);
            ave=sum1*1.0/(b-a+1.0);
            if(ave==(long long)ave)
                ave=(long long)ave;
            else///注意負數的進捨
            {
                sum1=query(1,n,1,n,1);
                if(sum1<=sum)
                {
                    if(ave>0)
                        ave=(long long)ave+1;
                    else
                        ave=(long long)ave;
                }
                else
                {
                    if(ave>0)
                        ave=(long long )ave;
                    else
                        ave=(long long)ave-1;
                }
            }
            update(a,b,(long long)ave,1,n,1);
        }
        for(i=1; i<=n; i++)
        {
            if(i==n)
                printf("%lld\n",query(i,i,1,n,1));
            else

                printf("%lld ",query(i,i,1,n,1));
        }
        printf("\n");
    }
    return 0;
}