LOJ6346:线段树:关于时间 ——题解
2024-10-19 02:35:45
题目还是没法粘贴……
一道蛮不错的题。
老年选手困了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/ +
+++++++++++++++++++++++++++++++++++++++++++
最新文章
- 【原创】cs+html+js+css模式(六):改造ajax.js,从原来的原生态js修改为依赖于jquery插件
- 004_kafka_安装运行
- [原]如何在Android用FFmpeg+SDL2.0解码显示图像
- 重点关注之Filter的使用(性能计数和错误处理)
- telnet命令判断端口是否通不通
- 【C++对象模型】函数返回C++对象的问题
- 读取AD模拟分量
- IOS 多线程,线程同步的三种方式
- 搜索(四分树):BZOJ 4513 [SDOI2016 Round1] 储能表
- android 用代码画虚线边框背景(转)
- 无法读取配置节 system.serviceModel 因为它缺少节声明的解决方法
- IBM AIX Shell编写遭遇错误一2
- 并行类加载与OSGI类加载
- 软件测试基础(软件测试分类和工具组)firebug、firepath的安装
- TSP-旅行商问题
- 南阳OJ-14-会场安排问题---区间不相交
- 6. Scala面向对象编程(基础部分)
- Love2D游戏引擎制作贪吃蛇游戏
- bigdata-02-hadoop2.8.4-resourceHA安装
- grid简单布局
热门文章
- 通过 zxing 生成二维码
- 阿里云ECS下CentOS7.4 yum安装Python3.6环境
- C++0x,std::move和std::forward解析
- BFC与合并 浅析
- Python函数的内省-Introspection
- ";Hello world!";团队第一次会议
- 王者荣耀交流协会beta冲刺贡献分分配结果
- 【转】自定义(滑动条)input[type=";range";]样式
- keydown事件下调用trigger事件执行两次
- 九度oj 题目1495:关键点