D. The Child and Sequence

Description

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

Solution

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

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

• 若 x < p x < p x<p：不用模；
• 若 x ≥ p x\ge p x≥p：设 x = p q + r ( 0 ≤ r < p ) x = pq + r(0\le r < p) x=pq+r(0≤r<p)，则 q ≥ 1 q\ge 1 q≥1，于是操作后得到的数 r < x 2 r < \dfrac{x}{2} r<2x​。

对于第一种情况，记录区间最大值 m x mx mx，当 m x < p mx < p mx<p 时直接 return；

对于第二种情况，数 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 次。

Code

// 18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#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("%lld\n", 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;
}