CodeForces#438 D.The Child and Sequence

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

#.The Child and Sequence

题面

At the children’s day, the child came to Picks’s house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite sequence of Picks.

Fortunately, Picks remembers how to repair the sequence. Initially he should create an integer array $a[1],a[2],…,a[n]$ . Then he should perform a sequence of $m$ operations. An operation can be one of the following:

1. Print operation $l,r$ . Picks should write down the value of $\sum_{i=l}^ra[i]$.
2. Modulo operation $l,r,x$ . Picks should perform assignment $ a[i]=a[i]\ mod\ x $ for each $i$ $(l\le i\le r) $ .
3. Set operation $k,x$ . Picks should set the value of $a[k]$ to $x$ (in other words perform an assignment $a[k]=x$ ).

Can you help Picks to perform the whole sequence of op

erations?

---

简要翻译

给定你一个数列，要求支持区间和查询，区间取模，单点修改。

---

Input

第一行包含两个整数$n,m$。

第二行包含用空格隔开的$n$个整数，$a[1],a[2],a[3]…a[n]$代表序列的值。

下面包含$m$行。每行开头包含一个整数$type$表示操作类型。

• 若$type=1$，后面跟着两个整数$l,r$，求$sum[l,r]$
• 若$type=2$，后面跟着三个整数$l,r,x$，表示区间$[l,r]$对$x$取模。
• 若$type=3$，后面跟着两个整数$k,x$，表示将$a[k]$修改为$x$。

---

Output

对于每个操作$1$，输出一个整数表示答案。

注意，答案可能会超出$int$。

---

Sample Input 1

5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3

---

Sample Output 1

8

5

---

Sample Input 2

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

---

Sample Output 2

49
15
23
1
9

---

Hint

$1\le n,m\le 10^5,1\le a[i]\le 10^9$。

$type∈\{1,2,3\}$。

操作$1$中，$1\le l\le r\le n$。

操作$2$中，$1\le l\le r\le n,1\le x\le 10^9$。

操作$3$中，$1\le k\le n,1\le x\le 10^9$。

---

样例解释

Σ(⊙▽⊙”a需要解释嘛？好吧还是解释一下吧www，只解释样例一哦

一开始,$a=1,2,3,4,5$。

第$1$次操作，$a=1,2,3,0,1$。

第$2$次操作，$a=1,2,5,0,1$。

第$3$次操作，$Ans=2+5+0+1=8$。

第$4$次操作，$a=1,2,2,0,1$。

第$5$次操作，$Ans=1+2+2=5$。

---

这道题啊，操作$1$和$3​$都是模板题吧？

那么，操作$2$怎么办呢？

对于操作$2$我们想：

• 如果我们原来的$a_i<x$的话呢？那么我们就不需要取模了，这样就可以节约时间。
• 若果我们原来的$a_i>=x$的话，我们就可以暴力维护。因为我们可以证明，一个数最多被模$log\ a_i$次，不懂得话就自己手推一波吧，很快的。

所以说，我们只需要维护区间最大值，如果最大值小于$x$的话，那么我们就直接在$change$里直接$return$就好了。

线段树本身时间复杂度$O(nlog\ n)$，乘$log \ a_i$，所以总时间复杂度为$O(nlog(n)loga_(i))​$。

---

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x = 0, w = 0;
	char ch = 0;
	while (!isdigit(ch)) {w |= ch == '-'; ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0'; ch = getchar();}
	return w ? -x : x;
}
int n,m;
const int N=100010;
struct seg_tree
{
	long long s;
	long long Max;
}t[N<<2];
int a[N];
void pushup(int root)
{
	t[root].s=t[root<<1].s+t[root<<1|1].s;
	t[root].Max=max(t[root<<1].Max,t[root<<1|1].Max);
}
void build(int root,int l,int r)
{
	if(l==r)
	{
		t[root].s=t[root].Max=a[l];
		return;
	}
	int mid=l+r>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	pushup(root);
}
void change(int root,int l,int r,int pos,int k)
{
	if(l==r)
	{
		t[root].s=t[root].Max=k;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) change(root<<1,l,mid,pos,k);
	if(pos>mid) change(root<<1|1,mid+1,r,pos,k);
	pushup(root);
}
void mod_it(int root,int l,int r,int ll,int rr,int mod)
{
	if(t[root].Max<mod) return;
	if(l==r)
	{
		t[root].s%=mod;
		t[root].Max%=mod;
		return;
	}
	int mid=l+r>>1;
	if(ll<=mid) mod_it(root<<1,l,mid,ll,rr,mod);
	if(rr>mid) mod_it(root<<1|1,mid+1,r,ll,rr,mod);
	pushup(root);
}
long long query(int root,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr) return t[root].s;
	int mid=l+r>>1;
	long long t=0;
	if(ll<=mid) t+=query(root<<1,l,mid,ll,rr);
	if(rr>mid) t+=query(root<<1|1,mid+1,r,ll,rr);
	return t;
}
int main(int argc, char const *argv[])
{
	n=read(),m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	build(1,1,n);
	while(m--)
	{
		int type=read();
		if(type==1)
		{
			int l=read(),r=read();
			printf("%lld\n",query(1,1,n,l,r));
		}
		else if(type==2)
		{
			int l=read(),r=read(),mod=read();
			mod_it(1,1,n,l,r,mod);
		}
		else
		{
			int pos=read(),k=read();
			change(1,1,n,pos,k);
		}
	}
	return 0;
}