結果
問題 | No.2250 Split Permutation |
ユーザー |
![]() |
提出日時 | 2023-03-17 21:47:19 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 1,474 ms / 3,000 ms |
コード長 | 34,340 bytes |
コンパイル時間 | 8,335 ms |
コンパイル使用メモリ | 168,632 KB |
実行使用メモリ | 206,740 KB |
最終ジャッジ日時 | 2024-09-18 10:37:13 |
合計ジャッジ時間 | 23,682 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (97 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.Collections.Generic;using System.IO;using System.Linq;using static System.Math;using System.Text;using System.Threading;using System.Globalization;using System.Runtime.CompilerServices;using System.Runtime.InteropServices;using Library;namespace Program{public static class ProblemD{static bool SAIKI = false;static public int numberOfRandomCases = 0;static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker){}static public void Solve(){var N = NN;var PList = NNList(N);var seg = new LIB_RedBlackTree<long, LIB_Mod998244353, LIB_Mod998244353>(0, 1, (x, y) => x + y, (x, y, c) => x * y, (x, y) => x * y);var allpat = LIB_Mod998244353.Pow(2, N - 1);LIB_Mod998244353 ans = 0;foreach (var item in PList){var idx = seg.LowerBound(item);ans -= seg.Query(idx, seg.Count) * allpat;ans += allpat * (seg.Count - idx);seg.Add(item, 1);seg.Update(0, seg.Count, (LIB_Mod998244353)1 / 2);}Console.WriteLine(ans);}class Printer : StreamWriter{public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }}static LIB_FastIO fastio = new LIB_FastIODebug();static string[] args;static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); }static long NN => fastio.Long();static double ND => fastio.Double();static string NS => fastio.Scan();static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift);static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e);static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector);static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e);static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector);static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase);static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase);static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase);static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase);static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x);static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }static IEnumerator<uint> _xsi = _xsc();static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true){ var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } returnfalse; }static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } returnfalse; }static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value);static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value);static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value);static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value);}}namespace Library {partial struct LIB_Mod998244353 : IEquatable<LIB_Mod998244353>, IEquatable<long>{const int _mod = 998244353; long v;[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_Mod998244353(long x){if (x < _mod && x >= 0) v = x;else if ((v = x % _mod) < 0) v += _mod;}[MethodImpl(MethodImplOptions.AggressiveInlining)]static public implicit operator LIB_Mod998244353(long x) => new LIB_Mod998244353(x);[MethodImpl(MethodImplOptions.AggressiveInlining)]static public implicit operator long(LIB_Mod998244353 x) => x.v;[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(LIB_Mod998244353 x) { if ((v += x.v) >= _mod) v -= _mod; }[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Sub(LIB_Mod998244353 x) { if ((v -= x.v) < 0) v += _mod; }[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Mul(LIB_Mod998244353 x) => v = (v * x.v) % _mod;[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Div(LIB_Mod998244353 x) => v = (v * Inverse(x.v)) % _mod;[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 operator +(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v + y.v; return t >= _mod ? newLIB_Mod998244353 { v = t - _mod } : new LIB_Mod998244353 { v = t }; }[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 operator -(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v - y.v; return t < 0 ? new LIB_Mod998244353 {v = t + _mod } : new LIB_Mod998244353 { v = t }; }[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 operator *(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * y.v;[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 operator /(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * Inverse(y.v);[MethodImpl(MethodImplOptions.AggressiveInlining)]static public bool operator ==(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v == y.v;[MethodImpl(MethodImplOptions.AggressiveInlining)]static public bool operator !=(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v != y.v;[MethodImpl(MethodImplOptions.AggressiveInlining)]static public long Inverse(long x){long b = _mod, r = 1, u = 0, t = 0;while (b > 0){var q = x / b;t = u;u = r - q * u;r = t;t = b;b = x - q * b;x = t;}return r < 0 ? r + _mod : r;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool Equals(LIB_Mod998244353 x) => v == x.v;[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool Equals(long x) => v == x;[MethodImpl(MethodImplOptions.AggressiveInlining)]public override bool Equals(object x) => x == null ? false : Equals((LIB_Mod998244353)x);[MethodImpl(MethodImplOptions.AggressiveInlining)]public override int GetHashCode() => v.GetHashCode();[MethodImpl(MethodImplOptions.AggressiveInlining)]public override string ToString() => v.ToString();static List<LIB_Mod998244353> _fact = new List<LIB_Mod998244353>() { 1, 1 };static List<LIB_Mod998244353> _inv = new List<LIB_Mod998244353>() { 0, 1 };static List<LIB_Mod998244353> _factinv = new List<LIB_Mod998244353>() { 1, 1 };static long _factm = _mod;[MethodImpl(MethodImplOptions.AggressiveInlining)]static void B(long n){if (_factm != _mod){_fact = new List<LIB_Mod998244353>() { 1, 1 };_inv = new List<LIB_Mod998244353>() { 0, 1 };_factinv = new List<LIB_Mod998244353>() { 1, 1 };}if (n >= _fact.Count){for (int i = _fact.Count; i <= n; ++i){_fact.Add(_fact[i - 1] * i);_inv.Add(_mod - _inv[(int)(_mod % i)] * (_mod / i));_factinv.Add(_factinv[i - 1] * _inv[i]);}}_factm = _mod;}[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 Comb(long n, long k){B(n);if (n == 0 && k == 0) return 1;if (n < k || n < 0) return 0;return _fact[(int)n] * _factinv[(int)(n - k)] * _factinv[(int)k];}[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 CombOK(long n, long k){LIB_Mod998244353 ret = 1;LIB_Mod998244353 deno = 1;var chk = n - k;if (chk < k) k = chk;for (var i = 0; i < k; i++) ret *= n - i;for (var i = 1; i <= k; i++) deno *= i;return ret / deno;}[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 Perm(long n, long k){B(n);if (n == 0 && k == 0) return 1;if (n < k || n < 0) return 0;return _fact[(int)n] * _factinv[(int)(n - k)];}[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 KanzenPerm(long n, long k) => Enumerable.Range(0, (int)k + 1).Aggregate((LIB_Mod998244353)0, (a, e) => a + (1- ((e & 1) << 1)) * LIB_Mod998244353.Comb(k, e) * LIB_Mod998244353.Perm(n - e, k - e));[MethodImpl(MethodImplOptions.AggressiveInlining)]static public LIB_Mod998244353 Pow(LIB_Mod998244353 x, long y){LIB_Mod998244353 a = 1;while (y != 0){if ((y & 1) == 1) a.Mul(x);x.Mul(x);y >>= 1;}return a;}}class LIB_RedBlackTree{static public LIB_RedBlackTree<long, long, long> CreateRangeUpdateRangeMin() => new LIB_RedBlackTree<long, long, long>(long.MaxValue, long.MinValue + 100, Math.Min, (x, y, c) => y, (x, y) => y);static public LIB_RedBlackTree<long, long, long> CreateRangeAddRangeMin() => new LIB_RedBlackTree<long, long, long>(long.MaxValue, 0, Math.Min, (x, y, c) => x + y, (x, y) => x + y);static public LIB_RedBlackTree<long, long, long> CreateRangeUpdateRangeMax() => new LIB_RedBlackTree<long, long, long>(long.MinValue, long.MaxValue - 100, Math.Max, (x, y, c) => y, (x, y) => y);static public LIB_RedBlackTree<long, long, long> CreateRangeAddRangeMax() => new LIB_RedBlackTree<long, long, long>(long.MinValue, 0, Math.Max, (x, y, c) => x + y, (x, y) => x + y);static public LIB_RedBlackTree<long, long, long> CreateRangeUpdateRangeSum() => new LIB_RedBlackTree<long, long, long>(0, long.MaxValue, (x,y) => x + y, (x, y, c) => y * c, (x, y) => y);static public LIB_RedBlackTree<long, long, long> CreateRangeAddRangeSum() => new LIB_RedBlackTree<long, long, long>(0, 0, (x, y) => x + y, (x, y, c) => x + y * c, (x, y) => x + y);}class LIB_RedBlackTree<Key, ValueT, ValueE> where ValueE : IEquatable<ValueE>{bool ope;class Node{public Node left;public Node right;public Key key;public ValueT val;public ValueT dat;public ValueE lazy;public bool isBlack;public int cnt;public bool needRecalc;}Func<ValueT, ValueT, ValueT> f;Func<ValueT, ValueE, int, ValueT> g;Func<ValueE, ValueE, ValueE> h;ValueT ti;ValueE ei;Comparison<Key> c;Node root;bool isNeedFix;Node lmax;[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree(ValueT ti, ValueE ei, Func<ValueT, ValueT, ValueT> f, Func<ValueT, ValueE, int, ValueT> g, Func<ValueE, ValueE,ValueE> h, Comparison<Key> c, bool ope = true){this.ti = ti;this.ei = ei;this.f = f;this.g = g;this.h = h;this.c = c;this.ope = ope;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree(ValueT ti, ValueE ei, Func<ValueT, ValueT, ValueT> f, Func<ValueT, ValueE, int, ValueT> g, Func<ValueE, ValueE,ValueE> h) : this(ti, ei, f, g, h, Comparer<Key>.Default.Compare) { }[MethodImpl(MethodImplOptions.AggressiveInlining)]bool IsRed(Node n) => n != null && !n.isBlack;[MethodImpl(MethodImplOptions.AggressiveInlining)]bool IsBlack(Node n) => n != null && n.isBlack;[MethodImpl(MethodImplOptions.AggressiveInlining)]int Cnt(Node n) => n == null ? 0 : n.cnt;[MethodImpl(MethodImplOptions.AggressiveInlining)]void Eval(Node n){if (n == null || ei.Equals(n.lazy)) return;n.val = g(n.val, n.lazy, 1);if (!n.needRecalc) n.dat = g(n.dat, n.lazy, Cnt(n));if (n.left != null) n.left.lazy = h(n.left.lazy, n.lazy);if (n.right != null) n.right.lazy = h(n.right.lazy, n.lazy);n.lazy = ei;}void Recalc(Node n){Eval(n);if (!n.needRecalc) return;n.needRecalc = false;n.dat = n.val;if (n.left != null){Recalc(n.left);n.dat = f(n.left.dat, n.dat);}if (n.right != null){Recalc(n.right);n.dat = f(n.dat, n.right.dat);}}Node RotateL(Node n){if (ope && n != null) { Eval(n); Eval(n.right); }Node m = n.right, t = m.left;m.left = n; n.right = t;n.cnt -= m.cnt - Cnt(t);m.cnt += n.cnt - Cnt(t);n.needRecalc = true; m.needRecalc = true;return m;}Node RotateR(Node n){if (ope && n != null) { Eval(n); Eval(n.left); }Node m = n.left, t = m.right;m.right = n; n.left = t;n.cnt -= m.cnt - Cnt(t);m.cnt += n.cnt - Cnt(t);n.needRecalc = true; m.needRecalc = true;return m;}Node RotateLR(Node n){n.left = RotateL(n.left);return RotateR(n);}Node RotateRL(Node n){n.right = RotateR(n.right);return RotateL(n);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(Key key, ValueT val){root = Add(root, key, val);root.isBlack = true;}Node Add(Node n, Key key, ValueT val){if (n == null){isNeedFix = true;return new Node() { key = key, val = val, dat = val, lazy = ei, cnt = 1 };}if (ope) Eval(n);if (c(key, n.key) < 0) n.left = Add(n.left, key, val);else n.right = Add(n.right, key, val);n.needRecalc = true;++n.cnt;return Balance(n);}[MethodImpl(MethodImplOptions.AggressiveInlining)]Node Balance(Node n){if (!isNeedFix || !IsBlack(n)) return n;if (IsRed(n.left) && IsRed(n.left.left)){n = RotateR(n);n.left.isBlack = true;}else if (IsRed(n.left) && IsRed(n.left.right)){n = RotateLR(n);n.left.isBlack = true;}else if (IsRed(n.right) && IsRed(n.right.left)){n = RotateRL(n);n.right.isBlack = true;}else if (IsRed(n.right) && IsRed(n.right.right)){n = RotateL(n);n.right.isBlack = true;}else isNeedFix = false;return n;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void RemoveAt(long index){root = RemoveAt(root, index);if (root != null) root.isBlack = true;}Node RemoveAt(Node n, long index){if (ope) Eval(n);--n.cnt;var r = index.CompareTo(Cnt(n?.left));if (r < 0){n.left = RemoveAt(n.left, index);n.needRecalc = true;return BalanceL(n);}if (r > 0){n.right = RemoveAt(n.right, index - Cnt(n?.left) - 1);n.needRecalc = true;return BalanceR(n);}if (n.left == null){isNeedFix = n.isBlack;return n.right;}n.left = RemoveMax(n.left);n.key = lmax.key;n.val = lmax.val;n.needRecalc = true;return BalanceL(n);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Remove(Key key){root = Remove(root, key);if (root != null) root.isBlack = true;}Node Remove(Node n, Key key){if (ope) Eval(n);--n.cnt;var r = c(key, n.key);if (r < 0){n.left = Remove(n.left, key);n.needRecalc = true;return BalanceL(n);}if (r > 0){n.right = Remove(n.right, key);n.needRecalc = true;return BalanceR(n);}if (n.left == null){isNeedFix = n.isBlack;return n.right;}n.left = RemoveMax(n.left);n.key = lmax.key;n.val = lmax.val;n.needRecalc = true;return BalanceL(n);}Node RemoveMax(Node n){if (ope) Eval(n);--n.cnt;if (n.right != null){n.right = RemoveMax(n.right);n.needRecalc = true;return BalanceR(n);}lmax = n;isNeedFix = n.isBlack;return n.left;}Node BalanceL(Node n){if (!isNeedFix) return n;if (IsBlack(n.right) && IsRed(n.right.left)){var b = n.isBlack;n = RotateRL(n);n.isBlack = b;n.left.isBlack = true;isNeedFix = false;}else if (IsBlack(n.right) && IsRed(n.right.right)){var b = n.isBlack;n = RotateL(n);n.isBlack = b;n.right.isBlack = true;n.left.isBlack = true;isNeedFix = false;}else if (IsBlack(n.right)){isNeedFix = n.isBlack;n.isBlack = true;n.right.isBlack = false;}else{n = RotateL(n);n.isBlack = true;n.left.isBlack = false;n.left = BalanceL(n.left);isNeedFix = false;}return n;}Node BalanceR(Node n){if (!isNeedFix) return n;if (IsBlack(n.left) && IsRed(n.left.right)){var b = n.isBlack;n = RotateLR(n);n.isBlack = b; n.right.isBlack = true;isNeedFix = false;}else if (IsBlack(n.left) && IsRed(n.left.left)){var b = n.isBlack;n = RotateR(n);n.isBlack = b;n.left.isBlack = true;n.right.isBlack = true;isNeedFix = false;}else if (IsBlack(n.left)){isNeedFix = n.isBlack;n.isBlack = true;n.left.isBlack = false;}else{n = RotateR(n);n.isBlack = true;n.right.isBlack = false;n.right = BalanceR(n.right);isNeedFix = false;}return n;}public KeyValuePair<Key, ValueT> this[long i]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get { return At(root, i); }}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void ChangeValue(long i, ValueT v){var n = root;while (true){if (ope) Eval(n);if (n.left == null){if (i == 0) break;else{n = n.right;--i;}}else if (n.left.cnt == i) break;else if (n.left.cnt > i) n = n.left;else{i = i - n.left.cnt - 1;n = n.right;}}n.needRecalc = true;n.val = v;}KeyValuePair<Key, ValueT> At(Node n, long i){while (true){if (ope) Eval(n);if (n.left == null){if (i == 0) return new KeyValuePair<Key, ValueT>(n.key, n.val);else{n = n.right;--i;}}else if (n.left.cnt == i) return new KeyValuePair<Key, ValueT>(n.key, n.val);else if (n.left.cnt > i) n = n.left;else{i = i - n.left.cnt - 1;n = n.right;}}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool ContainsKey(Key key){var t = LowerBound(key);return t < Cnt(root) && c(At(root, t).Key, key) == 0;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public long UpperBound(Key key){var n = root;var ret = 0L;while (true){if (n == null) return ret;if (c(key, n.key) < 0) n = n.left;else{ret += Cnt(n.left) + 1;n = n.right;}}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public long LowerBound(Key key){var n = root;var ret = 0L;while (true){if (n == null) return ret;if (c(key, n.key) <= 0) n = n.left;else{ret += Cnt(n.left) + 1;n = n.right;}}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public KeyValuePair<Key, ValueT> Min(){Node n = root.left, p = root;while (n != null){p = n;if (ope) Eval(p);n = n.left;}return new KeyValuePair<Key, ValueT>(p.key, p.val);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public KeyValuePair<Key, ValueT> Max(){Node n = root.right, p = root;while (n != null){p = n;if (ope) Eval(p);n = n.right;}return new KeyValuePair<Key, ValueT>(p.key, p.val);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Update(long l, long r, ValueE val) => Update(root, l, r, val);void Update(Node n, long l, long r, ValueE val){if (n == null) return;Eval(n);n.needRecalc = true;var lc = Cnt(n.left);if (lc < l) Update(n.right, l - lc - 1, r - lc - 1, val);else if (r <= lc) Update(n.left, l, r, val);else if (l <= 0 && Cnt(n) <= r) n.lazy = val;else{n.val = g(n.val, val, 1);if (l < lc) Update(n.left, l, lc, val);if (lc + 1 < r) Update(n.right, 0, r - lc - 1, val);}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public ValueT Query(long l, long r) => root == null ? ti : Query(root, l, r);ValueT Query(Node n, long l, long r){var v1 = ti; var v2 = ti; var v3 = ti;Eval(n);var lc = Cnt(n.left);if (lc < l) v3 = n.right == null ? ti : Query(n.right, l - lc - 1, r - lc - 1);else if (r <= lc) v1 = n.left == null ? ti : Query(n.left, l, r);else if (l <= 0 && Cnt(n) <= r){Recalc(n);v2 = n.dat;}else{if (l < lc) v1 = n.left == null ? ti : Query(n.left, l, lc);if (lc + 1 < r) v3 = n.right == null ? ti : Query(n.right, 0, r - lc - 1);v2 = n.val;}return f(f(v1, v2), v3);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool Any() => root != null;public long Count => Cnt(root);[MethodImpl(MethodImplOptions.AggressiveInlining)]public IEnumerable<KeyValuePair<Key, ValueT>> List() => L(root);[MethodImpl(MethodImplOptions.AggressiveInlining)]IEnumerable<KeyValuePair<Key, ValueT>> L(Node n){if (n == null) yield break;foreach (var i in L(n.left)) yield return i;yield return new KeyValuePair<Key, ValueT>(n.key, n.val);foreach (var i in L(n.right)) yield return i;}}class LIB_RedBlackTree<Key, Value>{LIB_RedBlackTree<Key, Value, int> tree;[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree(Comparison<Key> c) { tree = new LIB_RedBlackTree<Key, Value, int>(default(Value), 0, null, null, null, c, false); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree() : this(Comparer<Key>.Default.Compare) { }[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(Key key, Value val) => tree.Add(key, val);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Remove(Key key) => tree.Remove(key);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void RemoveAt(long index) => tree.RemoveAt(index);public KeyValuePair<Key, Value> this[long i]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get { return tree[i]; }}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool ContainsKey(Key key) => tree.ContainsKey(key);[MethodImpl(MethodImplOptions.AggressiveInlining)]public long UpperBound(Key key) => tree.UpperBound(key);[MethodImpl(MethodImplOptions.AggressiveInlining)]public long LowerBound(Key key) => tree.LowerBound(key);[MethodImpl(MethodImplOptions.AggressiveInlining)]public KeyValuePair<Key, Value> Min() => tree.Min();[MethodImpl(MethodImplOptions.AggressiveInlining)]public KeyValuePair<Key, Value> Max() => tree.Max();[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool Any() => tree.Any();public long Count => tree.Count;[MethodImpl(MethodImplOptions.AggressiveInlining)]public IEnumerable<KeyValuePair<Key, Value>> List() => tree.List();}class LIB_RedBlackTree<T>{LIB_RedBlackTree<T, int, int> tree;[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree(Comparison<T> c) { tree = new LIB_RedBlackTree<T, int, int>(0, 0, null, null, null, c, false); }[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_RedBlackTree() : this(Comparer<T>.Default.Compare) { }[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Add(T val) => tree.Add(val, 0);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Remove(T val) => tree.Remove(val);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void RemoveAt(long index) => tree.RemoveAt(index);public T this[long i]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get { return tree[i].Key; }}[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool ContainsKey(T val) => tree.ContainsKey(val);[MethodImpl(MethodImplOptions.AggressiveInlining)]public long UpperBound(T val) => tree.UpperBound(val);[MethodImpl(MethodImplOptions.AggressiveInlining)]public long LowerBound(T val) => tree.LowerBound(val);[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Min() => tree.Min().Key;[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Max() => tree.Max().Key;[MethodImpl(MethodImplOptions.AggressiveInlining)]public bool Any() => tree.Any();public long Count => tree.Count;[MethodImpl(MethodImplOptions.AggressiveInlining)]public IEnumerable<T> List() => tree.List().Select(e => e.Key);}class LIB_FastIO{[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_FastIO() { str = Console.OpenStandardInput(); }readonly Stream str;readonly byte[] buf = new byte[2048];int len, ptr;[MethodImpl(MethodImplOptions.AggressiveInlining)]byte read(){if (ptr >= len){ptr = 0;if ((len = str.Read(buf, 0, 2048)) <= 0){return 0;}}return buf[ptr++];}[MethodImpl(MethodImplOptions.AggressiveInlining)]char Char(){byte b = 0;do b = read();while (b < 33 || 126 < b);return (char)b;}[MethodImpl(MethodImplOptions.AggressiveInlining)]virtual public string Scan(){var sb = new StringBuilder();for (var b = Char(); b >= 33 && b <= 126; b = (char)read())sb.Append(b);return sb.ToString();}[MethodImpl(MethodImplOptions.AggressiveInlining)]virtual public long Long(){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 << 3) + (ret << 1) + b - '0';}}[MethodImpl(MethodImplOptions.AggressiveInlining)]virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }}class LIB_FastIODebug : LIB_FastIO{Queue<string> param = new Queue<string>();[MethodImpl(MethodImplOptions.AggressiveInlining)]string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue();}[MethodImpl(MethodImplOptions.AggressiveInlining)]public LIB_FastIODebug() { }[MethodImpl(MethodImplOptions.AggressiveInlining)]public override string Scan() => NextString();[MethodImpl(MethodImplOptions.AggressiveInlining)]public override long Long() => long.Parse(NextString());[MethodImpl(MethodImplOptions.AggressiveInlining)]public override double Double() => double.Parse(NextString());}}