結果
| 問題 | No.2361 Many String Compare Queries |
| ユーザー |
 KumaTachiRen
|
| 提出日時 | 2023-06-23 23:11:13 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 25,156 bytes |
| コンパイル時間 | 10,643 ms |
| コンパイル使用メモリ | 169,104 KB |
| 実行使用メモリ | 210,040 KB |
| 最終ジャッジ日時 | 2024-07-01 02:57:51 |
| 合計ジャッジ時間 | 14,932 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 58 ms
28,944 KB |
| testcase_01 | AC | 58 ms
29,312 KB |
| testcase_02 | AC | 58 ms
28,800 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | AC | 59 ms
29,036 KB |
| testcase_06 | WA | - |
| testcase_07 | AC | 60 ms
29,056 KB |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | AC | 264 ms
51,340 KB |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (94 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.ComponentModel;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Text;
using static Functions;
using ModInt = StaticModInt<Mod998244353>;
static class Program
{
static public void Main(string[] args)
{
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
new Solver();
Console.Out.Flush();
}
}
public class Solver
{
public Solver()
{
Solve();
}
void Solve()
{
int n = ri, q = ri;
var s = rs;
var sa = StringLib.SuffixArray(s);
var lcp = StringLib.LCPArray(s, sa);
var idx = new int[n];
for (int i = 0; i < n; i++) idx[sa[i]] = i;
var lr = new List<(int i, int l, int r, int sal)>();
for (int i = 0; i < q; i++)
{
int l = ri - 1, r = ri;
lr.Add((i, l, r, idx[l]));
}
lr.Sort((p1, p2) => p1.sal - p2.sal);
var ans = new long[q];
var st = new Stack<(int l, long v, long c)>();
int qidx = 0;
var bits = new BinaryIndexedTree<long, Op>(n + 1);
var bitc = new BinaryIndexedTree<long, Op>(n + 1);
for (int i = 0; i < n; i++)
{
if (i > 0)
{
int l = lcp[i - 1];
long v = 0;
long c = 0;
while (st.Count > 0 && st.Peek().l >= l)
{
var (tl, tv, tc) = st.Pop();
bits.Add(tl, -tv);
bitc.Add(tl, -tc);
v += tv;
c += tc;
}
if (c > 0)
{
st.Push((l, v, c));
bits.Add(l, v);
bitc.Add(l, c);
}
}
st.Push((n - sa[i], n - sa[i], 1));
bits.Add(n - sa[i], n - sa[i]);
bitc.Add(n - sa[i], 1);
while (qidx < q && lr[qidx].sal == i)
{
int d = lr[qidx].r - lr[qidx].l;
ans[lr[qidx].i] = bits.Sum(d) + bitc.Sum(d, n + 1) * (d - 1);
qidx++;
}
}
WriteJoin("\n", ans);
}
struct Op : IBinaryIndexedTreeOperator<long>
{
public long Identity => 0;
public long Addition(long x, long y) => x + y;
public long Subtract(long x, long y) => x - y;
}
const long INF = 1L << 60;
int ri { get { return (int)sc.Integer(); } }
long rl { get { return sc.Integer(); } }
ulong rul { get { return sc.UInteger(); } }
double rd { get { return sc.Double(); } }
string rs { get { return sc.Scan(); } }
string rline { get { return sc.Line(); } }
public StreamScanner sc = new StreamScanner(Console.OpenStandardInput());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
T[] RepArray<T>(T t, int count) => Enumerable.Repeat(t, count).ToArray();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void WriteJoin<T>(string s, IEnumerable<T> t) => Console.WriteLine(string.Join(s, t));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void WriteMat<T>(T[,] a)
{
int sz1 = a.GetLength(0);
int sz2 = a.GetLength(1);
for (int i = 0; i < sz1; i++)
{
var s = new List<string>();
for (int j = 0; j < sz2; j++) s.Add(a[i, j].ToString());
WriteJoin(" ", s);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(object t) => Console.WriteLine(t.ToString());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(string str) => Console.WriteLine(str);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(string str, object arg1) => Console.WriteLine(str, arg1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(string str, object arg1, object arg2) => Console.WriteLine(str, arg1, arg2);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(string str, object arg1, object arg2, object arg3) => Console.WriteLine(str, arg1, arg2, arg3);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Write(string str, params object[] arg) => Console.WriteLine(str, arg);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void WriteFlush(object t)
{ Console.WriteLine(t.ToString()); Console.Out.Flush(); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void WriteError(object t) => Console.Error.WriteLine(t.ToString());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void YN(bool t) => Console.WriteLine(t ? "YES" : "NO");
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Yn(bool t) => Console.WriteLine(t ? "Yes" : "No");
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void yn(bool t) => Console.WriteLine(t ? "yes" : "no");
}
public interface IStaticMod
{
uint Mod { get; }
bool IsPrime { get; }
}
public readonly struct Mod1000000007 : IStaticMod
{
public uint Mod => 1000000007;
public bool IsPrime => true;
}
public readonly struct Mod998244353 : IStaticMod
{
public uint Mod => 998244353;
public bool IsPrime => true;
}
public readonly struct StaticModInt<T> : IEquatable<StaticModInt<T>>, IFormattable where T : struct, IStaticMod
{
internal readonly uint _v;
private static readonly T op = default;
public int Value => (int)_v;
public static int Mod => (int)op.Mod;
public static StaticModInt<T> Zero => default;
public static StaticModInt<T> One => new StaticModInt<T>(1u);
[MethodImpl(256)]
public static StaticModInt<T> Raw(int v)
{
var u = unchecked((uint)v);
return new StaticModInt<T>(u);
}
[MethodImpl(256)]
public StaticModInt(long v) : this(Round(v)) { }
[MethodImpl(256)]
public StaticModInt(ulong v) : this((uint)(v % op.Mod)) { }
[MethodImpl(256)]
private StaticModInt(uint v) => _v = v;
[MethodImpl(256)]
private static uint Round(long v)
{
var x = v % op.Mod;
if (x < 0) x += op.Mod;
return (uint)x;
}
[MethodImpl(256)]
public static StaticModInt<T> operator ++(StaticModInt<T> v)
{
var x = v._v + 1;
if (x == op.Mod) x = 0;
return new StaticModInt<T>(x);
}
[MethodImpl(256)]
public static StaticModInt<T> operator --(StaticModInt<T> v)
{
var x = v._v;
if (x == 0) x = op.Mod;
return new StaticModInt<T>(x - 1);
}
[MethodImpl(256)]
public static StaticModInt<T> operator +(StaticModInt<T> lhs, StaticModInt<T> rhs)
{
var v = lhs._v + rhs._v;
if (v >= op.Mod) v -= op.Mod;
return new StaticModInt<T>(v);
}
[MethodImpl(256)]
public static StaticModInt<T> operator -(StaticModInt<T> lhs, StaticModInt<T> rhs)
{
unchecked
{
var v = lhs._v - rhs._v;
if (v >= op.Mod) v += op.Mod;
return new StaticModInt<T>(v);
}
}
[MethodImpl(256)]
public static StaticModInt<T> operator *(StaticModInt<T> lhs, StaticModInt<T> rhs) => new StaticModInt<T>((uint)((ulong)lhs._v * rhs._v % op.Mod));
[MethodImpl(256)]
public static StaticModInt<T> operator /(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs * rhs.Inv();
[MethodImpl(256)]
public static StaticModInt<T> operator +(StaticModInt<T> v) => v;
[MethodImpl(256)]
public static StaticModInt<T> operator -(StaticModInt<T> v) => new StaticModInt<T>(v._v == 0 ? 0 : op.Mod - v._v);
[MethodImpl(256)]
public static bool operator ==(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs._v == rhs._v;
[MethodImpl(256)]
public static bool operator !=(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs._v != rhs._v;
[MethodImpl(256)]
public static implicit operator StaticModInt<T>(int v) => new StaticModInt<T>(v);
[MethodImpl(256)]
public static implicit operator StaticModInt<T>(uint v) => new StaticModInt<T>((long)v);
[MethodImpl(256)]
public static implicit operator StaticModInt<T>(long v) => new StaticModInt<T>(v);
[MethodImpl(256)]
public static implicit operator StaticModInt<T>(ulong v) => new StaticModInt<T>(v);
[MethodImpl(256)]
public static implicit operator long(StaticModInt<T> v) => v._v;
[MethodImpl(256)]
public static implicit operator ulong(StaticModInt<T> v) => v._v;
[MethodImpl(256)]
public StaticModInt<T> Pow(long n)
{
var x = this;
var r = new StaticModInt<T>(1U);
while (n > 0)
{
if ((n & 1) > 0) r *= x;
x *= x;
n >>= 1;
}
return r;
}
[MethodImpl(256)]
public StaticModInt<T> Inv()
{
var (x, y, g) = ExtGcd(_v, op.Mod);
return new StaticModInt<T>(x);
}
[MethodImpl(256)]
static (long x, long y, long g) ExtGcd(long a, long b)
{
if (b == 0) return a >= 0 ? (1, 0, a) : (-1, 0, -a);
long c = SafeMod(a, b);
var (x2, y2, g) = ExtGcd(b, c);
long x = SafeMod(y2, b);
long y = (g - a * x) / b;
return (x, y, g);
}
[MethodImpl(256)]
static long SafeMod(long x, long m)
{
long r = x % m;
if (r < 0) r += m;
return r;
}
[MethodImpl(256)]
public override string ToString() => _v.ToString();
[MethodImpl(256)]
public string ToString(string format, IFormatProvider formatProvider) => _v.ToString(format, formatProvider);
[MethodImpl(256)]
public override bool Equals(object obj) => obj is StaticModInt<T> m && Equals(m);
[MethodImpl(256)]
public bool Equals(StaticModInt<T> other) => _v == other._v;
[MethodImpl(256)]
public override int GetHashCode() => _v.GetHashCode();
}
public static class Functions
{
[MethodImpl(256)]
public static int Popcount(ulong x)
{
x = (x & 0x5555555555555555UL) + ((x >> 1) & 0x5555555555555555UL);
x = (x & 0x3333333333333333UL) + ((x >> 2) & 0x3333333333333333UL);
x = (x & 0x0f0f0f0f0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0f0f0f0f0fUL);
x = (x & 0x00ff00ff00ff00ffUL) + ((x >> 8) & 0x00ff00ff00ff00ffUL);
x = (x & 0x0000ffff0000ffffUL) + ((x >> 16) & 0x0000ffff0000ffffUL);
x = (x & 0x00000000ffffffffUL) + ((x >> 32) & 0x00000000ffffffffUL);
return (int)x;
}
[MethodImpl(256)]
public static int Popcount(int x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff);
return x;
}
[MethodImpl(256)]
public static int Ctz(long x)
{
if (x == 0) return -1;
return Popcount((ulong)((x & -x) - 1));
}
[MethodImpl(256)]
public static int CeilPow2(int n)
{
int x = 0;
while ((1 << x) < n) x++;
return x;
}
[MethodImpl(256)]
public static int SafeMod(int x, int m)
{
int r = x % m;
return r < 0 ? r + Math.Abs(m) : r;
}
[MethodImpl(256)]
public static long SafeMod(long x, long m)
{
long r = x % m;
return r < 0 ? r + Math.Abs(m) : r;
}
[MethodImpl(256)] public static int Sign(long x) => x == 0 ? 0 : (x < 0 ? -1 : 1);
[MethodImpl(256)] public static int Sign(double x) => x == 0 ? 0 : (x < 0 ? -1 : 1);
[MethodImpl(256)] public static int DigitSum(long n, int d = 10) { long s = 0; while (n > 0) { s += n % d; n /= d; } return (int)s; }
[MethodImpl(256)] public static long Floor(long a, long b) => a >= 0 ? a / b : (a + 1) / b - 1;
[MethodImpl(256)] public static long Ceil(long a, long b) => a > 0 ? (a - 1) / b + 1 : a / b;
[MethodImpl(256)] public static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);
[MethodImpl(256)] public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
[MethodImpl(256)] public static void Swap(ref int x, ref int y) { x ^= y; y ^= x; x ^= y; }
[MethodImpl(256)] public static void Swap(ref long x, ref long y) { x ^= y; y ^= x; x ^= y; }
[MethodImpl(256)] public static void Swap<T>(ref T x, ref T y) { T t = y; y = x; x = t; }
[MethodImpl(256)] public static T Clamp<T>(T x, T l, T r) where T : IComparable<T> => x.CompareTo(l) <= 0 ? l : (x.CompareTo(r) <= 0 ? x : r);
[MethodImpl(256)] public static T Clamp<T>(ref T x, T l, T r) where T : IComparable<T> => x = x.CompareTo(l) <= 0 ? l : (x.CompareTo(r) <= 0 ? x : r);
[MethodImpl(256)] public static void Chmin<T>(ref T x, T y) where T : IComparable<T> { if (x.CompareTo(y) > 0) x = y; }
[MethodImpl(256)] public static void Chmax<T>(ref T x, T y) where T : IComparable<T> { if (x.CompareTo(y) < 0) x = y; }
public static int LowerBound(int[] arr, int val, int l = -1, int r = -1) => LowerBound<int>(arr.AsSpan(), t => t - val, l, r);
public static int LowerBound<T>(T[] arr, Func<T, int> comp, int l = -1, int r = -1) => LowerBound<T>(arr.AsSpan<T>(), comp, l, r);
public static int LowerBound<T>(Span<T> data, Func<T, int> comp, int l = -1, int r = -1)
{
if (data.Length == 0) return -1;
if (l == -1) l = 0;
if (r == -1) r = data.Length;
while (l < r)
{
int x = (l + r) / 2;
if (comp(data[x]) < 0) l = x + 1;
else r = x;
}
return l;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string ToBase2(long v, int digit = -1)
{
if (digit == -1)
{
digit = 0;
while ((v >> digit) > 0) digit++;
}
var c = new string[digit];
for (int i = 0; i < digit; i++) c[digit - 1 - i] = ((v >> i) & 1) == 0 ? "0" : "1";
return string.Join("", c);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static string ToBaseN(long v, int n, int digit = -1)
{
if (digit == -1)
{
digit = 0;
long pow = 1;
while (v >= pow) { digit++; pow *= n; }
}
var c = new int[digit];
for (int i = 0; i < digit; i++, v /= n) c[digit - 1 - i] = (int)(v % n);
return string.Join("", c);
}
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
private readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) throw new EndOfStreamException();
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; }
}
return buf[ptr++];
}
public char Char()
{
byte b = 0;
do b = read();
while (b < 33 || 126 < b);
return (char)b;
}
public string Line()
{
var sb = new StringBuilder();
for (var b = Char(); b != 10 && !isEof; b = (char)read()) sb.Append(b);
return sb.ToString();
}
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
return sb.ToString();
}
public long Integer()
{
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b) return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public ulong UInteger()
{
ulong ret = 0; byte b = 0;
do b = read();
while (b < '0' || '9' < b);
for (; true; b = read())
{
if (b < '0' || '9' < b) return ret;
else ret = ret * 10 + b - '0';
}
}
public double Double() { return double.Parse(Scan()); }
}
public static partial class StringLib
{
private static int[] SA_Naive(int[] s)
{
int n = s.Length;
var sa = new List<int>();
for (int i = 0; i < n; i++) sa.Add(i);
sa.Sort((l, r) =>
{
if (l == r) return 0;
while (l < n && r < n)
{
if (s[l] != s[r]) return s[l] - s[r];
l++; r++;
}
return -(l - r);
});
return sa.ToArray();
}
private static int[] SA_Doubling(ReadOnlySpan<int> s)
{
int n = s.Length;
var sa = new int[n];
for (int i = 0; i < n; i++) sa[i] = i;
var rnk = s.ToArray();
var tmp = new int[n];
for (int k = 1; k < n; k *= 2)
{
Comparison<int> cmp = (int x, int y) =>
{
if (rnk[x] != rnk[y]) return rnk[x] - rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx - ry;
};
Array.Sort(sa, (x, y) => cmp(x, y));
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
{
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) < 0 ? 1 : 0);
}
for (int i = 0; i < n; i++)
{
var t = tmp[i];
tmp[i] = rnk[i];
rnk[i] = t;
}
}
return sa;
}
private static int[] SA_IS(ReadOnlySpan<int> s, int upper, int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40)
{
int n = s.Length;
if (n == 0) return new int[0];
if (n == 1) return new int[1] { 0 };
if (n == 2)
{
if (s[0] < s[1]) return new int[] { 0, 1 };
else return new int[] { 1, 0 };
}
if (n < THRESHOLD_NAIVE) return SA_Naive(s.ToArray());
if (n < THRESHOLD_DOUBLING) return SA_Doubling(s);
var sa = new int[n];
var ls = new bool[n];
for (int i = n - 2; i >= 0; i--)
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
var sum_l = new int[upper + 1];
var sum_s = new int[upper + 1];
for (int i = 0; i < n; i++)
{
if (!ls[i]) sum_s[s[i]]++;
else sum_l[s[i] + 1]++;
}
for (int i = 0; i <= upper; i++)
{
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
var lms_map = new int[n + 1];
for (int i = 0; i < lms_map.Length; i++) lms_map[i] = -1;
int m = 0;
for (int i = 1; i < n; i++)
if (!ls[i - 1] && ls[i]) lms_map[i] = m++;
var lms = new List<int>();
for (int i = 1; i < n; i++)
if (!ls[i - 1] && ls[i]) lms.Add(i);
{
for (int i = 0; i < sa.Length; i++) sa[i] = -1;
var buf = (int[])sum_s.Clone();
foreach (var d in lms)
{
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
buf = (int[])sum_l.Clone();
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++)
{
int v = sa[i];
if (v >= 1 && !ls[v - 1])
{
sa[buf[s[v - 1]]++] = v - 1;
}
}
buf = (int[])sum_l.Clone();
for (int i = n - 1; i >= 0; i--)
{
int v = sa[i];
if (v >= 1 && ls[v - 1])
{
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
}
if (m > 0)
{
var sorted_lms = new List<int>();
foreach (int v in sa) if (lms_map[v] != -1) sorted_lms.Add(v);
var rec_s = new int[m];
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++)
{
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) same = false;
else
{
while (l < end_l)
{
if (s[l] != s[r]) break;
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
var rec_sa = SA_IS(rec_s, rec_upper);
for (int i = 0; i < m; i++) sorted_lms[i] = lms[rec_sa[i]];
{
for (int i = 0; i < sa.Length; i++) sa[i] = -1;
var buf = (int[])sum_s.Clone();
foreach (var d in sorted_lms)
{
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
buf = (int[])sum_l.Clone();
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++)
{
int v = sa[i];
if (v >= 1 && !ls[v - 1])
{
sa[buf[s[v - 1]]++] = v - 1;
}
}
buf = (int[])sum_l.Clone();
for (int i = n - 1; i >= 0; i--)
{
int v = sa[i];
if (v >= 1 && ls[v - 1])
{
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
}
}
return sa;
}
public static int[] SuffixArray(ReadOnlySpan<int> s, int upper) => SA_IS(s, upper);
public static int[] SuffixArray<T>(ReadOnlySpan<T> s) where T : IComparable<T>
{
var comp = Comparer<T>.Default;
int n = s.Length;
var idx = new (int i, T v)[n];
for (int i = 0; i < n; i++) idx[i] = (i, s[i]);
Array.Sort(idx, (l, r) => comp.Compare(l.v, r.v));
var s2 = new int[n];
int now = 0;
for (int i = 0; i < n; i++)
{
if (i > 0 && comp.Compare(idx[i - 1].v, idx[i].v) != 0) now++;
s2[idx[i].i] = now;
}
return SA_IS(s2, now);
}
public static int[] SuffixArray(string s)
{
int n = s.Length;
var s2 = new int[n];
for (int i = 0; i < n; i++) s2[i] = s[i];
return SA_IS(s2, 255);
}
}
public static partial class StringLib
{
public static int[] LCPArray<T>(ReadOnlySpan<T> s, ReadOnlySpan<int> sa) where T : IEquatable<T>
{
var comp = EqualityComparer<T>.Default;
int n = s.Length;
var rnk = new int[n];
for (int i = 0; i < n; i++) rnk[sa[i]] = i;
var lcp = new int[n];
Array.Fill(lcp, -1);
int h = 0;
for (int i = 0; i < n; i++)
{
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++)
if (!comp.Equals(s[j + h], s[i + h])) break;
lcp[rnk[i] - 1] = h;
}
return lcp;
}
public static int[] LCPArray(string s, ReadOnlySpan<int> sa) => LCPArray<char>(s.AsSpan(), sa);
}
public interface IBinaryIndexedTreeOperator<T>
{
T Identity { get; }
T Addition(T x, T y);
T Subtract(T x, T y);
}
class BinaryIndexedTree<T, Op> where Op : IBinaryIndexedTreeOperator<T>
{
private static readonly Op op = default;
public int Length { get; }
public readonly T[] data;
public BinaryIndexedTree(int n)
{
Length = n;
data = new T[Length + 1];
Array.Fill(data, op.Identity);
}
[MethodImpl(256)]
public void Add(int p, T x)
{
for (p++; p < data.Length; p += p & -p) data[p] = op.Addition(data[p], x);
}
[MethodImpl(256)]
public T Sum(int l, int r) => op.Subtract(Sum(r), Sum(l));
[MethodImpl(256)]
public T Sum(int x)
{
T s = op.Identity;
for (; x > 0; x -= x & -x) s = op.Addition(s, data[x]);
return s;
}
[MethodImpl(256)]
public int LowerBound(Func<T, bool> cond)
{
if (cond(op.Identity)) return 0;
int x = 0, r = 1;
while (r < Length) r = r << 1;
T s = op.Identity;
for (int len = r; len > 0; len >>= 1)
{
if (x + len < Length && !cond(op.Addition(s, data[x + len])))
{
s = op.Addition(s, data[x + len]);
x += len;
}
}
return x + 1;
}
}