首页 > 代码库 > SPOJ 11840. Sum of Squares with Segment Tree (线段树,区间更新)
SPOJ 11840. Sum of Squares with Segment Tree (线段树,区间更新)
http://www.spoj.com/problems/SEGSQRSS/
SPOJ Problem Set (classical)11840. Sum of Squares with Segment TreeProblem 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 <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; }
SPOJ 11840. Sum of Squares with Segment Tree (线段树,区间更新)