4 seconds
256 megabytes
standard input
standard output
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:
- 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?
The first line of input contains two integer: n, m (1 ≤ n, m ≤ 105).
The second line contains n integers, separated by space:a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) —
initial value of array elements.
Each of the next m lines begins with a number type 
.
- If type = 1, there will be two integers more in the line: l, r (1 ≤ l ≤ r ≤ n),
which correspond the operation 1. - If type = 2, there will be three integers more in the line: l, r, x (1 ≤ l ≤ r ≤ n; 1 ≤ x ≤ 109),
which correspond the operation 2. - If type = 3, there will be two integers more in the line: k, x (1 ≤ k ≤ n; 1 ≤ x ≤ 109),
which correspond the operation 3.
For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.
5 5
1 2 3 4 5
2 3 5 4
3 3 5
1 2 5
2 1 3 3
1 1 3
8
5
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
49
15
23
1 9 线段树，至于区间取模，非常明显这个数会越来越小或者不变，所以我们记录下每一个区间的最大值，假设对于模mod操作发现某个区间的最大值比mod小，显然这个区间就不是必需进行操作了。#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; typedef long long ll;
#define rep(i,s,t) for(int i=s;i<t;i++)
#define red(i,s,t) for(int i=s-1;i>=t;i--)
#define max(a,b) (a>b? a:b)
#define clr(a,v) memset(a,v,sizeof a)
#define L t<<1
#define R t<<1|1 inline int input(){
int ret=0;bool isN=0;char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') isN=1;
c=getchar();
}
while(c>='0' && c<='9'){
ret=ret*10+c-'0';c=getchar();
}
return isN? -ret:ret;
} inline void output(ll x){
if(x<0){
putchar('-');x=-x;
}
int len=0,data[20];
while(x){
data[len++]=x%10;x/=10;
}
if(!len) data[len++]=0;
while(len--)
putchar(data[len]+48);
putchar('\n');
} const int N=100005;
ll root[N<<2];
int Max[N<<2];
int n,m,a[N],op,x,y,z; inline void push_up(int t){
root[t]=root[L]+root[R];
Max[t]=max(Max[L],Max[R]);
} inline void build(int t,int x,int y){
if(x==y) root[t]=Max[t]=a[x];
else{
int mid=(x+y)>>1;
build(L,x,mid),build(R,mid+1,y);
push_up(t);
}
} inline void setVal(int t,int l,int r,int x,int v){
if(l==r){
root[t]=Max[t]=v;
}
else{
int mid=(l+r)>>1;
if(x<=mid) setVal(L,l,mid,x,v);
else setVal(R,mid+1,r,x,v);
push_up(t);
}
} inline void modefiyMod(int t,int l,int r,int x,int y,int mod){
if(Max[t]<mod) return;
if(l==r){
root[t]=Max[t]=root[t]%mod;return;
}
else{
int mid=(l+r)>>1;
if(y<=mid) modefiyMod(L,l,mid,x,y,mod);
else if(x>mid) modefiyMod(R,mid+1,r,x,y,mod);
else{
modefiyMod(L,l,mid,x,mid,mod);
modefiyMod(R,mid+1,r,mid+1,y,mod);
}
push_up(t);
}
} inline ll query(int t,int l,int r,int x,int y){
if(l>=x && r<=y) return root[t];
int mid=(l+r)>>1;
if(y<=mid) return query(L,l,mid,x,y);
else if(x>mid) return query(R,mid+1,r,x,y);
else return query(L,l,mid,x,mid)+query(R,mid+1,r,mid+1,y);
} int main(){
n=input(),m=input();
rep(i,1,n+1) a[i]=input();
build(1,1,n);
rep(i,0,m){
op=input();
if(op==1){
x=input(),y=input();
output(query(1,1,n,x,y));
}
else if(op==2){
x=input(),y=input(),z=input();
modefiyMod(1,1,n,x,y,z);
}
else{
x=input(),y=input();
setVal(1,1,n,x,y);
}
}
return 0;
}