Description
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 mm operations. An operation can be one of the following:
- Print operation (l,r) . Picks should write down the value of
.
- Modulo operation (l,r,x) . Picks should perform assignment $ a[i]=a[i] mod x $ for each (i (l<=i<=r)) .
- 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 operations?
Input
The first line of input contains two integer: n,mn,m (1<=n,m<=10^{5})(1<=n,m<=105) . The second line contains nn integers, separated by space: $ a[1],a[2],...,a[n] (1<=a[i]<=10^{9}) $ — initial value of array elements.
Each of the next mm lines begins with a number typetype
.
- If type=1type=1 , there will be two integers more in the line: $ l,r (1<=l<=r<=n) $ , which correspond the operation 1.
- If type=2type=2 , there will be three integers more in the line: $ l,r,x (1<=l<=r<=n; 1<=x<=10^{9}) $ , which correspond the operation 2.
- If type=3type=3 , there will be two integers more in the line: $ k,x (1<=k<=n; 1<=x<=10^{9}) $ , which correspond the operation 3.
Output
For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.
题目大意：
- 给出一个序列，进行如下三种操作：
- 区间求和
- 区间每个数模 xx
- 单点修改
- n,m≤100000
裸的线段树问题.,但是问题在于如何取模。
很容易想到的是,如果区间的最大值比取模的数小,那么我们就不需要修改。
因此，我们维护区间最大值。
但是如何修改？我们需要知道其位置。
因此,我们维护最大值位置,然后单点修改即可。
每次判断区间最大值时候比取模的数小。
如果小,那我们就不用取模,所以就可以切掉这个题了！
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#define int long long
#define R register
using namespace std;
const int gz=1e5+8;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
#define ls o<<1
#define rs o<<1|1
int tr[gz<<2],mx[gz<<2],val[gz],n,m;
inline int idmax(R int x,R int y)
{
return val[x]>val[y] ? x:y;
}
inline void up(R int o)
{
mx[o]=idmax(mx[ls],mx[rs]);
tr[o]=tr[ls]+tr[rs];
}
void build(R int o,R int l,R int r)
{
if(l==r)
{
tr[o]=val[l];
mx[o]=l;
return;
}
R int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
}
void change(R int o,R int l,R int r,R int pos,R int del)
{
if(l==r){tr[o]=val[l];return;}
R int mid=(l+r)>>1;
if(pos<=mid)change(ls,l,mid,pos,del);
else change(rs,mid+1,r,pos,del);
up(o);
}
int query(R int o,R int l,R int r,R int x,R int y)
{
if(x<=l and y>=r)return tr[o];
R int mid=(l+r)>>1,res=0;
if(x<=mid)res+=query(ls,l,mid,x,y);
if(y>mid)res+=query(rs,mid+1,r,x,y);
return res;
}
int query_max(R int o,R int l,R int r,R int x,R int y)
{
if(l==x and y==r) return mx[o];
R int mid=(l+r)>>1;
if(y<=mid) return query_max(ls,l,mid,x,y);
else if(x>mid)return query_max(rs,mid+1,r,x,y);
else return idmax(query_max(ls,l,mid,x,mid),query_max(rs,mid+1,r,mid+1,y));
}
signed main()
{
in(n);in(m);
for(R int i=1;i<=n;i++)in(val[i]);
build(1,1,n);
for(R int l,r,k,opt;m;m--)
{
in(opt);
switch(opt)
{
case 1:in(l),in(r),printf("%lld
",query(1,1,n,l,r));break;
case 2:break;
case 3:in(l),in(r);val[l]=r;change(1,1,n,l,r);break;
}
if(opt==2)
{
in(l),in(r),in(k);
for(R int pos;;)
{
pos=query_max(1,1,n,l,r);
if(val[pos]<k)break;
val[pos]%=k;
change(1,1,n,pos,val[pos]);
}
}
}
}