codeforces CF438D The Child and Sequence 線段樹

$ \Rightarrow $ 戳我進CF原題

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

 5 51 2 3 4 52 3 5 43 3 51 2 52 1 3 31 1 3

output1

 85

---

input2

 10 106 9 6 7 6 1 10 10 9 51 3 92 7 10 92 5 10 81 4 73 3 72 7 9 91 2 41 6 61 5 93 1 10

output2

 49152319

　

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\n",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
*/