线段树练习 3

思路:

  分块;

来,上代码:

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 200005
#define ll long long ll n,m,flag[maxn],size,bel[maxn],dis[maxn];
ll sum[maxn],li[maxn],ri[maxn],blo,si[maxn]; inline void in(ll &now)
{
ll if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
} int main()
{
in(n),size=sqrt(n);ll pos=,x;
for(ll i=;i<=n;i++)
{
in(dis[i]);
if(pos==) li[++blo]=i;
pos++,sum[blo]+=dis[i],bel[i]=blo;
if(pos==size) pos=,ri[blo]=i;
}
ri[blo]=n;
for(ll i=;i<=blo;i++) si[i]=ri[i]-li[i]+;
ll ty,l,r;in(m);
while(m--)
{
in(ty),in(l),in(r);
if(ty==)
{
in(x);
for(ll i=bel[l];i<=bel[r];i++)
{
if(l<=li[i]&&r>=ri[i]) flag[i]+=x,sum[i]+=si[i]*x;
else
{
for(ll j=max(l,li[i]);j<=min(r,ri[i]);j++) dis[j]+=x,sum[i]+=x;
}
}
}
else
{
ll ans=;
for(ll i=bel[l];i<=bel[r];i++)
{
if(l<=li[i]&&r>=ri[i]) ans+=sum[i];
else for(ll j=max(li[i],l);j<=min(ri[i],r);j++) ans+=dis[j]+flag[i];
}
printf("%lld\n",ans);
}
}
return ;
}

最新文章

  1. 前端神器avalonJS入门(三)
  2. 【重要更新】Senparc.Weixin SDK v4.3.3升级说明
  3. iOS开发之百度地图导航
  4. QML学习笔记之一
  5. ViewPager的简单例子
  6. android studio如何查看数据库文件
  7. 【原】Spring和Dubbo整合案例和过程
  8. js广告轮询效果
  9. javascript事件委托机制详解
  10. canvas图表(1) - 柱状图
  11. 关于Mac终端故障一直出现 [进程已完毕]
  12. Mac 管理员变为了普通用户怎么办?
  13. IOS中的数据存储方式,特点,使用情况
  14. localStorage sessionStorage 用法
  15. KnockoutJs学习笔记(五)
  16. Cocos Creator_发布到微信小游戏平台
  17. JAVA内存管理 [转]
  18. 转:IOS 基于APNS消息推送原理与实现(JAVA后台)
  19. 【已解决】mysql连接出错:ERROR 1040 (HY000): Too many connections
  20. SSH:Struts + Spring + Hibernate 轻量级Java EE企业框架

热门文章

  1. POJ 3320 尺取法(基础题)
  2. Gym - 101981D Country Meow(模拟退火)
  3. [BZOJ1010]玩具装箱toy(斜率优化)
  4. [BZOJ1208]宠物收养所(Splay)
  5. java中如何判断一个字符串是否包含另外一个字符串的方法
  6. Android BadgeView 工具包
  7. 【Clone Graph】cpp
  8. leetcode 【 Swap Nodes in Pairs 】python 实现
  9. python 学习分享-常用模块篇
  10. [python工具][pycharm]pycharm licence activation失效的解决方法