?
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
There will be T (T <= 25) test cases in the input file. First line of the input contains two positive integers, N (N <= 100,000) and Q (Q <= 100,000). The next line contains N integers, each at most 1000. Each of the next Qlines starts with a number, which indicates the type of operation:
2 st nd -- return the sum of the squares of the numbers with indices in [st, nd] {i.e., from st to nd inclusive} (1 <= st <= nd <= N).
1 st nd x -- add x to all numbers with indices in [st, nd] (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).
0 st nd x -- set all numbers with indices in [st, nd] to x (1 <= st <= nd <= N, and -1,000 <= x <= 1,000).
?
Output
For each test case output the “Case
:” 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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include