http://www.spoj.com/problems/SEGSQRSS/

SPOJ Problem Set (classical) 11840. Sum of Squares with Segment Tree Problem code: SEGSQRSS

Segment trees are extremely useful.  In particular "Lazy Propagation" (i.e. see
here, for example) allows one to compute sums over a range in O(lg(n)), and update ranges in O(lg(n)) as well.  In this problem you will compute something much harder:

The sum of squares over a range with range updates of 2 types:

1) increment in a range

2) set all numbers the same in a range.

Input

Output

For each test case output the “Case <caseno>:” in
the first line and from the second line output the sum of squares for each operation of type 2.  Intermediate overflow will not occur
with proper use of 64-bit signed integer.

Example

Input:

2

4 5

1 2 3 4

2 1 4

0 3 4 1

2 1 4

1 3 4 1

2 1 4

1 1

1

2 1 1

Output:

Case 1:

30

7

13

Case 2:

1

---

Added by:	Chen Xiaohong
Date:	2012-07-11
Time limit:	6s
Source limit:	50000B
Memory limit:	256MB
Cluster:	Pyramid (Intel Pentium III 733 MHz)
Languages:	All

题意：

有三种操作：将区间中的全部数置为x；将区间中的全部数加上x；求区间内全部数的平方和。

分析：

先考虑假设不须要求平方和，仅仅是求和，我们须要维护这些数据：addv-区间内的数共同加上的值;setv-区间内的数都置为的值(setv=INF表示不设置);sumv-区间内的数加上addv之前的值。

但这题求的是平方和。似乎不是非常好维护。假设仅仅是set操作，还是非常好维护的，那么难点就在于add操作了。考虑例如以下等式：(x+v)^2=x^2+2xv+v^2,x是add操作之前的数,v是add的数。这是一个数的情况。那么一段区间内的数呢？

显然有sum(xi^2)+(v^2)*length+2*sum(xi)*v。这样问题就迎刃而解了，仅仅要再维护一个区间的平方和即可，当set时直接改，add时加上(v^2)*length+2*sum(xi)*v即可。

/*

 *

 * Author : fcbruce

 *

 * Time : Fri 03 Oct 2014 04:16:10 PM CST

 *

 */

#include <cstdio>

#include <iostream>

#include <sstream>

#include <cstdlib>

#include <algorithm>

#include <ctime>

#include <cctype>

#include <cmath>

#include <string>

#include <cstring>

#include <stack>

#include <queue>

#include <list>

#include <vector>

#include <map>

#include <set>

#define sqr(x) ((x)*(x))

#define LL long long

#define itn int

#define INF 0x3f3f3f3f

#define PI 3.1415926535897932384626

#define eps 1e-10

#ifdef _WIN32

  #define lld "%I64d"

#else

  #define lld "%lld"

#endif

#define maxm

#define maxn 100007

using namespace std;

int addv[maxn<<2],setv[maxn<<2];

long long sumv[maxn<<2],sqrsumv[maxn<<2];

inline void pushdown(int k,int l,int r)

{

  int lc=k*2+1,rc=k*2+2,m=l+r>>1;

  addv[lc]+=addv[k];

  addv[rc]+=addv[k];

  addv[k]=0;

  if (setv[k]!=INF)

  {

    setv[lc]=setv[rc]=setv[k];

    sumv[lc]=(LL)setv[lc]*(m-l);sumv[rc]=(LL)setv[rc]*(r-m);

    sqrsumv[lc]=sqr((LL)setv[k]*(m-l));sqrsumv[rc]=sqr((LL)setv[rc])*(r-m);

    addv[lc]=addv[rc]=0;

    setv[k]=INF;

  }

}

inline void pushup(int k,int l,int r)

{

  int lc=k*2+1,rc=k*2+2,m=l+r>>1;

  sumv[k]=sumv[lc]+sumv[rc]+(LL)addv[lc]*(m-l)+(LL)addv[rc]*(r-m);

  sqrsumv[k]=sqrsumv[lc]+sqrsumv[rc]+(LL)(r-l)*(addv[k])+2ll*sumv[k]*addv[k];

}

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

{

  addv[k]=0;

  setv[k]=INF;

  sumv[k]=sqrsumv[k]=0ll;

  if (r-l==1)

  {

    scanf("%d",&sumv[k]);

    sqrsumv[k]=sqr((LL)sumv[k]);

    return ;

  }

  build(k*2+1,l,l+r>>1);

  build(k*2+2,l+r>>1,r);

  pushup(k,l,r);

}

void update_add(int a,int b,int v,int k,int l,int r)

{

  if (b<=l || r<=a) return ;

  if (a<=l && r<=b)

  {

    addv[k]+=v;

    sqrsumv[k]+=sqr((LL)v)*(r-l)+2ll*v*sumv[k];

    return ;

  }

  pushdown(k,l,r);

  update_add(a,b,v,k*2+1,l,l+r>>1);

  update_add(a,b,v,k*2+2,l+r>>1,r);

  pushup(k,l,r);

}

void update_set(int a,int b,int v,int k,int l,int r)

{

  if (b<=l || r<=a) return ;

  if (a<=l && r<=b)

  {

    addv[k]=0;

    setv[k]=v;

    sumv[k]=(LL)v*(r-l);

    sqrsumv[k]=sqr((LL)v)*(r-l);

    return ;

  }

  pushdown(k,l,r);

  update_set(a,b,v,k*2+1,l,l+r>>1);

  update_set(a,b,v,k*2+2,l+r>>1,r);

  pushup(k,l,r);

}

long long query(int a,int b,int k,int l,int r)

{

  if (b<=l || r<=a) return 0ll;

  if (a<=l && r<=b) return sqrsumv[k];

  pushdown(k,l,r);

  return query(a,b,k*2+1,l,l+r>>1)+query(a,b,k*2+2,l+r>>1,r);

}

int main()

{

#ifdef FCBRUCE

  freopen("/home/fcbruce/code/t","r",stdin);

#endif // FCBRUCE

  int T_T,__=0;

  scanf("%d",&T_T);

  while (T_T--)

  {

    int n,m;

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

    build(0,0,n);

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

    int op,a,b,v;

    while (m--)

    {

      scanf("%d",&op);

      switch (op)

      {

        case 0:

          scanf("%d%d%d",&a,&b,&v);

          a--;

          update_set(a,b,v,0,0,n);

          break;

        case 1:

          scanf("%d%d%d",&a,&b,&v);

          a--;

          update_add(a,b,v,0,0,n);

          break;

        case 2:

          scanf("%d %d",&a,&b);

          a--;

          printf(lld "\n",query(a,b,0,0,n));

          break;

      }

    }

  }

  return 0;

}