結果
| 問題 | No.1234 典型RMQ |
| ユーザー |
 TAKA 00
|
| 提出日時 | 2022-12-09 14:58:10 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
AC
|
| 実行時間 | 591 ms / 2,000 ms |
| コード長 | 40,643 bytes |
| コンパイル時間 | 9,429 ms |
| コンパイル使用メモリ | 166,928 KB |
| 実行使用メモリ | 193,192 KB |
| 最終ジャッジ日時 | 2024-10-14 18:43:48 |
| 合計ジャッジ時間 | 22,241 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 50 ms
29,808 KB |
| testcase_01 | AC | 49 ms
29,952 KB |
| testcase_02 | AC | 50 ms
29,952 KB |
| testcase_03 | AC | 48 ms
30,072 KB |
| testcase_04 | AC | 51 ms
29,824 KB |
| testcase_05 | AC | 57 ms
30,208 KB |
| testcase_06 | AC | 559 ms
75,904 KB |
| testcase_07 | AC | 439 ms
60,416 KB |
| testcase_08 | AC | 571 ms
80,348 KB |
| testcase_09 | AC | 513 ms
69,240 KB |
| testcase_10 | AC | 578 ms
77,560 KB |
| testcase_11 | AC | 562 ms
75,520 KB |
| testcase_12 | AC | 518 ms
67,200 KB |
| testcase_13 | AC | 429 ms
60,160 KB |
| testcase_14 | AC | 538 ms
67,584 KB |
| testcase_15 | AC | 495 ms
66,176 KB |
| testcase_16 | AC | 591 ms
77,568 KB |
| testcase_17 | AC | 523 ms
67,584 KB |
| testcase_18 | AC | 380 ms
57,728 KB |
| testcase_19 | AC | 577 ms
78,080 KB |
| testcase_20 | AC | 372 ms
75,392 KB |
| testcase_21 | AC | 554 ms
75,904 KB |
| testcase_22 | AC | 414 ms
80,768 KB |
| testcase_23 | AC | 418 ms
80,768 KB |
| testcase_24 | AC | 411 ms
80,896 KB |
| testcase_25 | AC | 407 ms
80,896 KB |
| testcase_26 | AC | 419 ms
80,896 KB |
| testcase_27 | AC | 51 ms
30,080 KB |
| testcase_28 | AC | 54 ms
30,080 KB |
| testcase_29 | AC | 52 ms
193,192 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (85 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) /home/judge/data/code/Main.cs(101,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(168,20): warning CS8981: 型名 'mod' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(192,20): warning CS8981: 型名 'toolbox' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1118,27): warning CS0162: 到達できないコードが検出されました [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(1128,17): warning CS0219: 変数 'k' は割り当てられていますが、その値は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(45,20): warning CS0169: フィールド 'Program.DFS' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(50,19): warning CS0169: フィールド 'Program.FF' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(48,21): warning CS0169: フィールド 'Program.SPFA' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(49,24): warning CS0169: フィールド 'Program.Kruskal' は使用されていません [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(51,20):
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
namespace test
{
internal class Program
{
static void Main(string[] args)
{
cin = new input();
mod = new mod(1000000007);
toolbox = new toolbox();
Priority_Queue = new Priority_Queue(false);
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
int n = cin.intreed();
var a = cin.arraylong(n).ToList();
int q = cin.intreed();
RMQ = new RMQ(n, a);
for(int i=0; i<q; i++)
{
if(cin.intreed()==1)
{
RMQ.update(cin.intreed(), cin.intreed() + 1, cin.intreed());
}
else
{
Console.WriteLine(RMQ.get(cin.intreed(),cin.intreed()+1));
cin.intreed();
}
}
Console.Out.Flush();
}
static input cin;
static mod mod;
static toolbox toolbox;
static UnionFind UnionFind;
static BFS BFS;
static DFS DFS;
static Priority_Queue Priority_Queue;
static Warshall_Floyd Warshall_Floyd;
static SPFA SPFA;
static Kruskal Kruskal;
static FF FF;
static TSP TSP;
static RMQ RMQ;
}
public static class Extensions
{
public static Dictionary<T, int> safe_addtion_for_dictionary_int<T>(this Dictionary<T, int> dic, T key)
{
if (dic.ContainsKey(key))
dic[key]++;
else
dic.Add(key, 1);
return dic;
}
public static Dictionary<T, List<T2>> safe_addtion_for_list_in_dictionary<T, T2>(this Dictionary<T, List<T2>> dic, T key, T2 value)
{
if (dic.ContainsKey(key))
dic[key].Add(value);
else
dic.Add(key, new List<T2>() { value });
return dic;
}
public static T list_pop_back<T>(this List<T> a)
{
var k = a[a.Count - 1];
a.RemoveAt(a.Count - 1);
return k;
}
public static T chmin<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) > 0)
return a = b;
else
return a;
}
public static T chmax<T>(ref this T a, T b)
where T : struct, IComparable
{
if (a.CompareTo(b) < 0)
return a = b;
else
return a;
}
}
internal class input
{
string[] soloinput;
int t;
public input()
{
soloinput = new string[0];
t = 0;
}
public string soloreed()
{
if (t < soloinput.Length)
{
return soloinput[t++];
}
string input = Console.ReadLine();
while (input == "")
{
input = Console.ReadLine();
}
soloinput = input.Split(" ");
t = 0;
return soloinput[t++];
}
public int intreed()
{
return int.Parse(soloreed());
}
public int[] arrayint(int N)
{
int[] A = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = intreed();
}
return A;
}
public long longreed()
{
return long.Parse(soloreed());
}
public long[] arraylong(long N)
{
long[] A = new long[N];
for (long i = 0; i < N; i++)
{
A[i] = longreed();
}
return A;
}
public decimal decimalreed()
{
return decimal.Parse(soloreed());
}
public decimal[] arraydecimal(long N)
{
decimal[] A = new decimal[N];
for (decimal i = 0; i < N; i++)
{
A[(long)i] = decimalreed();
}
return A;
}
}
internal class mod
{
public long T { get; set; }
public mod(long mod = 1000000007)
{
T = mod;
}
public long addition(long A, long B)
{
decimal C = A + B;
return (long)C % T;
}
public long subtraction(long A, long B)
{
decimal C = A - B;
return C % T >= 0 ? (long)C % T : (long)(C + T) % T;
}
public long multiplication(long A, long B)
{
return ((A % T) * (B % T)) % T;
}
}
internal class toolbox
{
string Y = "Yes";
string N = "No";
static input cin;
public toolbox()
{
cin = new input();
}
public long[] CumulativeSum(long[] A, bool mode = true)
{
if (mode == false) Array.Reverse(A);
long[] back = new long[A.Length + 1];
back[0] = 0;
for (int i = 1; i <= A.Length; i++)
{
back[i] = back[i - 1] + A[i - 1];
}
if (mode == false) Array.Reverse(A);
return back;
}
public long[] Eratosthenes(long A)
{
A++;
var back = new List<long>();
bool[] ch = new bool[A];
for (int i = 2; i < A; i++) ch[i] = true;
for (long i = 2; i < Math.Sqrt(A); i++)
{
if (ch[i] == true)
{
back.Add(i);
for (long t = 1; i * t < A; t++)
{
ch[i * t] = false;
}
}
}
for (long i = 0; i < A; i++)
{
if (ch[i] == true) back.Add(i);
}
return back.Distinct().ToArray();
}
public void Swap<T>(ref T a, ref T b)
{
var i = a;
a = b;
b = i;
}
public void LSwap<T>(ref List<T> A, int a, int b)
{
var i = A[a];
A[a] = A[b];
A[b] = i;
}
public long Gcd(long A, long B)
{
while (A != 0)
{
B %= A;
Swap(ref A, ref B);
}
return B;
}
public long[] AllDivisors(long N)
{
var back = new List<long>();
for (int i = 1; Math.Pow(i, 2) <= N; i++)
{
if (N % i == 0)
{
back.Add(i);
back.Add(N / i);
}
}
return back.Distinct().ToArray();
}
public static IEnumerable<T[]> ExhaustiveEnumeration<T>(IEnumerable<T> indata)
{
if (indata.Count() == 1) yield return new T[] { indata.First() };
foreach (var i in indata)
{
var used = new T[] { i };
var unused = indata.Except(used);
foreach (var t in ExhaustiveEnumeration(unused))
yield return used.Concat(t).ToArray();
}
//How to use
//var allpattern = toolbox.ExhaustiveEnumeration(Enumerable.Range(1, N));
}
public bool[,] bitallsearch(int N)
{
bool[,] back = new bool[(int)Math.Pow(2, N), N];
for (int i = 0; i < Math.Pow(2, N); i++)
{
for (int t = 0; t < N; t++)
{
var k = (i >> t) & 1;
if (k == 1)
{
back[i, t] = true;
}
}
}
return back;
}
public static int BS<T>(T[] A, T key)
where T : IComparable
{
//このコード、定数倍が大変な事になってるので標準ライブラリを使いましょう(BinarySearch)
int left = 0;
int right = A.Length;
int mid = 0;
while (left < right)
{
mid = (left + right) / 2;
if (A[mid].CompareTo(key) == 0)
return mid;
else if (A[mid].CompareTo(key) > 0)
right = mid;
else if (A[mid].CompareTo(key) < 0)
left = mid + 1;
}
return -1;
}
public static int lower_bound<T>(T[] a, T v)
{
return lower_bound(a, v, Comparer<T>.Default);
}
public static int lower_bound<T>(T[] A, T key, Comparer<T> v)
{
int left = 0;
int right = A.Length - 1;
int mid = 0;
var W = 0;
while (left <= right)
{
mid = (left + right) / 2;
W = v.Compare(A[mid], key);
if (W == -1)
left = mid + 1;
else
right = mid - 1;
}
return left;
}
public long[] prime_factorize(long N)
{
long T = N;
var back = new List<long>();
for (long i = 2; i * i <= T; i++)
{
if (T % i != 0) continue;
while (T % i == 0)
{
back.Add(i);
T /= i;
}
}
if (T != 1) back.Add(T);
return back.ToArray();
}
public long[] One_dimensional_Coordinate_Compression(long[] A)
{
long[] back = new long[A.Length];
var T = A.Distinct().ToList();
T.Sort();
for (int i = 0; i < A.Length; i++)
back[i] = T.BinarySearch(A[i]);
return back;
}
public void setYN(string A = "Yes", string B = "No")
{
Y = A;
N = B;
}
public void YN(bool ans)
{
if (ans)
Console.WriteLine(Y);
else
Console.WriteLine(N);
}
public string[] x_dekakou(int H, int W)
{
var s = new string[H + 2];
for (int i = 0; i < W + 2; i++)
{
s[0] += "x";
s[H + 1] += "x";
}
for (int i = 1; i < H + 1; i++)
{
//x場外 .白 #黒
s[i] = "x" + Console.ReadLine().Replace(" ", "") + "x";
}
return s;
}
public List<List<string>> x_dekakou_string(int H, int W)
{
var back = new List<List<string>>();
for (int i = 0; i < H + 2; i++)
back.Add(Enumerable.Repeat<string>("", W + 2).ToList());
for (int i = 0; i < W + 2; i++)
{
back[0][i] = "x";
back[H + 1][i] = "x";
}
for (int i = 1; i <= H; i++)
{
back[i][0] = "x";
back[i][W + 1] = "x";
for (int t = 1; t <= W; t++)
back[i][t] = cin.soloreed();
}
return back;
}
}
internal class UnionFind
{
public int[] tree { get; private set; }
static toolbox toolbox;
public UnionFind(int s)
{
tree = Enumerable.Repeat<int>(-1, s + 1).ToArray();
}
public int getroot(int i)
{
return tree[i] < 0 ? i : tree[i] = getroot(tree[i]);
}
public bool groupcheck(int i, int t)
{
return getroot(i) == getroot(t);
}
public bool unite(int i, int t)
{
toolbox = new toolbox();
var x = getroot(i);
var y = getroot(t);
if (x != y)
{
if (tree[x] > tree[y])
{
toolbox.Swap(ref x, ref y);
}
tree[x] += tree[y];
tree[y] = x;
}
return x != y;
}
public int get_cnt(int i)
{
return tree[getroot(i)] * -1;
}
}
internal class BFS
{
//この関数は基本的に1_indexで処理される
public int[] dist { get; set; }
public bool interactive { get; set; }
private Queue<int> que = new Queue<int>();
private List<List<int>> Graph = new List<List<int>>();
public BFS(int i, bool cnt = true)
{
Set_BFS(i, cnt);
}
public void Set_BFS(int i, bool cnt = true)
{
//(頂点数、双方向グラフであるT/F)
dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();
interactive = cnt;
for (int t = 0; t <= i; t++)
{
Graph.Add(new List<int>());
}
}
public void Connect_Graph(int i, int t)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add(t);
if (interactive)
Graph[t].Add(i);
}
public void Start_BFS(int i)
{
//(捜索を始める頂点(int))
dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();
que.Enqueue(i);
dist[i] = 0;
while (que.Count != 0)
{
var t = que.Dequeue();
for (int w = 0; w < Graph[t].Count; w++)
{
if (dist[Graph[t][w]] == -1)
{
que.Enqueue(Graph[t][w]);
dist[Graph[t][w]] = dist[t] + 1;
}
}
}
}
public void Start_BFS(List<int> i)
{
dist = Enumerable.Repeat<int>(-1, Graph.Count).ToArray();
foreach (var t in i)
{
que.Enqueue(t);
dist[t] = 0;
}
while (que.Count != 0)
{
var t = que.Dequeue();
for (int w = 0; w < Graph[t].Count; w++)
{
if (dist[Graph[t][w]] == -1)
{
que.Enqueue(Graph[t][w]);
dist[Graph[t][w]] = dist[t] + 1;
}
}
}
}
}
internal class DFS
{
//この関数は基本的に1_indexで処理される
private int[] dist;
private bool interactive = true;
private Stack<int> stc = new Stack<int>();
private List<List<int>> Graph = new List<List<int>>();
public DFS()
{
}
public void Set_DFS(int i, bool cnt = true)
{
//(頂点数、双方向グラフであるT/F)
dist = Enumerable.Repeat<int>(-1, i + 1).ToArray();
interactive = cnt;
for (int t = 0; t <= i; t++)
{
Graph.Add(new List<int>());
}
}
public void Connect_Graph(int i, int t)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add(t);
if (interactive)
Graph[t].Add(i);
}
public void Start_DFS(int i, bool cnt = false)
{
//(捜索を始める頂点(int))
stc.Push(i);
dist[i] = 0;
while (stc.Count != 0)
{
var t = stc.Pop();
for (int w = 0; w < Graph[t].Count; w++)
{
if (dist[Graph[t][w]] == -1)
{
stc.Push(Graph[t][w]);
}
}
}
}
public int Get_Cost(int i)
{
return dist[i];
}
}
internal class Dijkstra
{
static Priority_Queue Priority_Queue;
public long[] dist { get; set; }
public bool interactive { get; set; }
public int[] prev { get; set; }
/// <summary>
/// 行先,コスト
/// </summary>
public List<List<(long, long)>> Graph { get; set; }
public Dijkstra(int n, bool cnt = true)
{
Priority_Queue = new Priority_Queue(false);
dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
Graph = new List<List<(long, long)>>();
prev = Enumerable.Repeat<int>(-1, n + 1).ToArray();//前の頂点を保管する
for (int i = 0; i <= n; i++)
{
Graph.Add(new List<(long, long)>());
}
interactive = cnt;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add((t, cost));
if (interactive)
Graph[t].Add((i, cost));
}
public void Start_Dijkstra(long i)
{
dist[i] = 0;
Priority_Queue.Enqueue(0, i);
while (Priority_Queue.Queue.Count != 0)
{
var t = Priority_Queue.Dequeue();
int v = (int)t.Item2;
if (dist[v] < t.Item1)
continue;
for (int w = 0; w < Graph[v].Count; w++)
{
var e = Graph[v][w];
if (dist[(int)e.Item1] <= dist[v] + e.Item2)
continue;
else
{
dist[(int)e.Item1] = dist[v] + e.Item2;
Priority_Queue.Enqueue(dist[(int)e.Item1], e.Item1);
prev[e.Item1] = v;
}
}
}
}
public List<(int, int)> Get_tree()
{
var back = new List<(int, int)>();
for (int i = 1; i <= dist.Length - 1; i++)
{
back.Add((i, prev[i]));
}
return back;
}
}
internal class Priority_Queue
{
toolbox toolbox = new toolbox();
public List<(long, long)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Priority_Queue(bool cnt = true)
{
Queue = new List<(long, long)>();
revase = cnt;
}
public void Enqueue(long a, long b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, long) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
}
internal class Generic_Priority_Queue<T>
{
toolbox toolbox = new toolbox();
public List<(long, T)> Queue { get; private set; }
/// <summary>
/// true==>大きいやつから出るよ false==>小さいやつからでるよ
/// </summary>
public bool revase { get; set; }
public Generic_Priority_Queue(bool cnt = true)
{
Queue = new List<(long, T)>();
revase = cnt;
}
public void Enqueue(long a, T b)
{
if (revase == false)
a *= -1;
int i = Queue.Count, t;
Queue.Add((a, b));
while (i != 0)
{
t = (i - 1) / 2;
if (Queue[i].Item1 > Queue[t].Item1)
{
var k = Queue[i];
Queue[i] = Queue[t];
Queue[t] = k;
i = t;
}
else
{
break;
}
}
}
public (long, T) Dequeue()
{
int a = Queue.Count - 1;
var back = Queue[0];
Queue[0] = Queue[a];
Queue.RemoveAt(a);
for (int i = 0, j; (j = 2 * i + 1) < a;)
{
if (j != a - 1 && Queue[j].Item1 < Queue[j + 1].Item1)
j++;
if (Queue[i].Item1 < Queue[j].Item1)
{
var k = Queue[i];
Queue[i] = Queue[j];
Queue[j] = k;
i = j;
}
else
{
break;
}
}
if (revase == false)
back.Item1 *= -1;
return back;
}
public (long, T) get_first()
{
if (Queue.Count == 0)
return (default(long), default(T));
else
return Queue[0];
}
}
internal class SPFA
{
private Queue<long> que;
public long[] dist { get; set; }
public bool interactive { get; set; }
public List<List<(long, long)>> Graph { get; set; }
public List<long> times { get; set; }
public List<bool> pending { get; set; }
public SPFA(int n, bool cnt = true)
{
que = new Queue<long>();
dist = Enumerable.Repeat<long>(long.MaxValue, n + 1).ToArray();
times = Enumerable.Repeat<long>(0, n + 1).ToList();
pending = Enumerable.Repeat<bool>(false, n + 1).ToList();
Graph = new List<List<(long, long)>>();
for (int i = 0; i <= n; i++)
{
Graph.Add(new List<(long, long)>());
}
interactive = cnt;
BFS = new BFS(n, false);
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph[i].Add((t, cost));
if (interactive)
Graph[t].Add((i, cost));
BFS.Connect_Graph(i, t);
}
public bool Start_SPFA(int i)
{
//(捜索を始める頂点(int))
que.Enqueue(i);
pending[i] = true;
dist[i] = 0;
times[i]++;
while (que.Count != 0)
{
var t = (int)que.Dequeue();
pending[t] = false;
for (int w = 0; w < Graph[t].Count; w++)
{
long cost_before = dist[t] + Graph[t][w].Item2;
if (dist[Graph[t][w].Item1] <= cost_before)
continue;
dist[Graph[t][w].Item1] = cost_before;
if (!pending[(int)Graph[t][w].Item1])
{
if (times[(int)Graph[t][w].Item1]++ >= Graph.Count)
{
BFS.Start_BFS((int)Graph[t][w].Item1);
if (BFS.dist[times.Count - 1] != -1)
return false;
else
continue;
}
que.Enqueue(Graph[t][w].Item1);
pending[(int)Graph[t][w].Item1] = true;
}
}
}
return true;
}
static BFS BFS;
}
internal class Bellman_Ford
{
public long[] dist { get; set; }
public bool interactive { get; set; }
/// <summary>
/// 移動元,移動先,コスト
/// </summary>
public List<(long, long, long)> Graph { get; set; }
public int v;
public Bellman_Ford(int n, bool cnt = true)
{
v = n;
//ここの初期値(long.MaxValue/40)注意 オーバーフローしそう
dist = Enumerable.Repeat<long>(long.MaxValue / 40, n + 1).ToArray();
Graph = new List<(long, long, long)>();
interactive = cnt;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph.Add((i, t, cost));
if (interactive)
Graph.Add((t, i, cost));
}
public bool Start_Bellman_Ford(int i)
{
dist[i] = 0;
int cnt = 0;
while (cnt < v)
{
bool end = true;
foreach (var t in Graph)
{
if (t.Item1 != long.MaxValue && dist[t.Item1] + t.Item3 < dist[t.Item2])
{
dist[t.Item2] = dist[t.Item1] + t.Item3;
end = false;
}
}
if (end)
break;
cnt++;
}
return (cnt == v);
}
}
internal class Warshall_Floyd
{
public long[,] dist { get; private set; }
public bool interactive { get; set; }
public int v;
public Warshall_Floyd(int n, bool cnt = true)
{
dist = new long[n + 1, n + 1];
for (int i = 0; i <= n; i++)
for (int t = 0; t <= n; t++)
{
if (i == t)
{
dist[i, t] = 0;
}
else
{
dist[i, t] = long.MaxValue / 40;
}
}
interactive = cnt;
v = n;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
dist[i, t] = cost;
if (interactive)
dist[t, i] = cost;
}
public void Start_Warshall_Floyd()
{
for (int i = 1; i <= v; i++)
for (int t = 1; t <= v; t++)
for (int w = 1; w <= v; w++)
dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);
//dist[t, w] = Math.Min(dist[t, w], dist[t, i] + dist[i, w]);
}
}
internal class Binary_Trie
{
Node tree;
const int SZ = 64;
//const int SZ = 12;
int ans = 0;
List<byte> ans_byte;
public Binary_Trie()
{
tree = new Node();
ans_byte = new List<byte>();
}
public void add(long i)
{
tree = add_fx(tree, i);
}
private Node add_fx(Node now, long x, int now_height = SZ - 1)
{
if (now == null)
now = new Node();
now.cnt++;
if (now_height == -1)
return now;
long ne = x >> now_height & 1;
now[(int)ne] = add_fx(now[(int)ne], x, now_height - 1);
return now;
}
public void delete(long i)
{
tree = delete_fx(tree, i);
}
private Node delete_fx(Node now, long x, int now_height = SZ - 1)
{
if (now == null)
return now;
if (now.cnt == 0)
return now;
else
now.cnt--;
if (now_height == -1)
return now;
long ne = x >> now_height & 1;
now[(int)ne] = delete_fx(now[(int)ne], x, now_height - 1);
return now;
}
public int search(long i)
{
ans = 0;
search_fx(tree, i);
return ans;
}
private Node search_fx(Node now, long x, int now_height = SZ - 1)
{
if (now == null)
{
ans = 0;
return now;
}
else
{
if (now_height == -1)
return now;
long ne = x >> now_height & 1;
ans = now.cnt;
now[(int)ne] = search_fx(now[(int)ne], x, now_height - 1);
return now;
}
}
public int get_min_cnt(long i)
{
ans = 0;
get_min_cnt_fx(tree, i);
return ans;
}
private Node get_min_cnt_fx(Node now, long x, int now_height = SZ - 1)
{
if (now == null)
return now;
else
{
if (now_height == -1)
{
ans += now.cnt;
return now;
}
long ne = x >> now_height & 1;
if (ne == 1 && now[0] != null)
ans += now[0].cnt;
now[(int)ne] = get_min_cnt_fx(now[(int)ne], x, now_height - 1);
return now;
}
}
public int get_max_cnt(long i)
{
ans = 0;
get_max_cnt_fx(tree, i);
return ans;
}
private Node get_max_cnt_fx(Node now, long x, int now_height = SZ - 1)
{
if (now == null)
return now;
else
{
if (now_height == -1)
{
ans += now.cnt;
return now;
}
long ne = x >> now_height & 1;
if (ne == 0 && now[1] != null)
ans += now[1].cnt;
now[(int)ne] = get_max_cnt_fx(now[(int)ne], x, now_height - 1);
return now;
}
}
public long get_min(int xor = 0)
{
return get_min_fx(tree, xor);
}
private long get_min_fx(Node now, int xor, int now_height = SZ - 1)
{
if (SZ == -1) return 0;
int ne = xor >> SZ & 1;
if (now[ne] == null || now[ne].cnt == 0)
{
}
return 1;
}
public void ch()
{
int k = 0;
}
public class Node
{
public int cnt { get; set; }
public Node[] node = new Node[2];
public Node()
{
cnt = 0;
node[0] = null;
node[1] = null;
}
public Node this[int i]
{
get { return this.node[i]; }
set { this.node[i] = value; }
}
public void make_node(int i)
{
node[i] = new Node();
}
}
}
public class Kruskal
{
public List<(long, int, int)> Graph { get; set; }//コスト 行先、行先
static UnionFind UnionFind;
public Kruskal(int n)
{
Graph = new List<(long, int, int)>();
UnionFind = new UnionFind(n);
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる)
Graph.Add((cost, i, t));
}
public List<(long, int, int)> start_Kruskal()
{
var back = new List<(long, int, int)>();
Graph = Graph.OrderBy(i => i.Item1).ToList();
foreach (var i in Graph)
{
if (!UnionFind.groupcheck(i.Item2, i.Item3))
{
UnionFind.unite(i.Item2, i.Item3);
back.Add(i);
}
}
return back;
}
public bool is_conected(int x, int y)
{
return UnionFind.groupcheck(x, y);
}
}
public class FF
{
public List<List<(int, long, int)>> Graph { get; set; }//行先,コスト,逆辺のインデックス
public List<bool> flag { get; set; }
public int end { get; set; }
public FF(int n, int g = -1)
{
if (g == -1)
g = n;
flag = Enumerable.Repeat<bool>(false, n + 1).ToList();
Graph = new List<List<(int, long, int)>>();
for (int i = 0; i <= n; i++)
{
Graph.Add(new List<(int, long, int)>());
}
end = g;
}
public void Connect_Graph(int i, int t, long cost)
{
//(i==>tの辺を繋げる、気合で逆辺もつなげる)
int cnt_sei = Graph[i].Count;//正の辺のインデックス
int cnt_gixyaku = Graph[t].Count;//逆辺のインデックス
Graph[i].Add((t, cost, cnt_gixyaku));
Graph[t].Add((i, 0, cnt_sei));
}
public int Start_FF(int x, int fl)
{
if (flag[x])
return -1;
flag[x] = true;
if (x == end)
return fl;
int r = -1;
for (int t = 0; t < Graph[x].Count; t++)
{
var hen = Graph[x][t];
var w = hen.Item1;//行先
var c = hen.Item2;//コスト
var i = hen.Item3;//逆辺でのインデックス
if (c == 0)
continue;
r = Start_FF((int)w, (int)Math.Min(fl, c));
if (r == -1)
continue;
else
{
//容量減らす
Graph[x][t] = (w, c - r, i);
//逆辺増やす
Graph[w][i] = (x, Graph[w][i].Item2 + r, t);
return r;
}
}
return -1;
}
}
internal class RMQ
{
List<long> tree { get; set; }//完全二分木
List<long> lazy { get; set; }//遅延用
int n;
long inf = long.MaxValue/4;
bool is_max_query;
public RMQ(int i, bool is_max_query = false)
{
tree = new List<long>();
lazy = new List<long>();
n = 1;
while (n <= i)
n *= 2;
for (int t = 0; t < n * 2; t++)
{
tree.Add(inf);
lazy.Add(inf);
}
this.is_max_query = is_max_query;
}
public RMQ(int i,List<long> v,bool is_max_query=false)
{
tree = new List<long>();
lazy = new List<long>();
n = 1;
while (n <= i)
n *= 2;
for (int t = 0; t < n * 2; t++)
{
tree.Add(inf);
lazy.Add(0);
}
this.is_max_query = is_max_query;
for(int t=0; t<v.Count; t++)
tree[t+n]=v[t];
for (int t = n - 2; t >= 0; t--)
tree[t] = Math.Min(tree[t * 2 + 1], tree[t * 2 + 2]);
}
private void lazy_fx(int i)
{
if (lazy[i] == 0)
return;
if(i<n-1)
{
lazy[i * 2 + 1] += lazy[i];
lazy[i * 2 + 2] += lazy[i];
}
tree[i] += lazy[i];
lazy[i] = 0;
}
public void update(int l,int r,int value)
{
value *= is_max_query ? -1 : 1;
update_fx(0, value, 0, n, l, r);
}
public void update(int index,int value)
{
value *= is_max_query ? -1 : 1;
update_fx(0, value, 0, n, index, index+1);
}
public void update_fx(int index,int value,int now_l,int now_r,int L,int R)
{
lazy_fx(index);
if(now_l>=L&&now_r<=R)
{
lazy[index] += value;
lazy_fx(index);
}
else if(L<now_r&&now_l<R)
{
update_fx(index * 2 + 1, value, now_l, (now_l + now_r) / 2,L,R);
update_fx(index * 2 + 2, value, (now_l+now_r)/2, now_r, L, R);
tree[index] = Math.Min(tree[index * 2 + 1], tree[index * 2 + 2]);
}
}
public long get(int l,int r)
{
//lは含む rは含まない
return get_fx(0, 0, n, l, r) * (is_max_query ? -1 : 1);
}
public long get(int index)
{
return tree[n + index - 1];
}
private long get_fx(int index,int now_l,int now_r,int L,int R)
{
lazy_fx(index);
if (now_r<=L||R<=now_l)
return inf;
else if (now_l>=L&&now_r<=R)
return tree[index];
else
{
long vl = get_fx(index * 2 + 1, now_l, (now_l + now_r) / 2, L, R);
long vr = get_fx(index * 2 + 2, (now_l + now_r) / 2, now_r, L, R);
return Math.Min(vl,vr);
}
}
}
public class TSP
{
/// <summary>
/// 0indexedです！！！！ 1にしたいけど無理！！！！！！！！！
/// 引数も0indexで投げてください
/// </summary>
public readonly double double_inf = double.MaxValue / 128;
const long long_inf = long.MaxValue / 128;
public List<List<double>> dp { get; set; }
public bool interactive { get; set; }
public List<(double x,double y)> Graph { get; set; }
public TSP(int n, bool cnt = true)
{
dp = new List<List<double>>();
for (int i = 0; i < Math.Pow(2, n); i++)
{
dp.Add(new List<double>(n));
for (int t = 0; t < n; t++)
{
dp[i].Add(double_inf);
}
}
Graph = new List<(double x, double y)>();
interactive = cnt;
}
public void Connect_Graph(double x, double y)
{
//(i==>tの辺を繋げる、interactive==trueならt==>tの辺も繋げる)
Graph.Add((x, y));
}
public void start_tsp(int n)
{
for(int i=0; i<Graph.Count; i++)
{
dp[1 << i][i] = Math.Sqrt(Graph[i].x * Graph[i].x + Graph[i].y * Graph[i].y);
}
for (int flag = 0; flag < 1 << Graph.Count; flag++)
{
var cnt_get_booster = 1 << BitOperations.PopCount((uint)flag >> n);
for (int now = 0; now < Graph.Count; now++)
{
if (dp[flag][now] == double_inf)
continue;
for (int next = 0; next < Graph.Count; next++)
{
if ((flag & (1 << next)) != 0)
continue;
dp[flag | (1 << next)][next] = Math.Min(dp[flag | (1 << next)][next],dp[flag][now] + get_cost(now,next)/cnt_get_booster);
}
}
}
}
public double get_cost(int i,int t)
{
return Math.Sqrt(Math.Pow(2, (Graph[i].x - Graph[t].x) + Math.Pow(2, (Graph[i].y - Graph[t].y))));
}
}
}