信息学奥赛一本通 1551：维护序列

【题目链接】

ybt 1551：维护序列

【题目考点】

1. 线段树

• 区间修改 区间查询

【解题思路】

本题与洛谷 P3373 【模板】线段树 2大体相同，只有输入输出格式略有不同，具体解析请见上题的博文。

【题解代码】

解法1：线段树

#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define ADD 1
#define MUL 2
struct Node
{int l, r, m, val, tagAdd, tagMul;
} tree[4*N];
int n, p, m, a[N];
void pushUp(int i)
{tree[i].val = (tree[2*i].val+tree[2*i+1].val)%p;
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r, tree[i].m = l+r>>1, tree[i].tagMul = 1;if(l == r){tree[i].val = a[l];return;}build(2*i, l, tree[i].m);build(2*i+1, tree[i].m+1, r);pushUp(i);
}
void addTag(int type, int i, long long v)//v设为long long保证下面的运算都是long long类型的 
{if(type == ADD){tree[i].tagAdd = (tree[i].tagAdd+v)%p;tree[i].val = (tree[i].val+(tree[i].r-tree[i].l+1)*v)%p;}else //type == MUL{tree[i].tagMul = tree[i].tagMul*v%p;tree[i].tagAdd = tree[i].tagAdd*v%p;//增加的值也乘v tree[i].val = tree[i].val*v%p;}
}
void pushDown(int i)//只有在tagAdd和tagMul二者只有其一时，才能下传 
{if(tree[i].tagAdd == 0 && tree[i].tagMul == 1)return;addTag(MUL, 2*i, tree[i].tagMul);//必须先乘后加 addTag(MUL, 2*i+1, tree[i].tagMul);addTag(ADD, 2*i, tree[i].tagAdd);addTag(ADD, 2*i+1, tree[i].tagAdd);tree[i].tagAdd = 0, tree[i].tagMul = 1;
}
void update(int type, int i, int l, int r, int v)
{if(tree[i].r < l || tree[i].l > r)return;if(l <= tree[i].l && tree[i].r <= r){addTag(type, i, v);return;}pushDown(i);update(type, 2*i, l, r, v);update(type, 2*i+1, l, r, v);pushUp(i);
}
int query(int i, int l, int r)
{if(tree[i].r < l || tree[i].l > r)return 0;if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;pushDown(i);return (query(2*i, l, r) + query(2*i+1, l, r))%p;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int op, t, g, c;cin >> n >> p;for(int i = 1; i <= n; ++i)cin >> a[i];cin >> m;build(1, 1, n);while(m--){cin >> op;if(op == 1){cin >> t >> g >> c;update(MUL, 1, t, g, c);}else if(op == 2){cin >> t >> g >> c;update(ADD, 1, t, g, c);}else{cin >> t >> g;cout << query(1, t, g) << '\n';}}return 0;
}