IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> [AHOI 2009]维护序列 -> 正文阅读

[数据结构与算法][AHOI 2009]维护序列

原题

题目大意:

有一个初始序列,你要维护其3个操作:

1.格式:1 x y k 表示把区间[x,y]乘以k。

2.格式:2 x y k 表示把区间[x,y]加上k。

3.格式:3 x y 表示求区间[x,y]的和。

思路:

标准的线段树模板,蒟蒻打了3小时才过。

解题过程:

线段树是一种灵活的数据结构,在信竞中较为常见。

它的原理是这样的:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?上图为区间[1,6]的线段树

?序列中的每个元素即为线段树中的叶子节点,在一个子树中父节点=左孩子+右孩子。

所以定义一个结构体:

struct Node{
	ll l,r,k;//左孩子,右孩子,值
	ll add,mul;//加法和乘法
}tree[N<<2];//N<<2=N*4,线段树空间通常开4倍大

那我们如何建树呢?

上文说了,当节点为孩子节点是便是序列值,所以l==r时就是叶子节点。

所以建树程序如下:

inline ll build_tree(ll value,ll l,ll r){//ll 为提前定义的long long
	tree[value]=Node{l,r,0,0,1};//初始化
	if (l==r){
		ll num;
		scanf("%lld",&num);
		return tree[value].k=num%Mod;//存储时注意取模
	}
	ll mid=(l+r)>>1;
	return tree[value].k=(build_tree(value<<1,l,mid)+build_tree(value<<1|1,mid+1,r))%Mod;
    //线段树左边加右边
}

接着就是更新节点环节了,要更新3部分:

加法更新,乘法更新,和的更新。

inline void pushdown(ll value){
	tree[value*2].add=(tree[value].add+tree[value*2].add*tree[value].mul)%Mod;
    //左孩子加法更新:不用担心tree[value].mul没有值,初始化时变成1的
	tree[value*2+1].add=(tree[value].add+tree[value*2+1].add*tree[value].mul)%Mod;
    //右孩子加法更新,同上
	tree[value*2].mul=(tree[value].mul*tree[value*2].mul)%Mod;
	tree[value*2+1].mul=(tree[value].mul*tree[value*2+1].mul)%Mod;
    //乘法更新时不会乘上加法,注意!
	tree[value*2].k=(tree[value].mul*tree[value*2].k+tree[value].add*(tree[value*2].r-tree[value*2].l+1))%Mod;
	tree[value*2+1].k=(tree[value].mul*tree[value*2+1].k+tree[value].add*(tree[value*2+1].r-tree[value*2+1].l+1))%Mod;
    //更新左右孩子当前值
	tree[value].add=0;
	tree[value].mul=1;
    //还原
}

我们还有要区间更新的地方updata,见下:

inline void updata(ll value,ll x,ll pos,ll L,ll R){
	pushdown(value);//单点修改
	if (pos==1&&tree[value].l>=L&&tree[value].r<=R){//乘法操作
		tree[value].mul=(tree[value].mul*x)%Mod;
        tree[value].add=(tree[value].add*x)%Mod;
        tree[value].k=(tree[value].k*tree[value].mul)%Mod;
        return;
	}
	if(pos==2&&tree[value].l>=L&&tree[value].r<=R){//加法操作
        tree[value].add=(tree[value].add+x)%Mod;
        tree[value].k=(tree[value].k+tree[value].add*(tree[value].r-tree[value].l+1))%Mod;
        return;
    }
    ll mid=(tree[value].l+tree[value].r)/2;//分为2个区间
    if(L<=mid)
        updata(value*2,x,pos,L,R);
    if(R>mid)
        updata((value*2)+1,x,pos,L,R);
    tree[value].k=(tree[value*2].k+tree[value*2+1].k)%Mod;//tree[value].k的更新直接两边相加
}

那这时候只缺查询操作了。

inline ll query(ll value,ll L,ll R){
	pushdown(value);//单点修改
	if (tree[value].l>=L&&tree[value].r<=R)
		return tree[value].k%Mod;//如果是已经合并了的,直接返回
	ll mid=(tree[value].l+tree[value].r)>>1;
    return ((L<=mid?query(value*2,L,R):0)+(R>mid?query(value*2+1,L,R):0))%Mod;
    //左区间如果存在就加,右区间同理
}

至此,我们的线段树终于完成。

下面贴出此题代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+1;
struct Node{
	ll l;
	ll r;
	ll k;
	ll add;
	ll mul;
}tree[N*4];
ll n,m,Mod,pos;
inline ll build_tree(ll value,ll l,ll r){
	tree[value]=Node{l,r,0,0,1};
	if (l==r){
		ll num;
		scanf("%lld",&num);
		return tree[value].k=num%Mod;
	}
	ll mid=(l+r)>>1;
	return tree[value].k=(build_tree(value*2,l,mid)+build_tree(value*2+1,mid+1,r))%Mod;
}
inline void pushdown(ll value){
	tree[value*2].add=(tree[value].add+tree[value*2].add*tree[value].mul)%Mod;
	tree[value*2+1].add=(tree[value].add+tree[value*2+1].add*tree[value].mul)%Mod;
	tree[value*2].mul=(tree[value].mul*tree[value*2].mul)%Mod;
	tree[value*2+1].mul=(tree[value].mul*tree[value*2+1].mul)%Mod;
	tree[value*2].k=(tree[value].mul*tree[value*2].k+tree[value].add*(tree[value*2].r-tree[value*2].l+1))%Mod;
	tree[value*2+1].k=(tree[value].mul*tree[value*2+1].k+tree[value].add*(tree[value*2+1].r-tree[value*2+1].l+1))%Mod;
	tree[value].add=0;
	tree[value].mul=1;
}
inline ll query(ll value,ll L,ll R){
	pushdown(value);
	if (tree[value].l>=L&&tree[value].r<=R)
		return tree[value].k%Mod;
	ll mid=(tree[value].l+tree[value].r)>>1;
    return ((L<=mid?query(value*2,L,R):0)+(R>mid?query(value*2+1,L,R):0))%Mod;
}
inline void updata(ll value,ll x,ll pos,ll L,ll R){
	pushdown(value);
	if (pos==1&&tree[value].l>=L&&tree[value].r<=R){
		tree[value].mul=(tree[value].mul*x)%Mod;
        tree[value].add=(tree[value].add*x)%Mod;
        tree[value].k=(tree[value].k*tree[value].mul)%Mod;
        return;
	}
	if(pos==2&&tree[value].l>=L&&tree[value].r<=R){
        tree[value].add=(tree[value].add+x)%Mod;
        tree[value].k=(tree[value].k+tree[value].add*(tree[value].r-tree[value].l+1))%Mod;
        return;
    }
    ll mid=(tree[value].l+tree[value].r)/2;
    if(L<=mid)
        updata(value*2,x,pos,L,R);
    if(R>mid)
        updata((value*2)+1,x,pos,L,R);
    tree[value].k=(tree[value*2].k+tree[value*2+1].k)%Mod;
}
int main(){
	scanf("%lld%lld",&n,&Mod);
	build_tree(1,1,n);
	cin>>m;
	for (ll i=1;i<=m;i++){
		cin>>pos;
		ll x,y;
		cin>>x>>y; 
		if (pos!=3){
			ll k;
			cin>>k;
			updata(1,k,pos,x,y);
		}
		else if (pos==3)
			printf("%lld\n",query(1,x,y));
	}
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-23 16:56:46  更:2021-08-23 16:57:05 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 22:53:29-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码