[AHOI2009] 维护序列
[AHOI2009] 维护序列
题目背景
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
题目描述
有一个长为 n n n 的数列 { a n } \{a_n\} {an},有如下三种操作形式:
- 格式
1 t g c
,表示把所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 改为 a i × c a_i\times c ai×c ; - 格式
2 t g c
表示把所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 改为 a i + c a_i+c ai+c ; - 格式
3 t g
询问所有满足 t ≤ i ≤ g t\le i\le g t≤i≤g 的 a i a_i ai 的和,由于答案可能很大,你只需输出这个数模 p p p 的值。
输入格式
第一行两个整数 n n n 和 p p p。
第二行含有 n n n 个非负整数,表示数列 { a i } \{a_i\} {ai} 。
第三行有一个整数 m m m,表示操作总数。
从第四行开始每行描述一个操作,同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出格式
对每个操作 3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。
样例 #1
样例输入 #1
7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7
样例输出 #1
2
35
8
提示
样例输入输出 1 解释
- 初始时数列为 { 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{1,2,3,4,5,6,7\} {1,2,3,4,5,6,7}。
- 经过第 1 1 1 次操作后,数列为 { 1 , 10 , 15 , 20 , 25 , 6 , 7 } \{1,10,15,20,25,6,7\} {1,10,15,20,25,6,7}。
- 对第 2 2 2 次操作,和为 10 + 15 + 20 = 45 10+15+20=45 10+15+20=45,模 43 43 43 的结果是 2 2 2。
- 经过第 3 3 3 次操作后,数列为 { 1 , 10 , 24 , 29 , 34 , 15 , 16 } \{1,10,24,29,34,15,16\} {1,10,24,29,34,15,16}。
- 对第 4 4 4 次操作,和为 1 + 10 + 24 = 35 1+10+24=35 1+10+24=35,模 43 43 43 的结果是 35 35 35。
- 对第 5 5 5 次操作,和为 29 + 34 + 15 + 16 = 94 29+34+15+16=94 29+34+15+16=94,模 43 43 43 的结果是 8 8 8。
数据规模与约定
测试数据规模如下表所示:
数据点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,10 |
---|---|---|---|---|---|---|---|---|---|
n = n= n= | 10 10 10 | 1000 1000 1000 | 1000 1000 1000 | 10000 10000 10000 | 60000 60000 60000 | 70000 70000 70000 | 80000 80000 80000 | 90000 90000 90000 | 100000 100000 100000 |
m = m= m= | 10 10 10 | 1000 1000 1000 | 1000 1000 1000 | 10000 10000 10000 | 60000 60000 60000 | 70000 70000 70000 | 80000 80000 80000 | 90000 90000 90000 | 100000 100000 100000 |
对于全部的测试点,保证 0 ≤ p , a i , c ≤ 1 0 9 0 \leq p, a_i, c \leq 10^9 0≤p,ai,c≤109, 1 ≤ t ≤ g ≤ n 1 \leq t \leq g \leq n 1≤t≤g≤n。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rc(x) ((x<<1)|1)
#define lc(x) (x<<1)
const int M = 1e6;
const int N = 1e18;
int a[M], n, m, mod;
void read() {
cin >> n >> mod;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m ;
}
struct node {
int sum, mul, add;
};
struct segment {
node seg[M << 2];
void push_up(int x) {
seg[x].sum = (seg[lc(x)].sum + seg[rc(x)].sum) % mod;
}
void build(int o, int l, int r) {
seg[o].mul = 1; seg[o].add = 0;
if (l == r) {
seg[o].sum = a[l];
return;
}
int mid = (l + r) >> 1;
build(lc(o), l, mid);
build(rc(o), mid + 1, r);
push_up(o);
}
void f(int o, int l, int r, int add, int mul) {
seg[o].mul = (seg[o].mul * mul) % mod;
seg[o].add = (seg[o].add * mul) % mod;
seg[o].add = (seg[o].add + add) % mod;
seg[o].sum = (seg[o].sum * mul) % mod;
seg[o].sum = (seg[o].sum + (r - l + 1) * add) % mod;
}
void push_down(int o, int l, int r) {
int mid = (l + r) >> 1;
f(lc(o), l, mid, seg[o].add, seg[o].mul);
f(rc(o), mid + 1, r, seg[o].add, seg[o].mul);
seg[o].add = 0; seg[o].mul = 1;
}
void update(int ql, int qr, int add, int mul, int o = 1, int l = 1, int r = n) {
if (ql <= l and r <= qr) { f(o, l, r, add, mul); return; }
int mid = (l + r) >> 1;
push_down(o, l, r);
if (ql <= mid) update(ql, qr, add, mul, lc(o), l, mid);
if (qr >= 1 + mid)update(ql, qr, add, mul, rc(o), mid + 1, r);
push_up(o);
}
int query(int ql, int qr, int o = 1, int l = 1, int r = n) {
if (ql <= l and r <= qr) return seg[o].sum;
int mid = (l + r) >> 1, ans = 0;
push_down(o, l, r);
if (ql <= mid) ans = (ans + query(ql, qr, lc(o), l, mid)) % mod;
if (mid + 1 <= qr) ans = (ans + query(ql, qr, rc(o), mid + 1, r)) % mod;
push_up(o);
return ans%mod;
}
}T1;
void solve() {
int opt, x, y, k;
cin >> opt >> x >> y;
switch (opt) {
case 1: {
cin >> k;
T1.update(x, y, 0, k);
break;
}
case 2: {
cin >> k;
T1.update(x, y, k, 1);
break;
}
default:cout << T1.query(x, y) << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
read();
T1.build(1, 1, n);
while (m--) solve();
return 0;
}
说明
实现支区间加、区间乘和区间求和
-
#define int long long
将int
类型重定义为long long
类型 -
#define rc(x) ((x<<1)|1)
和#define lc(x) (x<<1)
定义了计算线段树左右子节点下标的宏。 -
全局数组
a[M]
存储原始数据,n
表示数据规模,m
表示操作次数,mod
用于取模运算。 -
node
结构体定义了线段树节点的三个属性:sum
表示区间和,mul
表示乘法懒惰标记,add
表示加法懒惰标记。 -
segment
结构体封装了线段树的主要操作:push_up(int x)
用于更新节点x
的sum
值,通过其左右子节点的sum
值计算得出。build(int o, int l, int r)
是线段树的构建函数,采用递归方式构建。push_down(int o, int l, int r)
用于下推节点o
的懒惰标记到其左右子节点。update(int ql, int qr, int add, int mul, int o, int l, int r)
是线段树的更新函数,用于更新区间[ql, qr]
上的值,可以是加法或乘法更新。query(int ql, int qr, int o, int l, int r)
是线段树的查询函数,用于查询区间[ql, qr]
的和。
需要注意乘法的优先级更高,处理好加乘关系
原文地址:https://blog.csdn.net/2301_77920554/article/details/136411848
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!