首页 > 其他分享 >线段树模板,洛谷原题P3373

线段树模板,洛谷原题P3373

时间:2024-08-18 14:15:37浏览次数:12  
标签:ch 洛谷 tag1 tag2 原题 int sum Tree P3373

线段树区间乘、加,范围求和,QWQ
原题

#include <bits/stdc++.h>
#define PII pair <int, int>
#define int long long
#define DB double

namespace FastIO
{
	inline int read(int MOD, int &ret){
		char ch = getchar();int ngtv = 1;
		if(MOD == 0) {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = ret * 10 + (ch - '0');ch = getchar();}}
		else {while(ch < '0' || ch > '9'){if(ch == '-') ngtv = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ret = (ret * 10 % MOD + (ch - '0') % MOD) % MOD;ch = getchar();} }
		return ret * ngtv;}
	inline char cread(char &ch){while(ch == ' ' || ch == '\n' || ch == '\r' || ch == 0) ch = getchar();ch = getchar();return ch;}
}
using namespace FastIO;
using namespace std;

const int N = 4e5 + 10, M = 1e5 + 10;
int A[M], mod, n, q;
int opt, x, y, k;

struct Node
{
	int sum, tag1, tag2;
	// sum:区间和;tag1子节点未加的值;tag2:子节点未乘的值
	int left, right;
	// 左右节点(sum的范围)
}Tree[N];

void init_tree(int x, int left, int right)
{
	Tree[x].left = left;
	Tree[x].right = right;
	
	if(left == right)
	{
		Tree[x].sum = A[left];
		return ;
	}
			
	Tree[x].tag1 = 0;
	Tree[x].tag2 = 1;
	int mid = (left + right) >> 1;
	init_tree(x * 2, left, mid);
	init_tree(x * 2 + 1, mid + 1, right);
	
	Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod;
}

void pushdown(int x)
{
	int l = Tree[x].left, r = Tree[x].right;
	int m = (l + r) >> 1;
	
	Tree[x * 2].sum = (Tree[x * 2].sum * Tree[x].tag2 + (m - l + 1) * Tree[x].tag1) % mod;
	Tree[x * 2 + 1].sum = (Tree[x * 2 + 1].sum * Tree[x].tag2 + (r - m) * Tree[x].tag1) % mod;
	
	Tree[x * 2].tag1 = (Tree[x * 2].tag1 * Tree[x].tag2 + Tree[x].tag1) % mod;
	Tree[x * 2 + 1].tag1 = (Tree[x * 2 + 1].tag1 * Tree[x].tag2 + Tree[x].tag1) % mod;
	Tree[x * 2].tag2 = (Tree[x].tag2 * Tree[x * 2].tag2) % mod;
	Tree[x * 2 + 1].tag2 = (Tree[x].tag2 * Tree[x * 2 + 1].tag2) % mod;
	
	Tree[x].tag1 = 0;
	Tree[x].tag2 = 1;
}

void add(int x, int l, int r, int ad)
{
	if(l > Tree[x].right || Tree[x].left > r)
		return ;

	if(l <= Tree[x].left && Tree[x].right <= r)
	{
		Tree[x].tag1 = (Tree[x].tag1 + ad) % mod;
		Tree[x].sum = (Tree[x].sum + (Tree[x].right - Tree[x].left + 1) * ad % mod) % mod;
		return ;
	}
	
	pushdown(x);
	
	add(x * 2, l , r, ad);
	add(x * 2 + 1, l, r, ad);
		
	Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod;
}

void ride(int x, int l, int r, int rid)
{
	if(l > Tree[x].right || Tree[x].left > r)
		return ;
	
	if(l <= Tree[x].left && Tree[x].right <= r)
	{
		Tree[x].sum = (Tree[x].sum * rid) % mod;
		Tree[x].tag1 = (Tree[x].tag1 * rid) % mod;
		Tree[x].tag2 = (Tree[x].tag2 * rid) % mod;
		return ;
	}
	
	pushdown(x);
	
	ride(x * 2, l, r, rid);
	ride(x * 2 + 1, l, r, rid);
	
	Tree[x].sum = (Tree[x * 2].sum + Tree[x * 2 + 1].sum) % mod; 
}

int sum(int x, int l, int r)
{
	if(l > Tree[x].right || Tree[x].left > r)
		return 0;
	
	if(l <= Tree[x].left && Tree[x].right <= r)
		return Tree[x].sum;
	
	pushdown(x);
	
	return (sum(x * 2, l, r) + sum(x * 2 + 1, l, r)) % mod;
}

signed main()
{
	read(0, n), read(0, q), read(0, mod);
	for(int i = 1; i <= n; i ++ )
		read(0, A[i]);
	
	init_tree(1, 1, n);
	// 创建一个线段树 √
	
	for(; q; q -- )
	{
		scanf("%d", &opt);
		
		if(opt == 1)
		{
			scanf("%d%d%d", &x, &y, &k);
			ride(1, x, y, k);
		}
		if(opt == 2)
		{
			scanf("%d%d%d", &x, &y, &k);
			add(1, x, y, k);
		}
		if(opt == 3)
		{
			scanf("%d%d", &x, &y);
			k = sum(1, x, y);
			printf("%lld\n", k);
		}
	}
	
    return 0;
}

标签:ch,洛谷,tag1,tag2,原题,int,sum,Tree,P3373
From: https://www.cnblogs.com/Hu-yan-xin/p/18365609

相关文章

  • 洛谷P1536 村村通
    传送门:P1536村村通人间风起,四季同书。(还是一篇817的做题记录la~)题意:有好多组数据,每组数据给你m条无向边的信息(u,v);问你最少再添加多少条边就能使整张图连通。思路:首先我们要知道,一个图如果连通,边的数量最少是n-1;但是题目会出现这样一种情况:n=4,m=3;1<——>......
  • 洛谷 B3735 B3736 B3787 题解
    嘿嘿我发烧已经好了!题目目录:No.1 B3735[信息与未来2018]圣诞树No.2 B3736[信息与未来2018]最大公约数No.3 B3787[信息与未来2023]精密计时 OK,开始正文!第一题:B3735[信息与未来2018]圣诞树 题目描述圣诞树共有 nn 层,从上向下数第 11 层有 11 个......
  • 洛谷P5663 [CSP-J2019] 加工零件
    传送门:P5663[CSP-J2019]加工零件这是一篇写于2024.8.17的做题记录,祝稻米朋友们节日快乐。废话还是少说一点比较好qwq题目意思:(一个很抽象的东西)说白了其实就是给你一张无向图,然后有p次询问,每次询问给你一个v和L,问你从1号点到v号点有没有长度为L的边。注意......
  • 洛谷p1717题解
    题目描述话说发源于小朋友精心设计的游戏被电脑组的童鞋们藐杀之后非常不爽,为了表示安慰和鼓励,VIP999决定请他吃一次“年年大丰收”,为了表示诚意,他还决定亲自去钓鱼。但是,因为还要准备NOIP2013,z老师只给了他 H 个小时的空余时间,假设有 n 个鱼塘都在一条水平路边,从左......
  • 洛谷p2580题解
    题目背景XS中学化学竞赛组教练是一个酷爱炉石的人。他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次,然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉(详情请见已结束比赛CON900)。题目描述这之后校长任命你为特派探员,每天记录他的点名。校长会提供化学竞......
  • 洛谷——P1102 A-B 数对
    题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数CCC,......
  • 洛谷——P1093 [NOIP2007 普及组] 奖学金
    题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都有......
  • 洛谷题单指南-常见优化技巧-P2866 [USACO06NOV] Bad Hair Day S
    原题链接:https://www.luogu.com.cn/problem/P2866题意解读:每个牛能看到的右边比他矮的牛,直到有比他高的挡住为止,因此只用找每个牛右边第一个比他高的牛的位置即可计算中间比他矮的有多少。解题思路:典型的单调栈应用,注意,常规的单调栈可以用来:1、找每个数左边第一个比他小的数的......
  • 洛谷题单指南-常见优化技巧-P4147 玉蟾宫
    原题链接:https://www.luogu.com.cn/problem/P4147题意解读:找到一个只包含'F'的最大的子矩形。解题思路:方法1:设R为0,F为1,先计算二维前缀和,再枚举所有子矩形左上角(x1,y1)、右下角(x2,y2),计算子矩形的区间和,更新最大值,只能得到部分分。方法2:对于二维矩阵每个点,定义三个属性:h[][]......
  • 洛谷P1786
    6.帮贡排序题目链接:[P1786帮贡排序-洛谷|计算机科学教育新生态(luogu.com.cn)]()题目背景在absi2011的帮派里,死号偏多。现在absi2011和帮主等人联合决定,要清除一些死号,加进一些新号,同时还要鼓励帮贡多的人,对帮派进行一番休整。题目描述目前帮派内共最多有一位帮主,......