[CF438D] The Child and Sequence - 线段树
Description
给定数列,查询区间和,区间取模,单点修改。
Solution
线段树,记录区间最大值,如果大于要取模的数就把修改暴力递归下去。
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct SegmentTree
{
struct Node
{
int sum;
int mx;
Node operator+(const Node &rhs)
{
return {sum + rhs.sum, max(mx, rhs.mx)};
}
};
vector<Node> node;
int n;
SegmentTree(int n) : n(n)
{
node.resize(4 * n + 9);
}
void build(int p, int l, int r, vector<int> &vec)
{
if (l == r)
node[p] = {vec[l], vec[l]};
else
build(p * 2, l, (l + r) / 2, vec), build(p * 2 + 1, (l + r) / 2 + 1, r, vec), node[p] = node[p * 2] + node[p * 2 + 1];
}
void Build(vector<int> &vec)
{
build(1, 1, n, vec);
}
void single_modify(int p, int l, int r, int pos, int key)
{
if (l == r)
node[p] = {key, key};
else if (pos <= (l + r) / 2)
single_modify(p * 2, l, (l + r) / 2, pos, key), node[p] = node[p * 2] + node[p * 2 + 1];
else
single_modify(p * 2 + 1, (l + r) / 2 + 1, r, pos, key), node[p] = node[p * 2] + node[p * 2 + 1];
}
void SingleModify(int pos, int key)
{
single_modify(1, 1, n, pos, key);
}
void modify(int p, int l, int r, int ql, int qr, int md)
{
if (l > qr || r < ql || node[p].mx < md)
return;
if (l == r)
{
node[p].sum %= md;
node[p].mx %= md;
}
else
{
modify(p * 2, l, (l + r) / 2, ql, qr, md);
modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, md);
node[p] = node[p * 2] + node[p * 2 + 1];
}
}
void Modify(int ql, int qr, int md)
{
modify(1, 1, n, ql, qr, md);
}
Node query(int p, int l, int r, int ql, int qr)
{
if (l > qr || r < ql)
return {0, 0};
if (l >= ql && r <= qr)
return node[p];
return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
}
int Query(int ql, int qr)
{
return query(1, 1, n, ql, qr).sum;
}
};
signed main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n + 2);
for (int i = 1; i <= n; i++)
cin >> a[i];
SegmentTree seg(n);
seg.Build(a);
for (int i = 1; i <= m; i++)
{
int t1, t2, t3, t4;
cin >> t1 >> t2 >> t3;
if (t1 == 1)
{
cout << seg.Query(t2, t3) << endl;
}
else if (t1 == 2)
{
cin >> t4;
seg.Modify(t2, t3, t4);
}
else if (t1 == 3)
{
seg.SingleModify(t2, t3);
}
}
}