AcWing1277. 维护序列
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为 NN 的数列，不妨设为 a1,a2,…,aN
有如下三种操作形式：
把数列中的一段数全部乘一个值；
把数列中的一段数全部加一个值；
询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
输入格式
第一行两个整数 N 和 P；
第二行含有 N 个非负整数，从左到右依次为 a 1 , a 2 , … , a N
第三行有一个整数 M，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作 11：1 t g c，表示把所有满足 t ≤ i ≤ g 的 a i改为 a i × c
操作 22：2 t g c，表示把所有满足 t ≤ i ≤ g 的 a i改为 a i + c
操作 33：3 t g，询问所有满足 t ≤ i ≤ g 的 a i的和模 P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
数据范围
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define fi first #define se second #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 #define mem(n,a) memset(n,a,sizeof(n)) #define rep(i,be,en) for(int i=be;i<=en;++i) #define pre(i,be,en) for(int i=en;i>=be;--i) inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 100100; int n,m, p; int w[N]; struct node { int l, r; LL sum, add, mul; }tr[4 * N]; void pushup(int u) { tr[u].sum = LL(tr[u << 1].sum + tr[u << 1 | 1].sum) % p; } void eval(node& t, int add, int mul) { t.sum = ((LL)t.sum * mul + (LL)(t.r - t.l + 1) * add) % p; t.mul = (LL)t.mul * mul % p; t.add = ((LL)t.add * mul + add) % p; } void pushdown(int u) { eval(tr[u << 1], tr[u].add, tr[u].mul); eval(tr[u << 1 | 1], tr[u].add, tr[u].mul); tr[u].add = 0; tr[u].mul = 1; } void build(int u, int l, int r) { if (l == r) { tr[u] = { r,r,w[r],0,1 }; } else { tr[u] = { l,r,0,0,1 }; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int l, int r, int add, int mul) { if (tr[u].l >= l && tr[u].r <= r)eval(tr[u], add, mul); else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid)modify(u << 1, l, r, add, mul); if (r > mid)modify(u << 1 | 1, l, r, add, mul); pushup(u); } } int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r)return tr[u].sum % p; else { pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL sum = 0; if (l <= mid)sum = query(u << 1, l, r); if (r > mid)sum = (sum + query(u << 1 | 1, l, r)) % p; return sum; } } int main() { cin >> n >> p; for (int i = 1;i <= n;++i)scanf("%d", &w[i]); build(1, 1, n); cin >> m; int t, l, r, d; while (m--) { scanf("%d%d%d", &t, &l, &r); if (t == 1) { scanf("%d", &d); modify(1, l, r, 0, d); } else if (t == 2) { scanf("%d", &d); modify(1, l, r, d, 1); } else { printf("%d\n", query(1, l, r)); } } return 0; }
