Codeforces Round #250 (Div. 1) D. The Child and Sequence
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 19
线段树,至于区间取模,非常明显这个数会越来越小或者不变,所以我们记录下每一个区间的最大值,假设对于模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; }
相关文章
- FB面经 Prepare: K closest point to the origin
- .NET Core SDK在Windows系统安装后出现Failed to load the hostfxr.dll等问题的解决方法
- Azure 删除VHD时报错:There is currently a lease on the blob and no lease ID was specified in the request
- What is the difference between POST and GET?
- What is the difference between application server and web server?
- What are the benefits of using Dependency Injection and IoC Containers?
- Package is not found in the following primary source
- The Five Qualities You Need in a Partner
- What does the dot after dollar sign mean in jQuery when declaring variables?
- The revocation function was unable to check revocation for the certificate
- What is the difference between task and thread?
- hdu 3006 The Number of set(思维+壮压DP)
- BZOJ3941 : [Usaco2015 Feb]Fencing the Herd
- Google Earth Engine(GEE)——The bands of the specified image contains different projections
- Git 拉取项目小技巧之切换分支error: The following untracked working tree files would be overwritten by checkout:
- I Show - Travel Language - Ask the way Teacher:Lamb
- HBase-TDG ClientAPI The Basics
- the mail of you!
- How to Change the default kernel (boot from old kernel) in CentOS/RHEL 8
- The last access date is not changed even after reading the file on Windows 7
- HDU 4126 Genghis Khan the Conqueror (树形DP+MST)
- CodeForces 288C Polo the Penguin and XOR operation (位运算,异或)
- CodeForces 288A Polo the Penguin and Strings (水题)
- 【解决方案】ERROR: lib/bridge_generated.dart:837:9: Error: The parameter ‘ptr‘ of the method ‘FlutterRustB
- Tomcat 8 Invalid character found in the request target. The valid characters are defined in RFC 3986
- There is no type initializer in Swift----One answer is to use static, it is the same as class final.
- 异常:The last packet sent successfully to the server was 0 milliseconds ago解决
- C# linq to entity中字段转化为指定类型 lambda 字段类型转换 解决"LINQ to Entities does not recognize the method 'System.String ToString(Int32)' method, and this method cannot be translated into a store expression."
- 【USACO 3.3】Riding The Fences(欧拉路径)
- 【安卓-疑难杂症】:你的主机中的软件中止了一个已建立的连接 and The application could not be installed: INSTALL_FAILED_USER_RESTRI
- Eclipse中使用MySql遇到:Loading class `com.mysql.jdbc.Driver'. This is deprecated. The new driver class is `com.mysql.cj.jdbc.Driver'. The driver is automatically registered via the SPI and manual loading o
- 1055 The World's Richest