結果
| 問題 | No.3013 ハチマキ買い星人 |
| ユーザー |
 Nauclhlt🪷
|
| 提出日時 | 2025-01-25 13:41:55 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,130 ms / 2,000 ms |
| コード長 | 62,055 bytes |
| コンパイル時間 | 19,104 ms |
| コンパイル使用メモリ | 172,372 KB |
| 実行使用メモリ | 247,784 KB |
| 最終ジャッジ日時 | 2025-01-25 22:56:50 |
| 合計ジャッジ時間 | 36,201 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge8 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 45 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (106 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Collections;
using System.Text;
using System.Text.RegularExpressions;
using static Tmpl;
using static CPDebug;
using System.Collections.Specialized;
using System.Globalization;
using System.Diagnostics;
StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
//using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite));
Console.SetOut(writer);
//using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open));
//Console.SetIn(reader);
Solver.Solve();
Console.Out.Flush();
public static class Solver
{
private static readonly AtCoderIO cin = new AtCoderIO();
public static unsafe void Solve()
{
int N = cin.Int();
int M = cin.Int();
int P = cin.Int();
long Y = cin.Long();
Graph<long> g = new(N);
for (int i = 0; i < M; i++)
{
int a = cin.Int() - 1;
int b = cin.Int() - 1;
long c = cin.Long();
g.AddEdge(a, b, c);
}
long[] fromStart = g.DijkstraFrom(0);
long[] fromDest = g.DijkstraFrom(N - 1);
long ans = 0;
for (int i = 0; i < P; i++)
{
int d = cin.Int() - 1;
long e = cin.Long();
long cost = fromStart[d];
long money = long.Max(0, Y - cost);
chmax(ref ans, money / e);
}
print(ans);
}
}
public abstract class GraphBase<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
protected List<List<Edge<T>>> _adjList;
protected List<Edge<T>> _directionAwareEdges;
protected int _vertexCount;
public int VertexCount => _vertexCount;
public List<List<Edge<T>>> AdjList => _adjList;
public List<Edge<T>> DirectionAwareEdges => _directionAwareEdges;
protected void Initialize(int vertexCount)
{
_vertexCount = vertexCount;
_adjList = new (vertexCount);
for (int i = 0; i < vertexCount; i++)
{
_adjList.Add(new());
}
_directionAwareEdges = new();
}
protected void Sync(int vertexCount, List<List<Edge<T>>> adjList, List<Edge<T>> daEdges)
{
_vertexCount = vertexCount;
_adjList = adjList;
_directionAwareEdges = daEdges;
}
public UnionFind CreateDSU()
{
UnionFind uf = new(_vertexCount);
for (int i = 0; i < _directionAwareEdges.Count; i++)
{
uf.Unite(_directionAwareEdges[i].From, _directionAwareEdges[i].To);
}
return uf;
}
public T[] DijkstraFrom(int n)
{
if (!Validate(n)) return null;
bool[] seen = new bool[_vertexCount];
T[] map = new T[_vertexCount];
Array.Fill(map, T.MaxValue);
map[n] = T.Zero;
PriorityQueue<int, T> pq = new();
pq.Enqueue(n, T.Zero);
while (pq.Count > 0)
{
int p = pq.Dequeue();
if (seen[p]) continue;
seen[p] = true;
List<Edge<T>> children = _adjList[p];
for (int i = 0; i < children.Count; i++)
{
T w = map[p] + children[i].Weight;
if (w < map[children[i].To])
{
map[children[i].To] = w;
pq.Enqueue(children[i].To, map[children[i].To]);
}
}
}
return map;
}
public T[,] WarshallFloyd()
{
if (_vertexCount > 800)
{
throw new InvalidOperationException("Too large graph.");
}
T[,] map = new T[_vertexCount, _vertexCount];
for (int i = 0; i < _vertexCount; i++)
{
for (int j = 0; j < _vertexCount; j++)
{
map[i, j] = T.MaxValue;
}
}
for (int i = 0; i < _vertexCount; i++)
{
map[i, i] = T.Zero;
}
for (int i = 0; i < _directionAwareEdges.Count; i++)
{
Edge<T> e = _directionAwareEdges[i];
map[e.From, e.To] = T.Min(e.Weight, map[e.From, e.To]);
}
for (int k = 0; k < _vertexCount; k++)
{
for (int j = 0; j < _vertexCount; j++)
{
for (int i = 0; i < _vertexCount; i++)
{
if (map[i, k] != T.MaxValue && map[k, j] != T.MaxValue)
{
if (map[i, k] + map[k, j] < map[i, j])
{
map[i, j] = map[i, k] + map[k, j];
}
}
}
}
}
return map;
}
public abstract void AddEdge(int a, int b, T weight);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
protected bool Validate(int n)
{
return 0 <= n && n < _vertexCount;
}
}
public class Graph<T> : GraphBase<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
private List<Edge<T>> _edges;
public List<Edge<T>> Edges => _edges;
public Graph(int vertexCount)
{
Initialize(vertexCount);
_edges = new();
}
public override void AddEdge(int a, int b, T weight)
{
if (!Validate(a) || !Validate(b)) return;
if (a > b)
{
(a, b) = (b, a);
}
Edge<T> right = new Edge<T>(a, b, weight);
Edge<T> left = new Edge<T>(b, a, weight);
_adjList[a].Add(right);
_adjList[b].Add(left);
_edges.Add(right);
_directionAwareEdges.Add(left);
_directionAwareEdges.Add(right);
}
public DfsTimeLabel DfsLabelFrom(int from)
{
if (!Validate(from)) return null;
bool[] seen = new bool[_vertexCount];
int timestamp = 0;
int[] inLabel = new int[_vertexCount];
int[] outLabel = new int[_vertexCount];
void dfs(int n, int prev)
{
inLabel[n] = timestamp;
timestamp++;
seen[n] = true;
var ch = _adjList[n];
for (int i = 0; i < ch.Count; i++)
{
if (ch[i].To == prev || seen[ch[i].To]) continue;
dfs(ch[i].To, n);
}
outLabel[n] = timestamp;
timestamp++;
}
dfs(from, -1);
return new DfsTimeLabel(inLabel, outLabel);
}
public Graph<T> CreateComplement()
{
HashSet<(int, int)> edgeSet = new();
for (int i = 0; i < _edges.Count; i++)
{
edgeSet.Add((_edges[i].From, _edges[i].To));
}
Graph<T> g = new(_vertexCount);
for (int i = 0; i < _vertexCount - 1; i++)
{
for (int j = i + 1; j < _vertexCount; j++)
{
if (!edgeSet.Contains((i, j)))
{
g.AddEdge(i, j, default);
}
}
}
return g;
}
public bool IsBipartite()
{
bool[] seen = new bool[_vertexCount];
Stack<(int, bool)> stack = new();
bool[] memo = new bool[_vertexCount];
for (int i = 0; i < _vertexCount; i++)
{
stack.Push((i, false));
while (stack.Count > 0)
{
(int n, bool c) = stack.Pop();
if (seen[n])
{
if (memo[n] != !c) return false;
continue;
}
seen[n] = true;
memo[n] = !c;
var ch = _adjList[n];
for (int j = 0; j < ch.Count; j++)
{
stack.Push((ch[j].To, !c));
}
}
}
return true;
}
public T MaxSpanningTreeWeight()
{
UnionFind unionFind = new(_vertexCount);
T ans = T.Zero;
foreach (var edge in _edges.OrderByDescending(x => x.Weight))
{
if (!unionFind.Same(edge.From, edge.To))
{
unionFind.Unite(edge.From, edge.To);
ans += edge.Weight;
}
}
return ans;
}
public T MinSpanningTreeWeight()
{
UnionFind unionFind = new(_vertexCount);
T ans = T.Zero;
foreach (var edge in _edges.OrderBy(x => x.Weight))
{
if (!unionFind.Same(edge.From, edge.To))
{
unionFind.Unite(edge.From, edge.To);
ans += edge.Weight;
}
}
return ans;
}
}
public class DirectedGraph<T> : GraphBase<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
private List<List<Edge<T>>> _reverseAdjList;
private List<Edge<T>> _reverseEdges;
public List<List<Edge<T>>> ReverseAdjList => _reverseAdjList;
public List<Edge<T>> ReverseEdges => _reverseEdges;
public List<Edge<T>> Edges => _directionAwareEdges;
public DirectedGraph(int vertexCount)
{
Initialize(vertexCount);
_reverseAdjList = new(vertexCount);
for (int i = 0; i < vertexCount; i++)
{
_reverseAdjList.Add(new());
}
_reverseEdges = new();
}
public override void AddEdge(int a, int b, T weight)
{
if (!Validate(a) || !Validate(b)) return;
Edge<T> e = new Edge<T>(a, b, weight);
Edge<T> rev = new Edge<T>(b, a, weight);
_adjList[a].Add(e);
_reverseAdjList[b].Add(rev);
_directionAwareEdges.Add(e);
_reverseEdges.Add(rev);
}
public bool TryTopologicalSort(out List<int> sorted)
{
sorted = new List<int>(_vertexCount);
int[] deg = new int[_vertexCount];
for (int i = 0; i < _directionAwareEdges.Count; i++)
{
deg[_directionAwareEdges[i].To]++;
}
Queue<int> queue = new();
for (int i = 0; i < _vertexCount; i++)
{
if (deg[i] == 0) queue.Enqueue(i);
}
while (queue.Count > 0)
{
int next = queue.Dequeue();
sorted.Add(next);
List<Edge<T>> p = _adjList[next];
for (int i = 0; i < p.Count; i++)
{
deg[p[i].To]--;
if (deg[p[i].To] < 0) return false;
if (deg[p[i].To] == 0)
{
queue.Enqueue(p[i].To);
}
}
}
return sorted.Count == _vertexCount;
}
public bool TryUniqueTopologicalSort(out List<int> sorted)
{
sorted = new List<int>(_vertexCount);
int[] deg = new int[_vertexCount];
for (int i = 0; i < _directionAwareEdges.Count; i++)
{
deg[_directionAwareEdges[i].To]++;
}
Queue<int> queue = new();
for (int i = 0; i < _vertexCount; i++)
{
if (deg[i] == 0) queue.Enqueue(i);
}
while (queue.Count > 0)
{
if (queue.Count > 1) return false;
int next = queue.Dequeue();
sorted.Add(next);
List<Edge<T>> p = _adjList[next];
for (int i = 0; i < p.Count; i++)
{
deg[p[i].To]--;
if (deg[p[i].To] < 0) return false;
if (deg[p[i].To] == 0)
{
queue.Enqueue(p[i].To);
}
}
}
return sorted.Count == _vertexCount;
}
public List<List<int>> SplitSCC()
{
bool[] seen = new bool[_vertexCount];
int[] t = new int[_vertexCount];
int seenIndex = 1;
void dfs1(int n)
{
seen[n] = true;
var ch = _adjList[n];
for (int i = 0; i < ch.Count; i++)
{
if (!seen[ch[i].To])
dfs1(ch[i].To);
}
t[n] = seenIndex;
seenIndex++;
}
for (int i = 0; i < _vertexCount; i++)
{
if (!seen[i])
{
dfs1(i);
}
}
Array.Clear(seen);
PriorityQueue<int, int> pq = new();
for (int i = 0; i < _vertexCount; i++)
{
pq.Enqueue(i, -t[i]);
}
List<List<int>> res = new();
Stack<int> stack = new();
while (pq.Count > 0)
{
int p = pq.Dequeue();
if (seen[p]) continue;
List<int> list = new();
stack.Push(p);
while (stack.Count > 0)
{
int n = stack.Pop();
if (seen[n]) continue;
seen[n] = true;
list.Add(n);
var ch = _reverseAdjList[n];
for (int j = 0; j < ch.Count; j++)
{
stack.Push(ch[j].To);
}
}
res.Add(list);
}
return res;
}
}
public abstract class GraphDecorator<T> : GraphBase<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
protected Graph<T> _graph;
public Graph<T> Graph => _graph;
public GraphDecorator(Graph<T> graph)
{
_graph = graph;
Sync(graph.VertexCount, graph.AdjList, graph.DirectionAwareEdges);
}
}
public abstract class DirectedGraphDecorator<T> : GraphBase<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
protected DirectedGraph<T> _graph;
public DirectedGraph<T> Graph => _graph;
public DirectedGraphDecorator(DirectedGraph<T> graph)
{
_graph = graph;
Sync(graph.VertexCount, graph.AdjList, graph.DirectionAwareEdges);
}
}
public class TreeDecorator<T> : GraphDecorator<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
public TreeDecorator(Graph<T> graph) : base(graph)
{
if (graph.Edges.Count != graph.VertexCount - 1)
{
throw new InvalidOperationException("Not a tree graph.");
}
}
public T[] BfsFrom(int n)
{
if (!Validate(n)) return null;
bool[] seen = new bool[_vertexCount];
T[] map = new T[_vertexCount];
map[n] = T.Zero;
Queue<(int, T)> queue = new();
queue.Enqueue((n, T.Zero));
while (queue.Count > 0)
{
(int p, T w) = queue.Dequeue();
if (seen[p]) continue;
seen[p] = true;
map[p] = w;
List<Edge<T>> children = _adjList[p];
for (int i = 0; i < children.Count; i++)
{
queue.Enqueue((children[i].To, w + children[i].Weight));
}
}
return map;
}
public T GetDiameter()
{
T[] dist = BfsFrom(0);
T max = T.Zero;
int v = 0;
for (int i = 0; i < _vertexCount; i++)
{
if (dist[i] > max)
{
max = dist[i];
v = i;
}
}
dist = BfsFrom(v);
return dist.Max();
}
public override void AddEdge(int a, int b, T weight)
{
_graph.AddEdge(a, b, weight);
}
}
public class FunctionalGraphDecorator<T> : DirectedGraphDecorator<T> where T : struct, INumber<T>, IMinMaxValue<T>
{
public FunctionalGraphDecorator(DirectedGraph<T> graph) : base(graph)
{
for (int i = 0; i < _vertexCount; i++)
{
if (_adjList[i].Count != 1)
{
throw new InvalidOperationException("Not a functional graph.");
}
}
}
public (List<List<int>> cycles, Graph<T> trees) SplitCycleTree(bool sortCycle = false)
{
List<List<int>> scc = _graph.SplitSCC();
List<List<int>> cycles = new();
Graph<T> tree = new(_vertexCount);
for (int i = 0; i < scc.Count; i++)
{
if (scc[i].Count == 1 && _adjList[scc[i][0]][0].To != scc[i][0])
{
// part of the trees
int u = scc[i][0];
tree.AddEdge(u, _adjList[u][0].To, _adjList[u][0].Weight);
}
else
{
// cycle
if (sortCycle)
{
List<int> sorted = new(scc[i].Count);
sorted.Add(scc[i][0]);
for (int j = 1; j < scc[i].Count; j++)
{
sorted.Add(_adjList[sorted[^1]][0].To);
}
cycles.Add(sorted);
}
else
{
cycles.Add(scc[i]);
}
}
}
return (cycles, tree);
}
public override void AddEdge(int a, int b, T weight)
{
_graph.AddEdge(a, b, weight);
}
}
public sealed class DfsTimeLabel
{
private int[] _in;
private int[] _out;
public DfsTimeLabel(int[] @in, int[] @out)
{
_in = @in;
_out = @out;
}
public int GetInTime(int n)
{
return _in[n];
}
public int GetOutTime(int n)
{
return _out[n];
}
}
static class Constants
{
public const long Mod = 998244353L;
//public const long Mod = 10007L;
//public const long Mod = 1000000007L;
}
public readonly struct Point
{
public readonly int X;
public readonly int Y;
public Point(int x, int y)
{
X = x;
Y = y;
}
public override int GetHashCode() => (X, Y).GetHashCode();
public override string ToString()
{
return $"({X}, {Y})";
}
}
public sealed class ReverseComparer<T> : IComparer<T>
{
public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);
public static ReverseComparer<T> Reverse(IComparer<T> comparer)
{
return new ReverseComparer<T>(comparer);
}
private readonly IComparer<T> comparer = Default;
private ReverseComparer(IComparer<T> comparer)
{
this.comparer = comparer;
}
public int Compare(T x, T y)
{
return comparer.Compare(y, x);
}
}
public sealed class AtCoderIO
{
Queue<string> _readQueue = new Queue<string>();
private void LoadQueue()
{
if (_readQueue.Count > 0) return;
string line = Console.ReadLine();
string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries);
for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]);
}
private void Guard()
{
if (_readQueue.Count == 0)
{
throw new Exception("NO DATA TO READ");
}
}
public int Int()
{
LoadQueue();
Guard();
return int.Parse(_readQueue.Dequeue());
}
public long Long()
{
LoadQueue();
Guard();
return long.Parse(_readQueue.Dequeue());
}
public string String()
{
LoadQueue();
Guard();
return _readQueue.Dequeue();
}
public short Short()
{
LoadQueue();
Guard();
return short.Parse(_readQueue.Dequeue());
}
public byte Byte()
{
LoadQueue();
Guard();
return byte.Parse(_readQueue.Dequeue());
}
public char Char()
{
LoadQueue();
Guard();
return char.Parse(_readQueue.Dequeue());
}
public double Double()
{
LoadQueue();
Guard();
return double.Parse(_readQueue.Dequeue());
}
public float Float()
{
LoadQueue();
Guard();
return float.Parse(_readQueue.Dequeue());
}
public ModInt ModInt()
{
return new ModInt(Long());
}
public T Read<T>()
{
Type type = typeof(T);
if (type == typeof(int)) return (T)(object)Int();
else if (type == typeof(long)) return (T)(object)Long();
else if (type == typeof(float)) return (T)(object)Float();
else if (type == typeof(double)) return (T)(object)Double();
else if (type == typeof(short)) return (T)(object)Short();
else if (type == typeof(byte)) return (T)(object)Byte();
else if (type == typeof(char)) return (T)(object)Char();
else if (type == typeof(string)) return (T)(object)String();
else if (type == typeof(ModInt)) return (T)(object)ModInt();
else return default(T);
}
public int[] IntArray(int n)
{
if (n == 0) return Array.Empty<int>();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = Int();
}
return arr;
}
public int[] ZeroIndexedPermutation(int n)
{
if (n == 0) return Array.Empty<int>();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
{
arr[i] = Int() - 1;
}
return arr;
}
public long[] LongArray(int n)
{
if (n == 0) return Array.Empty<long>();
long[] arr = new long[n];
for (int i = 0; i < n; i++)
{
arr[i] = Long();
}
return arr;
}
public double[] DoubleArray(int n)
{
if (n == 0) return Array.Empty<double>();
double[] arr = new double[n];
for (int i = 0; i < n; i++)
{
arr[i] = Double();
}
return arr;
}
public ModInt[] ModIntArray(int n)
{
if (n == 0) return Array.Empty<ModInt>();
ModInt[] arr = new ModInt[n];
for (int i = 0; i < n; i++)
{
arr[i] = (ModInt)Long();
}
return arr;
}
public T[] ReadArray<T>(int n)
{
if (n == 0) return Array.Empty<T>();
T[] arr = new T[n];
for (int i = 0; i < n; i++)
{
arr[i] = Read<T>();
}
return arr;
}
}
public static class CPDebug
{
public static void check<T>(T value, [CallerArgumentExpression(nameof(value))] string name = "value")
{
#if DEBUG
Console.WriteLine($"[DEBUG] {name}={value.ToString()}");
#endif
}
public static void check<T>(IEnumerable<T> value, [CallerArgumentExpression(nameof(value))] string name = "value")
{
#if DEBUG
Console.WriteLine($"[DEBUG] {name}=({string.Join(' ', value)})");
#endif
}
}
public static class Tmpl
{
public static int combination(int n, int r)
{
int c = 1;
for (int i = 1; i <= r; i++)
{
c = c * (n - i + 1) / i;
}
return c;
}
public static long combination(long n, long r)
{
long c = 1;
for (long i = 1; i <= r; i++)
{
c = c * (n - i + 1) / i;
}
return c;
}
public static long pow(long b, long exp)
{
if (exp == 0) return 1;
if (exp == 1) return b;
long m = pow(b, exp / 2L);
m *= m;
if (exp % 2L == 1) m *= b;
return m;
}
public static long modpow(long b, long exp, long mod)
{
if (exp == 0) return 1;
if (exp == 1) return b % mod;
long m = modpow(b, exp / 2L, mod);
m *= m;
m %= mod;
if (exp % 2L == 1) m *= b % mod;
m %= mod;
return m;
}
static long modinv( long a, long mod )
{
long b = mod, u = 1, v = 0;
while ( b > 0 )
{
long t = a / b;
a -= t * b; swap( ref a, ref b );
u -= t * v; swap( ref u, ref v );
}
u %= mod;
if (u < 0) u += mod;
return u;
}
public static long calcLcm(long a, long b)
{
return a * b / calcGcd(a, b);
}
public static long calcGcd(long a, long b)
{
if (a % b == 0) return b;
return calcGcd(b, a % b);
}
// ax ≡ b (mod m)なる最小のxを求める
public static bool solveModLinear(long a, long b, long m, out long minSolution)
{
long gcd = calcGcd(calcGcd(a, b), m);
a /= gcd;
b /= gcd;
m /= gcd;
if (calcGcd(a, m) == 1)
{
long inv = modinv(a, m);
minSolution = (b * inv) % m;
return true;
}
minSolution = 0;
return false;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void YesNo(bool t)
{
Console.WriteLine(t ? "Yes" : "No");
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void YESNO(bool t)
{
Console.WriteLine(t ? "YES" : "NO");
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void yesno(bool t)
{
Console.WriteLine(t ? "yes" : "no");
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool checkBit(int bit, int n)
{
return ((1 << n) & bit) != 0;
}
public static bool nextCombination(int n, int r, int[] array)
{
int i = array.Length - 1;
while (i >= 0 && array[i] == i + n - r)
{
i--;
}
if (i < 0) return false;
array[i]++;
for (int j = i + 1; j < r; j++)
{
array[j] = array[j - 1] + 1;
}
return true;
}
public static bool nextPermutation<T>(T[] array, int start, int length) where T : IComparable<T>
{
int end = start + length - 1;
if (end <= start) return false;
int last = end;
while (true)
{
int pos = last--;
if (array[last].CompareTo(array[pos]) < 0)
{
int i;
for (i = end + 1; array[last].CompareTo(array[--i]) >= 0; ) { }
T tmp = array[last]; array[last] = array[i]; array[i] = tmp;
Array.Reverse(array, pos, end - pos + 1);
return true;
}
if (last == start)
{
Array.Reverse(array, start, end - start);
return false;
}
}
throw new Exception("NextPermutation: Fatal error");
}
public static unsafe Dictionary<char, int> cntCharOcc(string s)
{
Dictionary<char, int> dict = new Dictionary<char, int>();
fixed (char* ptr = s)
{
for (int i = 0; i < s.Length; i++)
{
if (dict.ContainsKey(ptr[i]))
{
dict[ptr[i]] += 1;
}
else
{
dict[ptr[i]] = 1;
}
}
}
return dict;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void chmax<T> (ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
{
if (value > target)
{
target = value;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void chmin<T>(ref T target, T value) where T : struct, IComparisonOperators<T, T, bool>
{
if (value < target)
{
target = value;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void arrMod<T>(T[] array, T b) where T : IModulusOperators<T, T, T>
{
for (int i = 0; i < array.Length; i++)
{
array[i] %= b;
}
}
public static ReadOnlySpan<T> spanOf<T>(List<T> list)
{
return CollectionsMarshal.AsSpan(list);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void swap<T>(T[] array, int i, int j) where T : struct
{
(array[i], array[j]) = (array[j], array[i]);
}
public static void shuffle<T>(T[] array) where T : struct
{
Random random = new Random();
for (int i = array.Length - 1; i > 0; i--)
{
int index = random.Next(0, i + 1);
swap(array, index, i);
}
}
public static int lowerBound<T>(T[] array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (array[mid] < value)
low = mid + 1;
else
high = mid;
}
if (low == array.Length - 1 && array[low] < value)
{
return array.Length;
}
return low;
}
public static int lowerBound<T>(List<T> array, int start, int end, T value) where T : struct, IComparisonOperators<T, T, bool>
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (array[mid] < value)
low = mid + 1;
else
high = mid;
}
if (low == array.Count - 1 && array[low] < value)
{
return array.Count;
}
return low;
}
public static int upperBound<T>(T[] array, T value) where T : struct, IComparisonOperators<T, T, bool>
{
var l = 0;
var r = array.Length - 1;
while (l <= r)
{
var mid = l + (r - l) / 2;
if (array[mid] <= value) l = mid + 1;
else r = mid - 1;
}
return l;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void swap<T>(ref T a, ref T b) where T : struct
{
T temp = a;
a = b;
b = temp;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool dbleq(double a, double b)
{
return Math.Abs(a - b) < double.Epsilon;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int dblAsInt(double d)
{
return (int)Math.Round(d, 0);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static long dblAsLong(double d)
{
return (long)Math.Round(d, 0);
}
public static int[] compressCoords<T>(T[] a) where T : struct, IComparisonOperators<T, T, bool>
{
T[] b = a.OrderBy(x => x).Distinct().ToArray();
int[] result = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
result[i] = lowerBound(b, 0, b.Length - 1, a[i]);
}
return result;
}
public static List<RunLengthElement<T>> compressRunLength<T>(T[] array) where T : struct, IEquatable<T>
{
List<RunLengthElement<T>> list = new List<RunLengthElement<T>>();
int count = 1;
int start = 0;
T prev = array[0];
for (int i = 1; i < array.Length; i++)
{
if (prev.Equals(array[i]))
{
count++;
}
else
{
list.Add(new RunLengthElement<T>(start, count, prev));
start = i;
count = 1;
}
prev = array[i];
}
list.Add(new RunLengthElement<T>(start, count, prev));
return list;
}
public static char[] alphabetsLower()
{
return new[] { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
}
public static char[] alphebetsUpper()
{
return new[]{ 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print<T>(IEnumerable<T> array, char delimiter = ' ')
{
Console.WriteLine(string.Join(delimiter, array));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void fprint<T>(IEnumerable<T> array, char delimiter = ' ')
{
print(array);
Console.Out.Flush();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print(string msg)
{
Console.WriteLine(msg);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void fprint(string msg)
{
Console.WriteLine(msg);
Console.Out.Flush();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print(int val)
{
print(val.ToString());
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print(long val)
{
print(val.ToString());
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void print(ModInt val)
{
print(val.ToString());
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void fprint(int val)
{
print(val.ToString());
Console.Out.Flush();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void fprint(long val)
{
print(val.ToString());
Console.Out.Flush();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void fprint(ModInt val)
{
fprint(val.ToString());
Console.Out.Flush();
}
public static void print<T>(T[,] grid)
{
for (int y = 0; y < grid.GetLength(0); y++)
{
for (int x = 0; x < grid.GetLength(1); x++)
{
Console.Write(grid[y, x] + "\t");
}
Console.WriteLine();
}
}
public static void print01(bool t)
{
Console.WriteLine(t ? "1" : "0");
}
public static TSrc lowerBoundKth<TSrc, TCnt>(TSrc min, TSrc max, Func<TSrc, TCnt> f, TCnt bound)
where TSrc: struct, INumber<TSrc> where TCnt: struct, INumber<TCnt>
{
TSrc left = min;
TSrc right = max;
TSrc two = TSrc.CreateChecked(2);
TSrc one = TSrc.CreateChecked(1);
while (right > left)
{
TSrc mid = left + (right - left) / two;
TCnt c = f(mid);
if (c < bound)
{
left = mid + one;
}
else
{
right = mid;
}
}
return left;
}
public static bool isSquareNumber(long n)
{
long q = (long)Math.Floor(Math.Sqrt(n));
return q * q == n;
}
}
public readonly struct RunLengthElement<T> where T : struct
{
public readonly int Count;
public readonly int StartIndex;
public readonly T Value;
public RunLengthElement(int startIndex, int count, T value)
{
this.StartIndex = startIndex;
this.Count = count;
this.Value = value;
}
}
public readonly struct Edge<T> : IEquatable<Edge<T>>, IComparable<Edge<T>> where T : struct, INumber<T>
{
public readonly int To;
public readonly int From;
public readonly T Weight;
public Edge(int to, T weight)
{
this.To = to;
this.Weight = weight;
}
public Edge(int from, int to, T weight)
{
this.To = to;
this.From = from;
this.Weight = weight;
}
public override bool Equals(object obj)
{
if (obj is Edge<T> edge)
{
return this.Equals(edge);
}
else
{
return false;
}
}
public int CompareTo(Edge<T> other)
{
return Weight.CompareTo(other.Weight);
}
public bool Equals(Edge<T> edge)
{
return To == edge.To && From == edge.From && Weight == edge.Weight;
}
public override int GetHashCode()
{
return (To, From, Weight).GetHashCode();
}
public static bool operator ==(Edge<T> left, Edge<T> right)
{
return left.Equals(right);
}
public static bool operator !=(Edge<T> left, Edge<T> right)
{
return !left.Equals(right);
}
}
public readonly struct ModInt : IEquatable<ModInt>, IAdditionOperators<ModInt, ModInt, ModInt>, ISubtractionOperators<ModInt, ModInt, ModInt>, IAdditiveIdentity<ModInt, ModInt>
{
private readonly long Value;
public static ModInt One => (ModInt)1L;
public static ModInt Zero => (ModInt)0L;
public static ModInt AdditiveIdentity => Zero;
public ModInt(long value)
{
Value = SafeMod(value);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static long SafeMod(long a)
{
a %= Constants.Mod;
if (a < 0) a += Constants.Mod;
return a;
}
public ModInt Power(long exp)
{
if (exp <= -1) return this;
if (exp == 0) return 1;
if (exp == 1) return this;
ModInt m = Power(exp / 2);
m *= m;
if (exp % 2 == 1) m *= this;
return m;
}
public ModInt Inv()
{
return this.Power(Constants.Mod - 2L);
}
public static ModInt operator +(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value + right.Value));
}
public static ModInt operator -(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value - right.Value));
}
public static ModInt operator *(ModInt left, ModInt right)
{
return new ModInt(SafeMod(left.Value * right.Value));
}
public static ModInt operator /(ModInt left, ModInt right)
{
if (right.Value == 0L)
{
return Zero;
}
ModInt inv = right.Inv();
return SafeMod(left * inv);
}
public static ModInt operator %(ModInt left, ModInt right)
{
if (right.Value == 0L)
{
return Zero;
}
return new ModInt(SafeMod(left.Value % right.Value));
}
public static bool operator ==(ModInt left, ModInt right)
{
return left.Value == right.Value;
}
public static bool operator != (ModInt left, ModInt right)
{
return !(left == right);
}
public bool Equals(ModInt other)
{
return Value == other.Value;
}
public override bool Equals(object other)
{
if (other is ModInt m)
{
return this == m;
}
else return false;
}
public override int GetHashCode()
{
return Value.GetHashCode();
}
public static implicit operator ModInt(long v)
{
return new ModInt(v);
}
public static implicit operator ModInt(int v)
{
return new ModInt(v);
}
public static implicit operator long(ModInt m)
{
return m.Value;
}
public static implicit operator int(ModInt m)
{
return (int)m.Value;
}
public long Raw() => Value;
public override string ToString()
{
return Value.ToString();
}
}
public delegate T Monoid<T>(T a, T b);
public delegate T Apply<T, M>(T x, M m, int len);
// 一点に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(2N)
// 時間計算量:
// - 構築: O(N)
// - 操作: O(logN)
// - クエリ: O(logN)
public sealed class SegmentTree<T> where T : struct
{
private int _treeSize;
private int _dataSize;
private int _originalDataSize;
private T[] _data;
private Monoid<T> _operator;
private Monoid<T> _apply;
private T _identity;
public int OriginalDataSize => _originalDataSize;
public int TreeSize => _treeSize;
public T Identity => _identity;
public T this[int index]
{
get
{
return _data[_dataSize - 1 + index];
}
}
public SegmentTree(int n, Monoid<T> op, Monoid<T> apply, T identity)
{
_originalDataSize = n;
int size = 1;
while (n > size)
{
size <<= 1;
}
_dataSize = size;
_treeSize = 2 * size - 1;
_data = new T[_treeSize];
_identity = identity;
_operator = op;
_apply = apply;
}
public void Build(T[] array)
{
for (int i = 0; i < array.Length; i++)
{
_data[i + _dataSize - 1] = array[i];
}
for (int i = _dataSize - 2; i >= 0; i--)
{
_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
}
}
public void Apply(int index, T value)
{
index += _dataSize - 1;
_data[index] = _apply(_data[index], value);
while (index > 0)
{
index = (index - 1) >> 1;
_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
}
}
public T Query(int left, int right)
{
return QueryRec(left, right, 0, 0, _dataSize);
}
private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
{
if (left >= nodeRight || right <= nodeLeft)
{
return _identity;
}
if (left <= nodeLeft && nodeRight <= right)
{
return _data[index];
}
T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
return _operator(leftChild, rightChild);
}
// 返されたArraySegment<T>は変更してはいけない.
public ArraySegment<T> GetData()
{
return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
}
}
// 区間に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(4N)
// 時間計算量:
// - 構築: O(N)
// - 操作: O(logN)
// - クエリ: O(logN)
// - 一点参照: O(logN)
// operator: クエリに対応する二項演算をする
// mapping: 作用素を作用させる
// composition: 作用素を合成する
public sealed class LazySegmentTree<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>
{
private int _treeSize;
private int _dataSize;
private int _originalDataSize;
private T[] _data;
private M?[] _lazy;
private Monoid<T> _operator;
private Apply<T, M> _mapping;
private Monoid<M> _composition;
private T _identity;
public T this[int index]
{
get
{
return GetByIndex(index);
}
}
public LazySegmentTree(int n, Monoid<T> op, Apply<T, M> mapping, Monoid<M> composition, T identity)
{
_originalDataSize = n;
int size = 1;
while (n > size)
{
size <<= 1;
}
_dataSize = size;
_treeSize = 2 * size - 1;
_data = new T[_treeSize];
_data.AsSpan().Fill(_identity);
_lazy = new M?[_treeSize];
_identity = identity;
_operator = op;
_mapping = mapping;
_composition = composition;
}
public void Build(T[] array)
{
for (int i = 0; i < array.Length; i++)
{
_data[i + _dataSize - 1] = array[i];
}
for (int i = _dataSize - 2; i >= 0; i--)
{
_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
}
}
private void Evaluate(int index, int l, int r)
{
if (_lazy[index] is null)
{
return;
}
if (index < _dataSize - 1)
{
_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
}
_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
_lazy[index] = null;
}
private M GuardComposition(M? a, M? b)
{
if (a is null)
{
return (M)b;
}
else
{
return _composition((M)a, (M)b);
}
}
private void ApplyRec(int a, int b, M m, int index, int l, int r)
{
Evaluate(index, l, r);
if (a <= l && r <= b)
{
_lazy[index] = GuardComposition(_lazy[index], m);
Evaluate(index, l, r);
}
else if (a < r && l < b)
{
ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);
ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);
_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
}
}
public void Apply(int left, int right, M m)
{
ApplyRec(left, right, m, 0, 0, _dataSize);
}
public T Query(int left, int right)
{
return QueryRec(left, right, 0, 0, _dataSize);
}
private T QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
{
Evaluate(index, nodeLeft, nodeRight);
if (left >= nodeRight || right <= nodeLeft)
{
return _identity;
}
if (left <= nodeLeft && nodeRight <= right)
{
return _data[index];
}
T leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
T rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
return _operator(leftChild, rightChild);
}
public T GetByIndex(int target)
{
if (target < 0 || target >= _originalDataSize)
{
throw new Exception("Index is out of range.");
}
return AccessRec(target, 0, 0, _dataSize);
}
private T AccessRec(int target, int index, int l, int r)
{
Evaluate(index, l, r);
if (index >= _dataSize - 1)
{
return _data[index];
}
int mid = (l + r) / 2;
if (target < mid)
{
return AccessRec(target, (index << 1) + 1, l, mid);
}
else
{
return AccessRec(target, (index << 1) + 2, mid, r);
}
}
// index以下のノードをすべて即時に評価する.
private void EvaluateAll(int index, int l, int r)
{
if (_lazy[index] is null)
{
if (index < _dataSize - 1)
{
EvaluateAll((index << 1) + 1, l, (l + r) / 2);
EvaluateAll((index << 1) + 2, (l + r) / 2, r);
}
return;
}
if (index < _dataSize - 1)
{
_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
EvaluateAll((index << 1) + 1, l, (l + r) / 2);
EvaluateAll((index << 1) + 2, (l + r) / 2, r);
}
_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
_lazy[index] = null;
}
// 返されたArraySegment<T>は変更してはいけない.
public ArraySegment<T> GetData()
{
EvaluateAll(0, 0, _dataSize);
return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
}
}
public struct BeatsNode<T> where T : struct, IEquatable<T>
{
public T Value;
public bool Failed;
public BeatsNode(T value)
{
Failed = false;
Value = value;
}
}
// 区間に対する操作と区間に対するクエリを処理する.
// 空間計算量: O(4N)
// 時間計算量:
// - 構築: O(N)
// - 操作: (操作に依存した計算量)
// - クエリ: O(logN)
// operator: クエリに対応する二項演算をする. 必ず計算ができる必要がある.
// mapping: 作用素を作用させる. 計算が出来なければFailed←trueとして返す. この際, 子ノードに対する評価が実行される.
// composition: 作用素を合成する
public sealed class SegmentTreeBeats<T, M> where T : struct, IEquatable<T> where M : struct, IEquatable<M>
{
private int _treeSize;
private int _dataSize;
private int _originalDataSize;
private BeatsNode<T>[] _data;
private M?[] _lazy;
private Monoid<BeatsNode<T>> _operator;
private Apply<BeatsNode<T>, M> _mapping;
private Monoid<M> _composition;
private T _identity;
private BeatsNode<T> _identityNode;
public T this[int index]
{
get{
return GetByIndex(index);
}
}
public SegmentTreeBeats(int n, Monoid<BeatsNode<T>> op, Apply<BeatsNode<T>, M> mapping, Monoid<M> composition, T identity)
{
_originalDataSize = n;
int size = 1;
while (n > size)
{
size <<= 1;
}
_dataSize = size;
_treeSize = 2 * size - 1;
_data = new BeatsNode<T>[_treeSize];
_identityNode = new BeatsNode<T>(_identity);
_data.AsSpan().Fill(_identityNode);
_lazy = new M?[_treeSize];
_identity = identity;
_operator = op;
_mapping = mapping;
_composition = composition;
}
public void Build(T[] array)
{
for (int i = 0; i < array.Length; i++)
{
_data[i + _dataSize - 1] = new BeatsNode<T>(array[i]);
}
for (int i = _dataSize - 2; i >= 0; i--)
{
_data[i] = _operator(_data[(i << 1) + 1], _data[(i << 1) + 2]);
}
}
private void Evaluate(int index, int l, int r)
{
if (_lazy[index] is null)
{
return;
}
if (index < _dataSize - 1)
{
//_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
//_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
if (_lazy[(index << 1) + 1] is not null)
{
Evaluate((index << 1) + 1, l, (l + r) / 2);
}
_lazy[(index << 1) + 1] = _lazy[index];
if (_lazy[(index << 1) + 2] is not null)
{
Evaluate((index << 1) + 2, (l + r) / 2, r);
}
_lazy[(index << 1) + 2] = _lazy[index];
}
//_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
// 計算してみる
BeatsNode<T> val = _mapping(_data[index], (M)_lazy[index], r - l);
// 計算出来なければ
if (val.Failed)
{
if (index >= _dataSize - 1)
{
throw new Exception("葉ノードに対するmappingは失敗してはいけません");
}
// 子ノードを即評価
Evaluate((index << 1) + 1, l, (l + r) / 2);
Evaluate((index << 1) + 2, (l + r) / 2, r);
// 子ノードの結果から親を更新
_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
}
else
{
// 計算できればそのまま更新
_data[index] = val;
}
_lazy[index] = null;
}
private M GuardComposition(M? a, M? b)
{
if (a is null)
{
return (M)b;
}
else
{
return _composition((M)a, (M)b);
}
}
private void ApplyRec(int a, int b, M m, int index, int l, int r)
{
Evaluate(index, l, r);
if (a <= l && r <= b)
{
_lazy[index] = GuardComposition(_lazy[index], m);
Evaluate(index, l, r);
}
else if (a < r && l < b)
{
ApplyRec(a, b, m, (index << 1) + 1, l, (l + r) / 2);
ApplyRec(a, b, m, (index << 1) + 2, (l + r) / 2, r);
_data[index] = _operator(_data[(index << 1) + 1], _data[(index << 1) + 2]);
}
}
public void Apply(int left, int right, M m)
{
ApplyRec(left, right, m, 0, 0, _dataSize);
}
public T Query(int left, int right)
{
return QueryRec(left, right, 0, 0, _dataSize).Value;
}
private BeatsNode<T> QueryRec(int left, int right, int index, int nodeLeft, int nodeRight)
{
Evaluate(index, nodeLeft, nodeRight);
if (left >= nodeRight || right <= nodeLeft)
{
return _identityNode;
}
if (left <= nodeLeft && nodeRight <= right)
{
return _data[index];
}
BeatsNode<T> leftChild = QueryRec(left, right, (index << 1) + 1, nodeLeft, (nodeLeft + nodeRight) >> 1);
BeatsNode<T> rightChild = QueryRec(left, right, (index << 1) + 2, (nodeLeft + nodeRight) >> 1, nodeRight);
return _operator(leftChild, rightChild);
}
public T GetByIndex(int target)
{
if (target < 0 || target >= _originalDataSize)
{
throw new Exception("Index is out of range.");
}
return AccessRec(target, 0, 0, _dataSize);
}
private T AccessRec(int target, int index, int l, int r)
{
Evaluate(index, l, r);
if (index >= _dataSize - 1)
{
return _data[index].Value;
}
int mid = (l + r) / 2;
if (target < mid)
{
return AccessRec(target, (index << 1) + 1, l, mid);
}
else
{
return AccessRec(target, (index << 1) + 2, mid, r);
}
}
// index以下のノードをすべて即時に評価する.
private void EvaluateAll(int index, int l, int r)
{
if (_lazy[index] is null)
{
if (index < _dataSize - 1)
{
EvaluateAll((index << 1) + 1, l, (l + r) / 2);
EvaluateAll((index << 1) + 2, (l + r) / 2, r);
}
return;
}
if (index < _dataSize - 1)
{
//_lazy[(index << 1) + 1] = GuardComposition(_lazy[(index << 1) + 1], _lazy[index]);
//_lazy[(index << 1) + 2] = GuardComposition(_lazy[(index << 1) + 2], _lazy[index]);
if (_lazy[(index << 1) + 1] is not null)
{
Evaluate((index << 1) + 1, l, (l + r) / 2);
}
_lazy[(index << 1) + 1] = _lazy[index];
if (_lazy[(index << 1) + 2] is not null)
{
Evaluate((index << 1) + 2, (l + r) / 2, r);
}
_lazy[(index << 1) + 2] = _lazy[index];
EvaluateAll((index << 1) + 1, l, (l + r) / 2);
EvaluateAll((index << 1) + 2, (l + r) / 2, r);
}
_data[index] = _mapping(_data[index], (M)_lazy[index], r - l);
_lazy[index] = null;
}
// 返されたArraySegment<T>は変更してはいけない.
public void GetData(T[] destination)
{
if (destination.Length < _originalDataSize)
{
throw new Exception("書き込み先配列の大きさが足りない");
}
EvaluateAll(0, 0, _dataSize);
//return new ArraySegment<T>(_data, _dataSize - 1, _originalDataSize);
for (int i = 0; i < _originalDataSize; i++)
{
destination[i] = _data[_dataSize - 1 + i].Value;
}
}
}
public struct ChangeNode<T> : IEquatable<ChangeNode<T>> where T : struct, INumber<T>, IMinMaxValue<T>
{
public T Max;
public int MaxCount;
public T SecondMax;
public T Min;
public int MinCount;
public T SecondMin;
public T Sum;
public bool Equals(ChangeNode<T> other)
{
return this.Equals(other);
}
public static ChangeNode<R> MakeLeaf<R>(R value) where R : struct, INumber<R>, IMinMaxValue<R>
{
return new ChangeNode<R>()
{
Max = value,
MaxCount = 1,
SecondMax = R.MinValue,
Min = value,
MinCount = 1,
SecondMin = R.MaxValue,
Sum = value
};
}
}
public static class SegmentTreeBuilder
{
public static LazySegmentTree<T, T> RangeAddMax<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, T.Max,
(x, m, l) =>
{
return x + m;
},
(a, b) => { return a + b; },
identity);
}
public static LazySegmentTree<T, T> RangeUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, T.Max,
(x, m, l) =>
{
return m;
},
(x, y) => { return y; },
identity);
}
public static LazySegmentTree<T, T> RangeAddMin<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, T.Min,
(x, m, l) =>
{
return x + m;
},
(a, b) => { return a + b; },
identity);
}
public static LazySegmentTree<T, T> RangeUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, T.Min,
(x, m, l) =>
{
return m;
},
(x, y) => { return y; },
identity);
}
public static LazySegmentTree<T, T> RangeAddSum<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, (x, y) => x + y,
(x, m, l) =>
{
return x + m * T.CreateChecked(l);
},
(a, b) => { return a + b; },
identity);
}
public static LazySegmentTree<T, T> RangeUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
{
return new LazySegmentTree<T, T>(n, (x, y) => x + y,
(x, m, l) =>
{
return m * T.CreateChecked(l);
},
(a, b) => { return b; },
identity);
}
public static SegmentTree<T> PointUpdateMax<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, T.Max, (a, b) => b, identity);
}
public static SegmentTree<T> PointAddMax<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, T.Max, (a, b) => a + b, identity);
}
public static SegmentTree<T> PointUpdateMin<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, T.Min, (a, b) => b, identity);
}
public static SegmentTree<T> PointAddMin<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, T.Min, (a, b) => a + b, identity);
}
public static SegmentTree<T> PointUpdateSum<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => b, identity);
}
public static SegmentTree<T> PointAddSum<T>(int n, T identity) where T : struct, INumber<T>
{
return new SegmentTree<T>(n, (x, y) => x + y, (a, b) => a + b, identity);
}
}
public sealed class PrefixSum2D<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>
{
private T[,] _sums;
public PrefixSum2D(T[,] sequence)
{
int height = sequence.GetLength(0);
int width = sequence.GetLength(1);
_sums = new T[height + 1, width + 1];
// build prefix sum
for (int y = 0; y < height; y++)
{
for (int x = 0; x < width; x++)
{
_sums[y + 1, x + 1] = _sums[y + 1, x] + _sums[y, x + 1] - _sums[y, x] + sequence[y, x];
}
}
}
public T Sum(int startInclX, int startInclY, int endExclX, int endExclY)
{
return _sums[endExclY, endExclX] + _sums[startInclY, startInclX] - _sums[startInclY, endExclX] - _sums[endExclY, startInclX];
}
public T AllSum()
{
return _sums[_sums.GetLength(0) - 1, _sums.GetLength(1) - 1];
}
}
public sealed class PrefixSum<T> where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T>
{
private T[] _sums;
public PrefixSum(T[] sequence)
{
_sums = new T[sequence.Length + 1];
_sums[0] = T.AdditiveIdentity;
for (int i = 0; i < sequence.Length; i++)
{
_sums[i + 1] = _sums[i] + sequence[i];
}
}
// [a, b)
public T Sum(int aIncl, int bExcl)
{
return _sums[bExcl] - _sums[aIncl];
}
public T AllSum()
{
return _sums[^1];
}
public T[] GetArray()
{
return _sums;
}
}
public sealed class UnionFind
{
private int[] _parents;
private int[] _size;
private int _vertexCount;
public int VertexCount => _vertexCount;
public UnionFind(int n)
{
_vertexCount = n;
_parents = new int[n];
_size = new int[n];
for (int i = 0; i < n; i++)
{
_parents[i] = i;
_size[i] = 1;
}
}
public int Root(int x)
{
if (_parents[x] == x)
return x;
return _parents[x] = Root(_parents[x]);
}
public void Unite(int x, int y)
{
int rootX = Root(x);
int rootY = Root(y);
if (rootX == rootY)
return;
int from = rootX;
int to = rootY;
// merge from to to
if (_size[from] > _size[to])
{
(from, to) = (to, from);
}
_size[to] += _size[from];
_parents[from] = to;
}
public List<int> Find(int x)
{
int rootX = Root(x);
List<int> set = new List<int>();
for (int i = 0; i < _vertexCount; i++)
{
if (Root(i) == rootX)
set.Add(i);
}
return set;
}
public Dictionary<int, List<int>> FindAll()
{
Dictionary<int, List<int>> sets = new Dictionary<int, List<int>>();
for (int i = 0; i < _vertexCount; i++)
{
int root = Root(i);
if (sets.ContainsKey(root))
sets[root].Add(i);
else
sets[root] = new List<int>() { i };
}
return sets;
}
public bool Same(int x, int y)
{
int rootX = Root(x);
int rootY = Root(y);
return rootX == rootY;
}
public int Size(int v)
{
return _size[Root(v)];
}
public void Clear()
{
for (int i = 0; i < _vertexCount; i++)
{
_parents[i] = i;
}
}
}