『题解』Codeforces-438D The Child and Sequence

D. The Child and Sequence

给定数列，区间查询和，区间取模，单点修改。 n , m ≤ 1 0 5 , a i ≤ 1 0 9 n, m leq 10^5, a_ile 10^9 n,m≤105,ai​≤109。 Solution

思路与 花神游历各国 很像。

假设现在是 x   m o d   p xbmod p xmodp：

若 x < p x < p x对于第一种情况，记录区间最大值 m x mx mx，当 m x < p mx < p mx

对于第二种情况，数 n n n 至多经过 log ⁡ n log n logn 次取模操作就会变成 1 1 1，所以区间取模直接暴力递归即可。

一开始共可以被模 n log ⁡ a n log a nloga 次，然后单点修改可以使一个数多被模 log ⁡ log log 次，所以一共是 ( n + m ) log ⁡ a (n + m)log a (n+m)loga 次。

// 18 = 9 + 9 = 18.
#include 
#include 
#define Debug(x) cout << #x << "=" << x << endl
#define int long long
using namespace std;

const int MAXN = 1e5 + 5;

int a[MAXN];

#define lson pos << 1
#define rson pos << 1 | 1

struct tree
{
	int l, r, mx, sum;
}t[MAXN << 2];

void pushup(int pos)
{
	t[pos].mx = max(t[lson].mx, t[rson].mx);
	t[pos].sum = t[lson].sum + t[rson].sum;
}

void build(int pos, int l, int r)
{
	t[pos].l = l, t[pos].r = r;
	if (l == r)
	{
		t[pos].mx = t[pos].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lson, l, mid);
	build(rson, mid + 1, r);
	pushup(pos);
}

void update_val(int pos, int dis, int k)
{
	int l = t[pos].l, r = t[pos].r;
	if (l == r)
	{
		t[pos].mx = t[pos].sum = k;
		return;
	}
	int mid = (l + r) >> 1;
	if (dis <= mid)
	{
		update_val(lson, dis, k);
	}
	else
	{
		update_val(rson, dis, k);
	}
	pushup(pos);
}

void update_mod(int pos, int L, int R, int k)
{
	if (t[pos].mx < k)
	{
		return;
	}
	int l = t[pos].l, r = t[pos].r;
	if (l == r)
	{
		t[pos].mx %= k;
		t[pos].sum %= k;
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid)
	{
		update_mod(lson, L, R, k);
	}
	if (R > mid)
	{
		update_mod(rson, L, R, k);
	}
	pushup(pos);
}

int query(int pos, int L, int R)
{
	int l = t[pos].l, r = t[pos].r;
	if (L <= l && r <= R)
	{
		return t[pos].sum;
	}
	int mid = (l + r) >> 1, res = 0;
	if (L <= mid)
	{
		res = query(lson, L, R);
	}
	if (R > mid)
	{
		res += query(rson, L, R);
	}
	return res;
}

signed main()
{
	int n, m;
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", a + i);
	}
	build(1, 1, n);
	while (m--)
	{
		int op, l, r, k;
		scanf("%lld%lld%lld", &op, &l, &r);
		if (op == 1)
		{
			printf("%lldn", query(1, l, r));
		}
		else if (op == 2)
		{
			scanf("%lld", &k);
			update_mod(1, l, r, k);
		}
		else
		{
			update_val(1, l, r);
		}
	}
	return 0;
}