UESTC_秋實大哥與花 2015 UESTC Training for Data StructuresProblem B

B - 秋實大哥與花

Time Limit: 3000/1000MS (Java/Others) ??? Memory Limit: 65535/65535KB (Java/Others)

Submit?Status

秋實大哥是一個儒雅之人，晝聽笙歌夜醉眠，若非月下即花前。

所以秋實大哥精心照料了很多花朵。現在所有的花朵排成了一行，每朵花有一個愉悅值。

秋實大哥每天要對著某一段連續的花朵歌唱，然后這些花朵的愉悅值都會增加一個相同的值v(v可能為負)。

同時他想知道每次他唱完歌后這一段連續的花朵的愉悅值總和是多少。

Input

第一行有一個整數n，表示花朵的總數目。

第二行包含n個整數ai，表示第i朵花初始的愉悅值。

第三行包含一個整數m，表示秋實大哥唱了m天的歌。

接下來m行，每行包含三個整數l?r?v，表示秋實大哥對著[l,r]這個區間內的花朵歌唱，每朵花的愉悅值增加了v。

1≤n，m，ai，|v|≤100000，1≤l≤r≤n。

Output

輸出共m行，第i行表示秋實大哥完成第i天的歌唱后，那一段花朵的愉悅值總和。

Sample input and output

Sample Input	Sample Output
3 0 0 0 3 1 2 1 1 2 -1 1 3 1	2 0 3

解題報告:

沒啥好說的，線段樹模板基礎題。。唯一需要注意的就是long long了.

當然我是使用的樹狀數組:

題目中操作屬于區間更新?-?區間查詢<查詢點也是區間嘛>類型，可使用樹狀數組來實現.

令C[i]為從1至i號花的共同更新之和.

首先考慮更新,add[l,r,v]?→?c[r]?+=?v?,?c[l-1]?-=v;

?Sum[x]?=?從?1?至?x?號花的value之和.

??Sum[x]?=?c[1]*1?+?c[2]*2?+?c[3]?*?3?.....?+?c[x]?*?x?+?(c[x+1]?+?....?C[n]?)?*x;

??????????= (segema)f(x)?+ (segema)g(x)?*?x;

??????????=?兩個樹狀數組，一個維護?c[i]*i?,一個維護c[i]

之后考慮區間查詢:

?Query(l?,?r)

?=?sum[r]?-?sum[l-1]

?

#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 50;
ll n;
ll f[maxn],g[maxn];


inline ll lowbit(ll idx)
{
    return idx & (-idx);
}

void updataf(ll idx,ll res)
{
    if (!idx)
     return;
    while(idx <= n)
     {
         f[idx] += res;
         idx += lowbit(idx);
     }
}

void updatag(ll idx,ll res)
{
    if (!idx)
     return;
    while(idx <= n)
     {
         g[idx] += res;
         idx += lowbit(idx);
     }
}

ll sumf(ll idx)
{
    ll res = 0;
    while(idx > 0)
     {
         res += f[idx];
         idx -= lowbit(idx);
     }
    return res;
}

ll sumg(ll idx)
{
    ll res = 0;
    while(idx > 0)
     {
         res += g[idx];
         idx -= lowbit(idx);
     }
    return res;
}

int main(int argc,char *argv[])
{
  ll m;
  scanf("%lld%lld",&n,&m);
  memset(f,0,sizeof(f));
  memset(g,0,sizeof(g));
  for(int j = 1 ; j <= n ; ++ j)
   {
         ll v;
         scanf("%lld",&v);
         updataf(j,v*j);
         updataf(j-1,-v*(j-1));
         updatag(j,v);
         updatag(j-1,-v);
   }
  while(m--)
   {
         ll i,j,v;
         scanf("%lld%lld%lld",&i,&j,&v);
         updataf(j,v*j);
         updataf(i-1,-v*(i-1));
         updatag(j,v);
         updatag(i-1,-v);
         i--;
         ll res1 = sumf(i) + i*(sumg(n)-sumg(i));
      ll res2 = sumf(j) + j*(sumg(n)-sumg(j));
         printf("%lld\n",res2 - res1);
   }
  return 0;
}

?

?