https://loj.ac/problem/6346

题目还是没法粘贴……

一道蛮不错的题。

老年选手困了30min后才想要推式子实在是太懒了……

我们可以对每次更新列表看成系数*x即可。

举例:第i次有列表(l,r,x),则第j次求和时答案*(j-i)即可。

但是系数不统一很难受,于是得到:(i-k)*x=(i-1)*a,求a=x+(1-k)*x/(i-1),则(i-1)*a=(i-1)*x+(1-k)*x

于是我们用线段树多维护一个(1-k)*x就行了。

注意一下线段树常数问题。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
ll b[N],tr[N*],lz[N*],t[N*],lazy[N*];
inline void push(int a,int l,int r){
int mid=(l+r)>>;
lz[a<<]+=lz[a];lz[a<<|]+=lz[a];
tr[a<<]+=lz[a]*(mid-l+);tr[a<<|]+=lz[a]*(r-mid);
lz[a]=;
lazy[a<<]+=lazy[a];lazy[a<<|]+=lazy[a];
t[a<<]+=lazy[a]*(mid-l+);t[a<<|]+=lazy[a]*(r-mid);
lazy[a]=;
}
void mdy(int a,int l,int r,int l1,int r1,ll w,bool on){
if(r<l1||r1<l)return;
if(l1<=l&&r<=r1){
if(!on)lz[a]+=w,tr[a]+=w*(r-l+);
else lazy[a]+=w,t[a]+=w*(r-l+);
return;
}
push(a,l,r);
int mid=(l+r)>>;
mdy(a<<,l,mid,l1,r1,w,on);mdy(a<<|,mid+,r,l1,r1,w,on);
tr[a]=tr[a<<]+tr[a<<|];
t[a]=t[a<<]+t[a<<|];
}
ll qry(int a,int l,int r,int l1,int r1,ll k){
if(r<l1||r1<l)return ;
if(l1<=l&&r<=r1)return k*tr[a]+t[a];
push(a,l,r);
int mid=(l+r)>>;
return qry(a<<,l,mid,l1,r1,k)+qry(a<<|,mid+,r,l1,r1,k);
}
int main(){
int n=read();
for(int i=;i<=n;i++)b[i]=b[i-]+read();
int m=read();
for(int i=;i<=m;i++){
int d=read();
if(d==){
int l=read(),r=read(),x=read();
mdy(,,n,l,r,x,);mdy(,,n,l,r,(-i)*x,);
}else{
int l=read(),r=read();
printf("%lld\n",b[r]-b[l-]+qry(,,n,l,r,i-));
}
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

最新文章

  1. 【原创】cs+html+js+css模式(六):改造ajax.js,从原来的原生态js修改为依赖于jquery插件
  2. 004_kafka_安装运行
  3. [原]如何在Android用FFmpeg+SDL2.0解码显示图像
  4. 重点关注之Filter的使用(性能计数和错误处理)
  5. telnet命令判断端口是否通不通
  6. 【C++对象模型】函数返回C++对象的问题
  7. 读取AD模拟分量
  8. IOS 多线程,线程同步的三种方式
  9. 搜索(四分树):BZOJ 4513 [SDOI2016 Round1] 储能表
  10. android 用代码画虚线边框背景(转)
  11. 无法读取配置节 system.serviceModel 因为它缺少节声明的解决方法
  12. IBM AIX Shell编写遭遇错误一2
  13. 并行类加载与OSGI类加载
  14. 软件测试基础(软件测试分类和工具组)firebug、firepath的安装
  15. TSP-旅行商问题
  16. 南阳OJ-14-会场安排问题---区间不相交
  17. 6. Scala面向对象编程(基础部分)
  18. Love2D游戏引擎制作贪吃蛇游戏
  19. bigdata-02-hadoop2.8.4-resourceHA安装
  20. grid简单布局

热门文章

  1. 通过 zxing 生成二维码
  2. 阿里云ECS下CentOS7.4 yum安装Python3.6环境
  3. C++0x,std::move和std::forward解析
  4. BFC与合并 浅析
  5. Python函数的内省-Introspection
  6. &quot;Hello world!&quot;团队第一次会议
  7. 王者荣耀交流协会beta冲刺贡献分分配结果
  8. 【转】自定义(滑动条)input[type=&quot;range&quot;]样式
  9. keydown事件下调用trigger事件执行两次
  10. 九度oj 题目1495:关键点