SPOJ 11840. Sum of Squares with Segment Tree (线段树,区间更新)

简介:

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

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:

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).

st nd x -- add "x" to all numbers with indices in [st, nd(1 <= st <= nd <= Nand -1,000 <= x <= 1,000).

st nd x -- set all numbers with indices in [st, nd] to "x(1 <= st <= nd <= Nand -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;
}


本文转自mfrbuaa博客园博客,原文链接:http://www.cnblogs.com/mfrbuaa/p/5163223.html,如需转载请自行联系原作者

相关文章
|
存储 编解码 数据可视化
云VR:虚拟现实专业化的下一步
但究竟什么是云VR,云VR将如何帮助各行各业开展业务?本文将带您了解VR和云VR的未来,以及它与我们目前可以体验的沉浸式VR有何不同。
|
5月前
|
存储 消息中间件 前端开发
PHP后端与uni-app前端协同的校园圈子系统:校园社交场景的跨端开发实践
校园圈子系统校园论坛小程序采用uni-app前端框架,支持多端运行,结合PHP后端(如ThinkPHP/Laravel),实现用户认证、社交关系管理、动态发布与实时聊天功能。前端通过组件化开发和uni.request与后端交互,后端提供RESTful API处理业务逻辑并存储数据于MySQL。同时引入Redis缓存热点数据,RabbitMQ处理异步任务,优化系统性能。核心功能包括JWT身份验证、好友系统、WebSocket实时聊天及活动管理,确保高效稳定的用户体验。
295 4
PHP后端与uni-app前端协同的校园圈子系统:校园社交场景的跨端开发实践
|
JSON 安全 API
淘宝 API 接口:解锁商品详情的强大工具
淘宝API接口在电商领域扮演着关键角色,为商家和开发者提供强大的数据支持和服务能力。它不仅帮助商家获取商品信息、管理订单和物流,还支持数据分析、价格调整等功能,助力商家在竞争激烈的市场中取得成功。此外,通过注册认证、搭建开发环境等步骤,开发者可快速上手并利用丰富的技术文档和社区支持进行高效开发。
|
12月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
235 0
|
前端开发 JavaScript UED
CSS进阶-3D变换与透视效果
【6月更文挑战第15天】CSS3的3D变换和透视效果增强了网页的深度感。通过`rotateX/Y/Z`旋转和`translateZ`移动,结合`perspective`属性可创建3D空间。`perspective`定义观察者与Z轴的距离,影响元素的缩放感。常见问题包括过度失真和元素遮挡顺序,可通过调整`perspective`值和使用`z-index`解决。进阶技巧涉及层叠上下文理解和3D卡片翻转效果,通过实践与探索,设计师能更好地利用这些工具创新用户体验。
289 6
|
安全 网络协议 网络安全
2024黑龙江省职业院校技能信息安全管理与评估样题第一阶段
2024黑龙江省职业院校技能信息安全管理与评估样题第一阶段
|
Linux 数据安全/隐私保护
Linux添加新账户
Linux添加新账户
129 0
|
存储 安全 C语言
C语言中的字符串常量及其处理技术
C语言中的字符串常量及其处理技术
746 0
|
存储 SQL 缓存
阿里华为等大厂的本地缓存、分布式缓存解决方案详解(中)
阿里华为等大厂的本地缓存、分布式缓存解决方案详解
490 0