UVA 12501 Bulky process of bulk reduction —

　　和普通的线段树不同的是，查询x~y的话，给出的答案是第一个值的一倍加上第二个值的两倍一直到第n个值的n倍。

　　思路的话，就是关于query和pushup的方法。用一个新的变量sum记录一下这个区间里面按照答案给出的方式的值，比如说，这个节点的区间是1~3，那么这个节点的sum值就是(1*val[1]+2*val[2]+3*val[3])。那么对于pushup操作，当前这个节点的sum值是左边的sum值+左边的区间长度*右边的c值（c值代表的是这个区间的所有元素的和）+右边的sum值。这样的话就相当于右边的sum升高了需要的高度，就满足题意了。

　　另外关于query也是类似，要返回时，加上(l-ql)倍的c[o]的值就行了，这样就相当于右边的sum升高了(l-ql)的高度了。如果不能理解，可以手动模拟一下试试。

　　但是这题WA了好多次，，因为我现在才知道原来uva的long long得用lld，QAQ。。。

　　具体见代码：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #define t_mid (l+r>>1)

 #define ls o<<1

 #define rs o<<1 | 1

 #define lson ls,l,t_mid

 #define rson rs,t_mid+1,r

 using namespace std;

 typedef long long ll;

 const int N =  + ;

 ll c[N<<],sum[N<<],add[N<<];

 void pushup(int o,int len){c[o]=c[ls]+c[rs];sum[o]=sum[ls]+c[rs]*len+sum[rs];}

 void build(int o,int l,int r)

 {

     add[o]=;

     if(l==r) {c[o]=sum[o]=;return;}

     build(lson);

     build(rson);

     pushup(o,t_mid-l+);

 }

 void pushdown(int o,int len)

 {

     if(add[o])

     {

         int llen=(len-(len>>)),rlen=(len>>);

         add[ls] += add[o];

         add[rs] += add[o];

         c[ls] += add[o]*llen;

         c[rs] += add[o]*rlen;

         sum[ls] += add[o]*(llen)*(llen+)/;

         sum[rs] += add[o]*(rlen)*(rlen+)/;

         add[o]=;

     }

 }

 void update(int o,int l,int r,int ql,int qr,int dt)

 {

     if(ql <= l && qr >= r)

     {

         add[o] += (ll)dt;

         c[o] += (ll)dt*(r-l+);

         sum[o] += (ll)dt*(r-l+)*(r-l+)/;

         return;

     }

     pushdown(o,r-l+);

     if(ql <= t_mid) update(lson,ql,qr,dt);

     if(qr >t_mid) update(rson,ql,qr,dt);

     pushup(o,t_mid-l+);

 }

 ll query(int o,int l,int r,int ql,int qr)

 {

     if(ql <= l && qr >= r)

     {

         return (l-ql)*c[o]+sum[o];

     }

     pushdown(o,r-l+);

     ll res = ;

     if(ql <= t_mid) res += query(lson,ql,qr);

     if(qr > t_mid) res += query(rson,ql,qr);

     return res;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for(int kase=;kase<=T;kase++)

     {

         printf("Case %d:\n",kase);

         int n,m;

         scanf("%d%d",&n,&m);

         build(,,n);

         while(m--)

         {

             char s[];

             scanf("%s",s);

             if(s[]=='c')

             {

                 int x,y,dt;

                 scanf("%d%d%d",&x,&y,&dt);

                 update(,,n,x,y,dt);

             }

             else

             {

                 int x,y;

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

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

             }

         }

     }

 }

巴特西

UVA 12501 Bulky process of bulk reduction ——（线段树成段更新）

最新文章

热门文章