Codeforces Round #250 (Div. 1) D. The Child and Sequence 线段树 区间取摸

D. The Child and Sequence

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/438/problem/D

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 m operations. An operation can be one of the following:

  1. Print operation l, r. Picks should write down the value of Codeforces Round #250 (Div. 1) D. The Child and Sequence 线段树 区间取摸.
  2. Modulo operation l, r, x. Picks should perform assignment a[i] = a[imod 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 ≤ 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 Codeforces Round #250 (Div. 1) D. The Child and Sequence 线段树 区间取摸.

  • 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.

Sample 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

Sample Output

8
5

HINT

题意

给你n个数,三个操作

1.输出[l,r]的和

2.将[l,r]中的数,对v取摸

3.把a[x]变成v

题解:

线段树

区间定值和区间和很简单

区间取摸的话,需要维护一个区间最大值,如果这个区间的最大值小于要取摸的数,那么就直接break就好了

代码

#include<iostream>
#include<stdio.h>
using namespace std;
#define maxn 100005
struct node
{
int l,r;
long long mx,sum;
}a[maxn*];
int d[maxn];
void build(int x,int l,int r)
{
a[x].l = l,a[x].r = r;
if(l==r)
{
a[x].mx = a[x].sum = d[l];
return;
}
int mid = (l+r)/;
build(x<<,l,mid);
build(x<<|,mid+,r);
a[x].mx = max(a[x<<].mx , a[x<<|].mx);
a[x].sum = a[x<<|].sum + a[x<<].sum;
}
void change(int x,int pos,long long val)
{
int l = a[x].l,r = a[x].r;
if(l==r)
{
a[x].mx = a[x].sum = val;
return;
}
int mid = (l+r)/;
if(pos<=mid)
change(x<<,pos,val);
else
change(x<<|,pos,val);
a[x].mx = max(a[x<<].mx,a[x<<|].mx);
a[x].sum = a[x<<].sum + a[x<<|].sum;
}
void mod(int x,int l,int r,long long val)
{
int L = a[x].l,R = a[x].r;
if(a[x].mx<val)return;
if(L==R)
{
a[x].sum%=val;
a[x].mx%=val;
return;
}
int mid = (L+R)/;
if(r<=mid)
mod(x<<,l,r,val);
else if(l>mid)
mod(x<<|,l,r,val);
else mod(x<<,l,mid,val),mod(x<<|,mid+,r,val);
a[x].sum = a[x<<].sum + a[x<<|].sum;
a[x].mx = max(a[x<<].mx,a[x<<|].mx);
}
long long get(int x,int l,int r)
{
int L = a[x].l,R = a[x].r;
if(L>=l&&R<=r)
{
return a[x].sum;
}
int mid = (L+R)/;
long long sum1 = ,sum2 = ;
if(r<=mid)
sum1 = get(x<<,l,r);
else if(l>mid)
sum2 = get(x<<|,l,r);
else sum1 = get(x<<,l,mid),sum2 = get(x<<|,mid+,r);
return sum1 + sum2;
}
int main()
{
int n,q;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
scanf("%d",&d[i]);
build(,,n);
while(q--)
{
int op;
scanf("%d",&op);
if(op==)
{
int x,y;scanf("%d%d",&x,&y);
printf("%lld\n",get(,x,y));
}
if(op==)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
mod(,x,y,z);
}
if(op==)
{
int x,y;scanf("%d%d",&x,&y);
change(,x,y);
}
}
}
上一篇:有空可以对C#尝一下鲜,WCF看上去很诱人(跨进程、跨机器、跨子网,跨企业网乃至跨Internet的分布式服务)


下一篇:Codeforces Round #332 (Div. 2) C. Day at the Beach 线段树