Codeforces Round #250 D

Codeforces Round #250 D"/>

Codeforces Round #250 D

题目大意

• 有三种操作:求和，区间取模，单点修改
• n,m<=105,a[i]<=109 $n,m<=10^5,a[i]<=10^9$

官方题解

vfk大大的题目
简单来说就是解释了一下取模操作的复杂度可以不超过 nlog(n) $nlog(n)$
然而我不停地TTTTTTTT,好像的确比别人慢很多QAQAQ….
UPD:重写过了啦啦啦~

constmaxn=700000;
varw:array[0..4*maxn,1..2]of int64;i,j,k:longint;n,m:longint;a,b,c,d:longint;
procedure build(a,l,r:longint);
var mid:longint;
beginif l=r then begin read(w[a,1]); w[a,2]:=w[a,1]; exit; end;mid:=(l+r)>>1;build(a*2,l,mid); build(a*2+1,mid+1,r);w[a,1]:=w[a*2,1]+w[a*2+1,1];if w[a*2,2]>w[a*2+1,2]then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
end;function query(a,x,y,l,r:longint):int64;
var mid:longint;
beginif (x=l)and(y=r)then exit(w[a,1]);mid:=(x+y)>>1;if r<=mid then exit(query(a*2,x,mid,l,r)) else if l>mid then exit(query(a*2+1,mid+1,y,l,r))else exit(query(a*2,x,mid,l,mid)+query(a*2+1,mid+1,y,mid+1,r));
end;procedure update1(a,x,y,l,r,mmod:longint);
var mid:longint;
beginif w[a,2]<mmod then exit;if x=y then begin w[a,1]:=w[a,1] mod mmod; w[a,2]:=w[a,1]; exit; end;mid:=(x+y)>>1;if r<=mid then update1(a*2,x,mid,l,r,mmod) else if l>mid then update1(a*2+1,mid+1,y,l,r,mmod)else begin update1(a*2,x,mid,l,mid,mmod); update1(a*2+1,mid+1,y,mid+1,r,mmod); end;w[a,1]:=w[a*2,1]+w[a*2+1,1];if w[a*2,2]>w[a*2+1,2]then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
end;procedure update2(a,x,y,b,c:longint);
var mid:longint;
beginif x=y then begin w[a,1]:=c; w[a,2]:=c; exit; end;mid:=(x+y)>>1;if b<=mid then update2(a*2,x,mid,b,c)else update2(a*2+1,mid+1,y,b,c);w[a,1]:=w[a*2,1]+w[a*2+1,1];if w[a*2,2]>w[a*2+1,2]then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
end;beginreadln(n,m);build(1,1,n);for i:=1 to m dobeginread(a);case a of1:begin readln(b,c); writeln(query(1,1,n,b,c)); end;2:begin readln(b,c,d); update1(1,1,n,b,c,d); end;3:begin readln(b,c); update2(1,1,n,b,c); end;end;end;
end.