首页 > 其他分享 >【模板】 与等差数列结合的线段树

【模板】 与等差数列结合的线段树

时间:2024-02-02 11:26:04浏览次数:27  
标签:last cl int 线段 mid 等差数列 cr 模板 define

题面

image

代码

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define fi first
#define se second
#define push_back pb
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define int long long
#define N 300100
#define ls i<<1
#define rs i<<1|1
#define mid (l+r)/2
struct Seg_Tree{
	ll sum[N<<3],lz1[N<<3],a[N<<3],lz2[N<<3],sum1[N<<3];
	// 这里 N*8 要特别注意,因为后续会先 pushdown() 所以多乘了个 2.
	void pu(int i){
		sum[i]=sum[ls]+sum[rs];
		sum1[i]=sum1[ls]+sum1[rs];
	}
	void build(int i,int l,int r){
		if(l==r){
			sum[i]=lz1[i]=lz2[i]=a[i]=sum1[i]=0;
			return;
		}
		build(ls,l,mid),build(rs,mid+1,r);
		pu(i);
	}
	void pd(int i,int l,int r){
		if(lz1[i]){
			sum[ls]=1ll*(mid-l+1)*lz1[i];
			sum[rs]=1ll*(r-mid)*lz1[i];
			lz1[ls]=lz1[i],lz1[rs]=lz1[i];
		}
		if(lz2[i]){
			sum1[ls]=lz2[i]*(mid-l+1)*(l+mid)/2;
			sum1[rs]=lz2[i]*(r-mid)*(mid+1+r)/2;
			lz2[ls]=lz2[rs]=lz2[i];
		}
		lz1[i]=0,lz2[i]=0;
	}
	void mod1(int i,int l,int r,int cl,int cr,ll k){
		pd(i,l,r);
		if(l>=cl&&r<=cr){
			sum[i]=(r-l+1)*k;
			lz1[i]=k;
			return;
		}
		if(r<cl||l>cr) return;
		mod1(ls,l,mid,cl,cr,k);
		mod1(rs,mid+1,r,cl,cr,k);
		pu(i);
	}
	void mod2(int i,int l,int r,int cl,int cr,ll k){
		pd(i,l,r);
		if(l>=cl&&r<=cr){
			sum1[i]=1ll*(r-l+1)*(l+r)/2*k;
			lz2[i]=k;
			return;
		}
		if(r<cl||l>cr) return;
		mod2(ls,l,mid,cl,cr,k);
		mod2(rs,mid+1,r,cl,cr,k);
		pu(i);
	}
	ll ask(int i,int l,int r,int cl,int cr){
		//cout<<l<<" "<<r<<" "<<sum[i]<<" "<<sum1[i]<<endl;
		pd(i,l,r); ll ans=0;
		if(l>=cl&&r<=cr) ans+=sum[i]-sum1[i];
		else if(r<cl||l>cr) ans+=0;
		else{
			ans+=ask(ls,l,mid,cl,cr);
			ans+=ask(rs,mid+1,r,cl,cr);
		}
		pu(i);
		return ans;
	}
} t;
int n,m,q;
set<int> s;
int v[N];
signed main(){
	IOS
	cin>>n>>m>>q;
	vector<int> xi(m+1);
	rep(i,1,m) cin>>xi[i],s.insert(xi[i]);
	rep(i,1,m){
		int a;cin>>a;
		v[xi[i]]=a;
	}
	t.build(1,1,n);
	int last=-1;
	set<int>::iterator it;
	for(auto vi:s){
		if(last!=-1){
			t.mod1(1,1,n,last+1,vi,1ll*vi*v[last]);
			t.mod2(1,1,n,last+1,vi,v[last]);
		}
		last=vi;
	}
	//rep(i,1,n) t.ask(1,1,n,i,i);
	rep(i,1,q){
		int op,x,k;
		cin>>op>>x>>k;
		if(op==2){
			cout<<t.ask(1,1,n,x,k)<<endl;
		}
		else{
			it=s.lower_bound(x);
			int r=*it;it--;int l=*it;
			s.insert(x);v[x]=k;
			t.mod1(1,1,n,l+1,x,1ll*x*v[l]);
			t.mod2(1,1,n,l+1,x,v[l]);
			t.mod1(1,1,n,x+1,r,1ll*r*k);
			t.mod2(1,1,n,x+1,r,k);
		}
	}
	return 0;
}
/*
8 3 4
1 3 8
3 24 10
2 2 5
1 5 15
2 5 5
2 7 8

*/

标签:last,cl,int,线段,mid,等差数列,cr,模板,define
From: https://www.cnblogs.com/shyiaw/p/18002804

相关文章

  • sqlserver SQLServer Profiler 模板制作和导入
    SQLServerProfiler是一个基于图形界面的工具,用于监视和分析SQLServer数据库系统的活动。目录一、使用标准模板追踪数据库服务器SQL二、制作模板三、导出模板四、将模板文件导入新的客户端五、在新的客户端修改配置和使用模板 使用标准模板追踪数据库服务器SQL ......
  • [算法学习笔记01]线段树
    #[算法学习笔记01]线段树###每日蒟蒻小故事(1/1)蒟蒻刚刚升到S组,发现S组正在学习线段树Ⅲ.蒟蒻并不知道什么是线段树.蒟蒻十分害怕,向大佬询问什么是线段树.大佬邪魅一笑,并未解释.于是可怜的蒟蒻什么也听不懂,只得在洛谷和OIWIKI上自学线段树.“所以什么是线段树?”###什么......
  • 金媒10.3升级解决模板消息失效问题及小程序上架流程
    做为老用户都知道金媒系统是全开源系统,虽然里面有JS文件里会记录域名等服务器信息但是懂技术的去除屏蔽掉即可,但是有一个问题就是微信官方消息模板已经改版了旧的模板不在使用,这就造成所有需要对接的CMS系统都要改版,金媒10.3就是针对这一问题做了升级,即以前所有版本即使安装后也不......
  • 帝国cms看雪时间轴博客趣静态模板bokequV1.
    帝国cms看雪时间轴博客趣静态模板bokequV1.0是一款女生唯美简洁个人博客静态页面模板,蓝色时间轴个人网页模板,下雪空间个人模板。喜欢的网友可以用开源程序帝国cms标签仿站建设http://www.bokequ.com/category/theme博客趣bokequV1.0模板非常简洁清爽,清新优雅,由蓝色背景+......
  • 前缀和---子矩阵的和(模板)
      #include<iostream>usingnamespacestd;constintN=1010;inta[N][N],s[N][N];intmain(){intn,m,q;cin>>n>>m>>q;for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>&g......
  • 一个 WPF + MudBlazor 的项目模板(附:多项目模板制作方法)
    最近做了几个WPF+MudBlazor的小东西,每次从头搭建环境比较繁琐,然鹅搭建过程还没啥技术含量,索性就直接做了个模板,方便以后使用。1.介绍一个用来创建.NET8+WPF+MudBlazor的项目模板适用于VS2022用法:vs插件市场下载or自己通过Github源码编译2.模板打包方......
  • [word] word自动将更改后的内容保存到通用文档模板的解决办法
    word自动将更改后的内容保存到通用文档模板的解决办法打开word时出现“word自动将更改后的内容保存到通用文档模板上。是否加载该模板?”这里直接讲解word2007出现这种问题如何快速解决。方法/步骤点击office按钮-再点击Word选项(弹出的对话框右下角)点击加载项,选则COM加载项->转到由......
  • 【模板】WBLT
    todo:可持久化#include<bits/stdc++.h>usingnamespacestd;#ifdefLOCAL#definedebug(...)fprintf(stderr,##__VA_ARGS__)#else#definedebug(...)void(0)#endiftypedeflonglongLL;template<intN>structWBLT{staticconstexprdoublealph......
  • 线段树合集
    线段树合集线段树:https://oi-wiki.org/ds/seg/扫描线:https://oi-wiki.org/geometry/scanning/orhttps://zhuanlan.zhihu.com/p/103616664orhttps://www.cnblogs.com/Rakan-LoveJ/p/11401851.html标记永久化:https://www.cnblogs.com/wozaixuexi/p/9462461.html李超线段树:ht......
  • [职场] 就业推荐表个人简历模板范文
    就业推荐表个人简历篇1姓名:张大大目前所在:广州年龄:21户口所在:广东省国籍:中国婚姻状况:民族:汉族求职意向人才类型:普通求职应聘职位:财务/会计助理/会计文员工作年限:0职称:无职称求职类型:实习可到职日期:随时......