結果
問題 | No.1234 典型RMQ |
ユーザー | TAKA 00 |
提出日時 | 2022-12-09 12:40:45 |
言語 | C# (.NET 8.0.203) |
結果 |
WA
|
実行時間 | - |
コード長 | 40,645 bytes |
コンパイル時間 | 9,392 ms |
コンパイル使用メモリ | 167,228 KB |
実行使用メモリ | 193,472 KB |
最終ジャッジ日時 | 2024-10-14 18:37:00 |
合計ジャッジ時間 | 21,980 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (88 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(47,31): warning CS0169: フィールド 'Program.Warshall_Floyd' は使用されていません [/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(43,26): warning CS0169: フィールド 'Program.UnionFind' は使用されていません [/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/co
ソースコード
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 = 2; 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 = 2; while (n < i) n *= 2; for (int t = 0; t < n * 2-1; 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-1]=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_l>=R||now_r<=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)))); } } }