結果
| 問題 | No.1234 典型RMQ |
| ユーザー |
 fgwiebfaoish
|
| 提出日時 | 2020-09-18 23:03:44 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 595 ms / 2,000 ms |
| コード長 | 7,829 bytes |
| コンパイル時間 | 1,582 ms |
| コンパイル使用メモリ | 110,080 KB |
| 実行使用メモリ | 48,256 KB |
| 最終ジャッジ日時 | 2024-11-09 02:01:33 |
| 合計ジャッジ時間 | 13,829 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Collections;using System.Collections.Specialized;using System.Linq;using System.Text;using System.IO;using System.Reflection;using static System.Math;using System.Numerics;using System.Threading;//using nint=System.Int32;static class Program{const int mod=(int)1e9+7;const double eps=1e-11;static void Main(){Sc sc=new Sc();var n=sc.I;var a=sc.La2;var avl=new Avl2(false);avl.Ud(0,n,0);for(int i = 1;i<=n;i++) {avl.Ud(i,i,a[i]);}var q=sc.I;StringBuilder sb=new StringBuilder();for(int i = 0;i<q;i++) {var e=sc.Ia;if(e[0]==1){avl.Ud(e[1],e[2],e[3]);}else{sb.Append(avl.Get(e[1],e[2]).Item2+"\n");}}Console.Write(sb);}}public class Avl2{public class Nd{public int h=1,c=1;public int nl,nr,dnl;public long d,dd=0;public Nd l,r;public bool lf;public Nd(int nl,int nr,long d,Nd du){this.nl=dnl=nl;this.nr=nr;this.d=d;l=du;r=du;lf=true;}public Nd(int nl,int nr,Nd l,Nd r){this.nl=nl;this.nr=nr;this.l=l;this.r=r;compare(this);h=Max(l.h,r.h)+1;lf=false;}}public Nd root,du;public int cnt=0;private static Action<Nd> compare;private static Func<long,long,bool> compare2;public Avl2(bool bo){if(bo){compare=CoMax;compare2=CoMax2;}else{compare=CoMin;compare2=CoMin2;}du=new Nd(int.MinValue,int.MaxValue,bo?long.MinValue:long.MaxValue,du);du.h=0;du.c=0;root=du;}private void CoMax(Nd nd){if(nd.l.d+nd.l.dd>nd.r.d+nd.r.dd){nd.d=nd.l.d+nd.l.dd;nd.dnl=nd.l.dnl;}else{nd.d=nd.r.d+nd.r.dd;nd.dnl=nd.r.dnl;}}private void CoMin(Nd nd){if(nd.l.d+nd.l.dd<nd.r.d+nd.r.dd){nd.d=nd.l.d+nd.l.dd;nd.dnl=nd.l.dnl;}else{nd.d=nd.r.d+nd.r.dd;nd.dnl=nd.r.dnl;}}private bool CoMax2(long a,long b){return a>=b;}private bool CoMin2(long a,long b){return a<=b;}public void Ud(int a,int b,long d){if(a>b){(a,b)=(b,a);}if(root!=du){root=Fu(root,a,b,d);if(Abs(root.l.h-root.r.h)>1){root=Rotate(root);}}else{root=new Nd(a,b,d,du);}}private Nd Fu(Nd t,int nl,int nr,long d){Fdd(t);if(!t.lf){if(t.nl==nl&&t.nr==nr){t.d+=d;t.l.dd+=d;t.r.dd+=d;return t;}if(t.l.nr>=nl){t.l=Fu(t.l,nl,Min(t.l.nr,nr),d);}if(t.l.nr<nr){t.r=Fu(t.r,Max(t.l.nr+1,nl),nr,d);}if(Abs(t.l.l.h-t.l.r.h)>1){t.l=Rotate(t.l);}if(Abs(t.r.l.h-t.r.r.h)>1){t.r=Rotate(t.r);}compare(t);t.nl=t.l.nl;t.nr=t.r.nr;t.h=Max(t.l.h,t.r.h)+1;}else{if(t.nr<nl){return new Nd(t.nl,nr,t,new Nd(nl,nr,d,du));}else if(t.nl>nr){return new Nd(nl,t.nr,new Nd(nl,nr,d,du),t);}else if(t.nl<nl){if(t.nr<nr){Nd e=new Nd(t.nl,nr,t,new Nd(nl,nr,new Nd(nl,t.nr,t.d+d,du),new Nd(t.nr+1,nr,d,du)));t.nr=nl-1;return e;}else if(t.nr>nr){Nd e=new Nd(t.nl,t.nr,t,new Nd(nl,t.nr,new Nd(nl,nr,t.d+d,du),new Nd(nr+1,t.nr,t.d,du)));t.nr=nl-1;return e;}else{t.nr=nl-1;return new Nd(t.nl,nr,t,new Nd(nl,nr,t.d+d,du));}}else if(t.nl>nl){if(t.nr<nr){Nd e=new Nd(nl,nr,new Nd(nl,t.nl-1,d,du),new Nd(t.nl,nr,t,new Nd(t.nr+1,nr,d,du)));t.d+=d;return e;}else if(t.nr>nr){Nd e=new Nd(nl,t.nr,new Nd(nl,t.nl-1,d,du),new Nd(t.nl,t.nr,new Nd(t.nl,nr,t.d+d,du),t));t.nl=nr+1;return e;}else{t.d+=d;return new Nd(nl,nr,new Nd(nl,t.nl-1,d,du),t);}}else{if(t.nr<nr){t.d+=d;return new Nd(nl,nr,t,new Nd(t.nr+1,nr,d,du));}else if(t.nr>nr){t.nl=nr+1;return new Nd(nl,t.nr,new Nd(nl,nr,t.d+d,du),t);}else{t.d+=d;return t;}}}return t;}public ValueTuple<int,long> Get(int a,int b){return Fdg(root,a,b);}private ValueTuple<int,long> Fdg(Nd t,int nl,int nr){Fdd(t);if(t.lf){return ValueTuple.Create(t.dnl,t.d);}if(nl<=t.nl&&nr>=t.nr){return ValueTuple.Create(t.dnl,t.d);}var d=ValueTuple.Create(du.dnl,du.d);if(t.l.nr>=nl){d=Fdg(t.l,nl,nr);}if(t.r.nl<=nr){var e=Fdg(t.r,nl,nr);d=compare2(d.Item2,e.Item2)?d:e;}return d;}private void Fdd(Nd t){if(t.dd!=0){t.d+=t.dd;t.l.dd+=t.dd;t.r.dd+=t.dd;t.dd=0;}}private Nd Rotate(Nd t){Nd nd=du;Fdd(t);if(t.l.h>t.r.h){Fdd(t.l);if(t.l.l.h>t.l.r.h){nd=t.l;t.l=t.l.r;nd.r=t;Ft(t);}else{Fdd(t.l.r);nd=t.l.r;t.l.r=nd.l;nd.l=t.l;Ft(t.l);t.l=nd.r;nd.r=t;Ft(t);}}else{Fdd(t.r);if(t.r.l.h>t.r.r.h){Fdd(t.r.l);nd=t.r.l;t.r.l=nd.r;nd.r=t.r;Ft(t.r);t.r=nd.l;nd.l=t;Ft(t);}else{nd=t.r;t.r=t.r.l;nd.l=t;Ft(t);}}Ft(nd);return nd;}public ValueTuple<int,long> Gl(int a,int b,long d){Fdd(root);return compare2(root.d,d)?Fgl(root,a,b,d):ValueTuple.Create(du.nr,-1L);}private ValueTuple<int,long> Fgl(Nd t,int a,int b,long d){if(t.lf){return ValueTuple.Create(t.nl,t.d);}Fdd(t.l);if(a<=t.l.nr&&t.l.nl<=b&&compare2(t.l.d,d)){var z=Fgl(t.l,a,b,d);if(z.Item1!=du.nr){return z;}}Fdd(t.r);if(a<=t.r.nr&&t.r.nl<=b&&compare2(t.r.d,d)){return Fgl(t.r,a,b,d);}return ValueTuple.Create(du.nr,-1L);}public ValueTuple<int,long> Gr(int a,int b,long d){Fdd(root);return compare2(root.d,d)?Fgr(root,a,b,d):ValueTuple.Create(du.nl,-1L);}private ValueTuple<int,long> Fgr(Nd t,int a,int b,long d){if(t.lf){return ValueTuple.Create(t.nr,t.d);}Fdd(t.r);if(a<=t.r.nr&&t.r.nl<=b&&compare2(t.r.d,d)){var z=Fgr(t.r,a,b,d);if(z.Item1!=du.nl){return z;}}Fdd(t.l);if(a<=t.l.nr&&t.l.nl<=b&&compare2(t.l.d,d)){return Fgr(t.l,a,b,d);}return ValueTuple.Create(du.nl,-1L);}private void Ft(Nd t){if(!t.lf){t.h=Max(t.l.h,t.r.h)+1;t.c=t.l.c+t.r.c;compare(t);t.nl=t.l.nl;t.nr=t.r.nr;}}}public class Sc{public int I{get{return int.Parse(Console.ReadLine());}}public long L{get{return long.Parse(Console.ReadLine());}}public double D{get{return double.Parse(Console.ReadLine());}}public string S{get{return Console.ReadLine();}}public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}public string[] Sa{get{return Console.ReadLine().Split();}}public object[] Oa{get{return Console.ReadLine().Split();}}public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}public int[] Ia3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),int.Parse);}public int[] Ia3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),int.Parse);}public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}public long[] La3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),long.Parse);}public long[] La3(int a){return Array.ConvertAll((Console.ReadLine()+" "+a.ToString()).Split(),long.Parse);}public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}public double[] Da3(string a,string b){return Array.ConvertAll((a+Console.ReadLine()+b).Split(),double.Parse);}public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}}