codeforces CF438D The Child and Sequence 线段树

D. The Child and Sequence

time limit per test: 4 seconds memory limit per test: 256 megabytes input: standard input output: 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:
　
$ 1. $ Print operation $ l, r $ . Picks should write down the value of $ sum_{i=l}^r a[i] $ .
$ 2. $ Modulo operation $ l, r, x $ . Picks should perform assignment $ a[i] = a[i] quad mod quad x $ for each $ i (l ≤ i ≤ 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 operations?
　

Input

The first line of input contains two integer: $ n, m (1 ≤ n, m ≤ 10^5) $ .
The second line contains n integers, separated by space: $ a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^9) $ — initial value of array elements.
　
Each of the next $ m $ lines begins with a number $ type (type in (1,2,3) ) $ .
　

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 ≤ 10^9) $ , which correspond the operation 2.
If $ type = 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.
　

Examples

input1

output1

 8
 5

input2

 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

output2

Note

Consider the first testcase:
　

At first, $ a = (1, 2, 3, 4, 5) $ .
After operation 1, $ a = (1, 2, 3, 0, 1) $ .
After operation 2, $ a = (1, 2, 5, 0, 1) $ .
At operation 3, $ 2 + 5 + 0 + 1 = 8 $ .
After operation 4, $ a = (1, 2, 2, 0, 1) $ .
At operation 5, $ 1 + 2 + 2 = 5 $ .

题目大意

给出一个序列，进行如下三种操作：
区间求和
区间每个数膜模 $ x $
单点修改
$ n,m le 100000 $

思路

如果没有第二个操作的话，就是一棵简单的线段树。那么如何处理这个第二个操作呢？
对于一个数 $ a $ ，如果模数 $ x>a $ ，则这次取模是没有意义的，直接跳过；
如果 $ x>a/2 $ 则取模结果小于 $ a/2 $ ；如果 $ x<a/2 $ ，取模结果小于 $ x $，则也小于 $ a/2 $
所以对于一个数，最多只会做 $ log_a $ 次取模操作。这是可以接受的！
对于一个区间，维护最大值，如果模数 $ x> $ 最大值，直接跳过即可。否则继续往下像单点修改一样。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
#define N 100005
int n,m,sum[N<<2],smx[N<<2];
void build(int o,int l,int r){
	if(l==r){
		scanf("%lld",&sum[o]);
		smx[o]=sum[o];
		return;
	}
	int mid=l+r>>1;
	build(o<<1,l,mid); build(o<<1|1,mid+1,r);
	sum[o]=sum[o<<1]+sum[o<<1|1];
	smx[o]=max(smx[o<<1],smx[o<<1|1]);
}
void updata(int o,int l,int r,int pos,int val){
	if(l==r){
		sum[o]=smx[o]=val;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid) updata(o<<1,l,mid,pos,val);
	else updata(o<<1|1,mid+1,r,pos,val);
	sum[o]=sum[o<<1]+sum[o<<1|1];
	smx[o]=max(smx[o<<1],smx[o<<1|1]);
}
void modtify(int o,int l,int r,int L,int R,int k){
	if(smx[o]<k) return;
	if(l==r){
		sum[o]%=k;
		smx[o]=sum[o];
		return;
	}
	int mid=l+r>>1;
	if(L>mid) modtify(o<<1|1,mid+1,r,L,R,k);
	else if(R<=mid) modtify(o<<1,l,mid,L,R,k);
	else{
		modtify(o<<1,l,mid,L,R,k);
		modtify(o<<1|1,mid+1,r,L,R,k);
	}
	sum[o]=sum[o<<1]+sum[o<<1|1];
	smx[o]=max(smx[o<<1],smx[o<<1|1]);
}
int query(int o,int l,int r,int L,int R){
	if(L<=l&&r<=R) return sum[o];
	int mid=l+r>>1;
	if(L>mid) return query(o<<1|1,mid+1,r,L,R);
	else if(R<=mid) return query(o<<1,l,mid,L,R);
	else return query(o<<1,l,mid,L,R)+query(o<<1|1,mid+1,r,L,R);
}
signed main(){
	scanf("%lld %lld",&n,&m);
	build(1,1,n);
	while(m--){
		int opt,x,y;
		scanf("%lld %lld %lld",&opt,&x,&y);
		if(opt==1) printf("%lld
",query(1,1,n,x,y));
		else if(opt==2){
			int k;
			scanf("%lld",&k);
			modtify(1,1,n,x,y,k);
		} else updata(1,1,n,x,y);
	}
	return 0;
}
/*
#         42611024
When      2018-09-07 14:02:33 
Who       PotremZ
Problem   D - The Child and Sequence
Lang      GNU C++11
Verdict   Accepted
Time      826 ms
Memory    6300 KB
*/