題干：

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?moperations. 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,?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.

Output

For each operation 1, please print a line containing the answer. Notice that the answer may exceed the 32-bit integer.

Examples

Input

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

Output

8 5

Input

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

Output

49 15 23 1 9

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.

題目大意：

給一個序列
支持3種操作
1 u v 對于所有i u<=i<=v，輸出a[i]的和
2 u v t 對于所有i u<=i<=v a[i]=a[i]%t
3 u v 表示a[u]=v（將v賦值給a[u]）
n,q<=1e5 a[i],t,v<=1e9

解題報告：

? ? 這題需要維護最大值的，不能直接判斷是否sum=0了就返回。因為我操作可能給的模數(shù)很大，如果我給1e5次這個大模數(shù)操作，那就n^2logn了，肯定炸，但是用判斷最大值的的方法就可以取消一大部分操作使復(fù)雜度降回來。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; struct TREE {int l,r;ll sum;ll maxx; } tree[MAX<<2]; ll a[MAX]; int n,m; void pushup(int cur) {tree[cur].sum = tree[cur*2].sum + tree[cur*2+1].sum;tree[cur].maxx = max(tree[cur*2].maxx,tree[cur*2+1].maxx); } void build(int l,int r,int cur) {tree[cur].l = l,tree[cur].r = r;if(l == r) {tree[cur].sum = tree[cur].maxx = a[r];return ;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } void update(int pl,int pr,ll val,int cur) {if(tree[cur].maxx < val) return ;if(tree[cur].l == tree[cur].r) {tree[cur].sum %=val;tree[cur].maxx %= val;return ;}if(pl <= tree[cur*2].r) update(pl,pr,val,cur*2);if(pr >= tree[cur*2+1].l) update(pl,pr,val,cur*2+1);pushup(cur); } void update2(int tar,ll val,int cur) {if(tree[cur].l == tree[cur].r) {tree[cur].sum = tree[cur].maxx = val;return ;}if(tar <= tree[cur*2].r) update2(tar,val,cur*2);if(tar >= tree[cur*2+1].l) update2(tar,val,cur*2+1);pushup(cur); } ll qSum(int pl,int pr,int cur) {if(pl <= tree[cur].l && pr >= tree[cur].r) return tree[cur].sum;ll res = 0;if(pl <= tree[cur*2].r) res += qSum(pl,pr,cur*2);if(pr >= tree[cur*2+1].l) res += qSum(pl,pr,cur*2+1); return res; } int main() {cin>>n>>m;for(int i = 1; i<=n; i++) cin>>a[i];build(1,n,1);while(m--) {int op,u,v;ll t;scanf("%d",&op);if(op == 1) {scanf("%d%d",&u,&v);printf("%lld\n",qSum(u,v,1));}if(op == 2) {scanf("%d%d%lld",&u,&v,&t);if(u>v) swap(u,v);update(u,v,t,1);}if(op == 3) {scanf("%d%lld",&u,&t);update2(u,t,1);}}return 0 ; } /* 16:25 - 16:38 */

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 438D】The Child and Sequence（线段树区间取模操作）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。