🧪
AtCoder入緑に使ったテンプレ(C#)
素敵な夜ですね。色々と死にかけ状態ですがなんとかAtCoder 入緑しました。C#テンプレを共有です。お部屋をお連れします。C#erはよろしければお使いください。
お借りした部分ばかりですが、何卒ご容赦頂けますと幸いです。
色変記事はこちらです
// ABC999999999999
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 ComproSimarmLib.Util;using System.Numerics;
using static System.Console;
public class Program
{
public static void Problem()
{
var sc = new Scanner();
long a = sc.Nl();
long b = sc.Nl();
long ans = 0;
Console.WriteLine(ans);
}
public static void Main(string[] args)
{
Problem();
}
const int Mod1097 = 1000000007;
}
namespace ComproSimarmLib.Util
{
class Scanner
{
private string[] _line;
private int _index;
private const char Separator = ' ';
private Boolean fileInput = false;
StreamReader file;
//コンストラクタでindexを0に、lineを配列に初期化
public Scanner(string type="console")
{
_line = new string[0];
_index = 0;
if (type == "file") {
fileInput = true;
string FileToRead = Console.ReadLine();
file = new StreamReader(FileToRead);
}
}
//以下借り物
public string Next()
{
while (_index >= _line.Length)
{
if (fileInput == true)
{
_line = file.ReadLine().Split(Separator);
}
else
{
_line = Console.ReadLine().Split(Separator);
}
_index = 0;
}
return _line[_index++];
}
public int Ni() => int.Parse(Next());
public long Nl() => long.Parse(Next());
public double Ndo() => double.Parse(Next());
public decimal Nde() => decimal.Parse(Next());
public char Ncr() => Next()[0];
public char[] Ncs() => Next().ToCharArray();
public string[] Array()
{
if (fileInput == true)
{
_line = file.ReadLine().Split(Separator);
}
else
{
_line = Console.ReadLine().Split(Separator);
}
_index = _line.Length;
return _line;
}
public int[] Ints() => Array().Select(int.Parse).ToArray();
public long[] Longs() => Array().Select(long.Parse).ToArray();
public double[] Doubles() => Array().Select(double.Parse).ToArray();
public decimal[] Decimals() => Array().Select(decimal.Parse).ToArray();
public char[] CharsSpaced() => Array().Select(x=>Convert.ToChar(x)).ToArray();
}
class LittleMethods
{
//整数二つを受け入れ、最大公約数を出す
public long GreatestCommonDivisor(long a, long b)
{
// https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d
long x = 0;
while (1 == 1)
{
if (a % b == 0)
{
return b;
}
else
{
x = a % b;
a = b;
b = x;
}
}
}
//整数二つを入れ、最小公倍数を出す
public long LeastCommonMultipul(long a, long b)
{
// https://qiita.com/Jane35416555/items/0d9d6dd088049ce64e3d
long x = GreatestCommonDivisor(a, b);
return a * b / x;
}
//整数一つを入れ、素数ならtrueを返す
public bool PrimeNumberOrNot(long x)
{
if (x == 1) { return false; }
for (long i = 2; i * i <= x; i++)
{
if (x % i == 0) { return false; }
}
return true;
}
//整数一つを入れ、全ての約数をListで返す
public List<long> AllDivisors(long x)
{
List<long> y = new List<long>();
if (x == 1) { y.Add(1); return y; }
for (long i = 1; i * i <= x; i++)
{
if (x % i == 0)
{
y.Add(i);
if (x / i != i) { y.Add(x / i); }
}
}
y.Sort();
return y;
}
//https://stackoverflow.com/questions/4124189/
//sqrtの精度に問題があると聞いたので。decimalを入れるとルートしてdecimalで返す。
public decimal SuperSqrt(decimal x, decimal epsilon = 0.0M)
{
decimal cur = (decimal)Math.Sqrt((double)x), prev;
do
{
prev = cur;
if (prev == 0.0M) return 0;
cur = (prev + x / prev) / 2;
} while (Math.Abs(prev - cur) > epsilon);
return cur;
}
//階乗して返す
public long Multipul_Fuctrial(long x)
{
long a = 1;
for (int i = 2; i <= x; i++)
{
a *= i;
}
return a;
}
//特定の数で毎回割りながら階乗する。
public long Multipul_FuctrialRemainderer(long x)
{
long a = 1;
long b = (long)Math.Pow(10, 9) + 7;//ここは問題に寄る
for (int i = 2; i <= x; i++)
{
a *= i;
a = a % b;
}
return a;
}
//順列総当り用 戻り値:1 2 3,1 3 2,などなど各順列のリストのリスト
//本番中に作ったので参考URLを紛失。申し訳ございません。
//重い! 注意
public IEnumerable<T[]> Make_PermutationList<T>(IEnumerable<T> col)
{
if (col.Count() == 1) yield return new T[] { col.First() };
foreach (var x in col)
{
var selected = new T[] { x };
var unused = col.Except(selected);
foreach (var y in Make_PermutationList(unused))
{
yield return selected.Concat(y).ToArray();
}
}
}
// https://webbibouroku.com/Blog/Article/cs-permutation
// 使い方:List<long[]> PermListList = lm.AllPermutation<long>(seed);
public List<T[]> AllPermutation<T>(params T[] array) where T : IComparable
{
var a = new List<T>(array).ToArray();
var res = new List<T[]>();
res.Add(new List<T>(a).ToArray());
var n = a.Length;
var next = true;
while (next)
{
next = false;
// 1
int i;
for (i = n - 2; i >= 0; i--)
{
if (a[i].CompareTo(a[i + 1]) < 0) break;
}
// 2
if (i < 0) break;
// 3
var j = n;
do
{
j--;
} while (a[i].CompareTo(a[j]) > 0);
if (a[i].CompareTo(a[j]) < 0)
{
// 4
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
Array.Reverse(a, i + 1, n - i - 1);
res.Add(new List<T>(a).ToArray());
next = true;
}
}
return res;
}
//int nを受け取り、数が少ない順で2^n以下全てのbitを記載したリストのリストを返す
public List<List<int>> Make_BitList<T>(int n)
{
List<List<int>> allBit = new List<List<int>>();
for (int i = 0; i < 1 << n; i++)
{
List<int> item = new List<int>();
string bitString = Convert.ToString(i, 2).PadLeft(n, '0');
foreach (char c in bitString)
{
item.Add(c - 48);
}
allBit.Add(item);
}
return allBit;
}
//nCr 巨大数に弱い 考えて使うこと
public long NumberOfCombination(long n, long r)
{
long x = 1;
for (long i = 0; i < r; i++)
{
x *= n - i;
}
for (long i = r; i > 0; i--)
{
x /= i;
}
return x;
}
public long LongPow(long a,long b){
long ret = 1;
for(long i = 0;i<b;i++){
ret*=a;
}
return ret;
}
public BigInteger BigPow(long a,long b){
BigInteger ret = 1;
for(long i = 0;i<b;i++){
ret*=a;
}
return ret;
}
// ダイクストラ
// tree=new List<Pair>[n];tree[first].Add(new Pair(second,cost));var time = lm.Dijkstra(0,tree);
// のようにして使う
// 各頂点への最短時間が配列として記録される
public long[] Dijkstra(int start,List<Pair>[] tree){
var q = new PriorityQueue<Pair>(tree.Length,false);
var res = Enumerable.Repeat(long.MaxValue,tree.Length).ToArray();
res[start] = 0;
q.Enqueue(new Pair(start,0));
while(q.Count>0){
var cur = q.Dequeue();
if(res[cur.Pos] != cur.Val) continue;
foreach (var next in tree[cur.Pos])
{
if(res[next.Pos]<= cur.Val + next.Val) continue;
res[next.Pos] = cur.Val + next.Val;
q.Enqueue(new Pair(next.Pos,cur.Val+next.Val));
}
}
return res;
}
// ワーシャルフロイド法(Floyd-Warshall Algorithm)
// tree=new List<Pair>[n];tree[first].Add(new Pair(second,cost));
// long[][] time = lm.FloydWarshall(tree,nodeCount);
// 各頂点から各頂点への最短距離がジャグ配列として返る
public long[][] FloydWarshall(List<Pair>[] tree,long n){
long[][] dp = new long[n][];
for(int i = 0;i<n;i++){
dp[i] = Enumerable.Repeat(long.MaxValue / 1000,(int)n).ToArray();
}
for (int i = 0; i < tree.Length; i++)
{
foreach (var edge in tree[i])
{
dp[i][edge.Pos] = edge.Val;
}
}
for (int i = 0; i < n; i++)
{
dp[i][i] = 0;
}
for (int k = 0; k < n; k++)
{
for (int s = 0; s < n; s++)
{
for (int t = 0; t < n; t++)
{
dp[s][t] = Math.Min(dp[s][t],dp[s][k]+dp[k][t]);
}
}
}
return dp;
}
// 最小全域木判定 クラスカル法
// https://atcoder.jp/contests/abc218/tasks/abc218_e
// int[][] es = [[pointA,pointB,cost],[...],...]
// var mes = Kruskal(int nodeNum,es);
// とするとint[][] mes = [[(必要なedge)],[...],...]が返る
// 無向グラフは片道だけでOK
// 応用していく場合はedges.Add(new List<long>(){a-1,b-1,c,?});でも動く
public int[][] Kruskal(int n,int[][] edges){
var uf = new UnionFind(n);
var minSTreeNodes = new List<int[]>();
foreach (var e in edges.OrderBy(e=>e[2]))
{
if(uf.Same(e[0],e[1])){continue;}
uf.Unite(e[0],e[1]);
minSTreeNodes.Add(e);
}
return minSTreeNodes.ToArray();
}
// 座標の入ったListを入れると、座標圧縮された後のListを返す(開始地点は1)。
public List<long> positionComp(List<long> map){
var mapSorted = new SortedSet<long>(map).ToList();
var compedMap = new List<long>();
foreach(var pos in map){
compedMap.Add(mapSorted.BinarySearch(pos)+1);
}
return compedMap;
}
public long ketasuu(long x){
return x.ToString().Length;
}
// https://atcoder.jp/contests/abc145/submissions/8472887
// 2乗ずつかけていく少し高速なpow、第3引数はmod
public long ModFastPow(long x,long n,long m){
long ans = 1;
while(n>0){
if(n%2==1){
ans = ans * x % m;
n-=1;
}
x=x*x%m;
n/=2;
}
return ans;
}
// 高速なpowを使って高速化した、modの世界でのみ成り立つnCr、第3引数はmod
public long ModWorldNcr(long n,long r,long m){
long ans = 1;
for (var i = n-r+1; i <= n; i++)
ans = ans * i % m;
for (var i = 2; i<=r; i++)
ans = ans * ModFastPow(i,m-2,m) %m;
return ans;
}
// https://atcoder.jp/contests/abc142/submissions/18533628
// 引数を素因数分解し、その内容でDictionaryを作る
public Dictionary<long,long> PrimeFactorDictionary(long n){
var dic = new Dictionary<long,long>();
var tmp = n;
while(tmp % 2 ==0){
tmp /= 2;
if(dic.ContainsKey(2)) ++dic[2];
else dic.Add(2,1);
}
for (var p = 3L; p*p <= n; p+=2)
{
while(tmp % p == 0){
tmp /= p;
if(dic.ContainsKey(p)) dic[p]++;
else dic.Add(p,1);
}
if (tmp == 1) break;
}
if (tmp > 1) dic.Add(tmp, 1);
return dic;
}
// 二分探索関数。第二引数の配列の中から、最初にxより大きかった場所のインデックスを返す。
public long BinarySearch_firstLarger(long x,long[] arrSorted){
long l = 0;
long r = arrSorted.Length;
long m = 0;
while(l+1<r){
m = (l + r) / 2;
if(arrSorted[m] > x) r = m;
else l = m;
}
if(arrSorted[l]>=x) return l;
else return r;
}
// 二分探索関数。第二引数の配列の中から、最後にxより小さかった場所のインデックスを返す。
public long BinarySearch_lastSmaller(long x,long[] arrSorted){
long l = 0;
long r = arrSorted.Length;
long m = 0;
while(l+1<r){
m = (l + r) / 2;
if(arrSorted[m] >= x) r = m;
else l = m;
}
if(r==arrSorted.Length) return l;
else if(arrSorted[r]>=x) return l;
else return r;
}
// ランレングス圧縮を行い、文字×文字数のタプルのリストを返す。
public List<Tuple<string,long>> RunLengthEncode(string s){
var ret = new List<Tuple<string,long>>();
var count = 1;
for(var i = 1 ; i < s.Length ; i++)
{
if(s[i] != s[i-1]){
ret.Add(new Tuple<string,long>(s.Substring(i-1,1),count));
count = 1;
}else{
count++;
}
}
ret.Add(new Tuple<string,long>(s.Substring(s.Length-1,1),count));
return ret;
}
// 回転。Tuple<long,long> lotatedxy = littleLotate(回転前x,y,原点x,y,度数法の回転角度)
public Tuple<double,double> littleLotate(double x1,double y1,double x0,double y0,double angle360){
double dis = Sqrt((x0-x1) * (x0-x1) + (y0-y1) * (y0-y1));
double startRad = Atan2(y1-y0,x1-x0);
double newRad = startRad + 2 * Math.PI / (360 / angle360);
double unitX = Math.Cos(newRad);
double unitY = Math.Sin(newRad);
return new Tuple<double,double>(x0+unitX*dis,y0+unitY*dis);
}
// 2点間の距離。
public double twoPointsDistance(double x1,double y1,double x2,double y2){
double dis = Sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
return dis;
}
// p1、p2の2点でできた直線と点(x,y)の距離
public double lineOfTwoPointsAndPointDistance(int p1x,int p1y,int p2x,int p2y,int x,int y){
double a = p2y - p1y;
double b = -(p2x - p1x);
double c = (p2x - p1x) * p1y - (p2y - p1y) * p1x;
double dist = Abs(a * x + b * y + c) / Sqrt(a * a + b * b);
return dist;
}
}
}
// 優先度付きキュー用のPair型 CompareTo関数使用
class Pair : IComparable<Pair>{
public long Pos;
public long Val;
public Pair(long pos, long val){
Pos=pos;Val=val;
}
public int CompareTo(Pair b){
return Val.CompareTo(b.Val);
}
}
// 優先度付きキュー
// var q = new PriorityQueue<Pair>(tree.Length,false); で呼び
// q.Enqueue(new Pair(pos,val));でEnqueue、q.Dequeue();でDequeue
// dijkstra、Pair、優先度付きキューは https://atcoder.jp/contests/abc035/submissions/24032918 より
class PriorityQueue<T> where T : IComparable<T>{
public T[] List;
public int Count;
bool IsTopMax;
public PriorityQueue(int count,bool isTopMax = false){
IsTopMax = isTopMax;
List = new T[count];
}
public void Enqueue(T value){
if(Count == List.Length){
var newlist = new T[List.Length*2];
for (int i = 0; i < List.Length; ++i)
{
newlist[i] = List[i];
}
List = newlist;
}
var pos = Count;
List[pos] = value;
++Count;
while(pos>0){
var parent=(pos-1)/2;
if(Calc(List[parent],List[pos],true)) break;
Swap(parent,pos);
pos = parent;
}
}
public T Dequeue(){
--Count;
Swap(0,Count);
var pos = 0;
while(true){
var child = pos * 2 + 1;
if(child >= Count) break;
if(child + 1 < Count && Calc(List[child+1],List[child],false)) ++child;
if(Calc(List[pos],List[child],true)) break;
Swap(pos,child);
pos = child;
}
return List[Count];
}
bool Calc(T a, T b,bool equalVal){
var ret = a.CompareTo(b);
if(ret == 0 && equalVal) return true;
return IsTopMax ? ret > 0 : ret < 0;
}
void Swap(int a,int b){
var tmp = List[a];
List[a] = List[b];
List[b] = tmp;
}
}
/* 個数不要な優先度付きキュー https://yambe2002.hatenablog.com/entry/2018/12/24/140754
public class PriorityQueue<T> where T : IComparable
{
private IComparer<T> _comparer = null;
private int _type = 0;
private T[] _heap;
private int _sz = 0;
private int _count = 0;
/// <summary>
/// Priority Queue with custom comparer
/// </summary>
public PriorityQueue(IComparer<T> comparer)
{
_heap = new T[128];
_comparer = comparer;
}
/// <summary>
/// Priority queue
/// </summary>
/// <param name="type">0: asc, 1:desc</param>
public PriorityQueue(int type = 0)
{
_heap = new T[128];
_type = type;
}
private int Compare(T x, T y)
{
if (_comparer != null) return _comparer.Compare(x, y);
return _type == 0 ? x.CompareTo(y) : y.CompareTo(x);
}
public void Push(T x)
{
_count++;
if (_count > _heap.Length)
{
var newheap = new T[_heap.Length * 2];
for (int n = 0; n < _heap.Length; n++) newheap[n] = _heap[n];
_heap = newheap;
}
//node number
var i = _sz++;
while (i > 0)
{
//parent node number
var p = (i - 1) / 2;
if (Compare(_heap[p], x) <= 0) break;
_heap[i] = _heap[p];
i = p;
}
_heap[i] = x;
}
public T Pop()
{
_count--;
T ret = _heap[0];
T x = _heap[--_sz];
int i = 0;
while (i * 2 + 1 < _sz)
{
//children
int a = i * 2 + 1;
int b = i * 2 + 2;
if (b < _sz && Compare(_heap[b], _heap[a]) < 0) a = b;
if (Compare(_heap[a], x) >= 0) break;
_heap[i] = _heap[a];
i = a;
}
_heap[i] = x;
return ret;
}
public int Count()
{
return _count;
}
public T Peek()
{
return _heap[0];
}
public bool Contains(T x)
{
for (int i = 0; i < _sz; i++) if (x.Equals(_heap[i])) return true;
return false;
}
public void Clear()
{
while (this.Count() > 0) this.Pop();
}
public IEnumerator<T> GetEnumerator()
{
var ret = new List<T>();
while (this.Count() > 0)
{
ret.Add(this.Pop());
}
foreach (var r in ret)
{
this.Push(r);
yield return r;
}
}
public T[] ToArray()
{
T[] array = new T[_sz];
int i = 0;
foreach (var r in this)
{
array[i++] = r;
}
return array;
}
}
*/
// https://atcoder.jp/contests/abc097/submissions/2592272
public class UnionFind
{
private int[] data;
private int[] rank;
private int[] size;
public UnionFind(int n)
{
data = new int[n];
rank = new int[n];
size = new int[n];
for(var i = 0; i < n; i++)
{
data[i] = i;
rank[i] = 0;
size[i] = 1;
}
}
public int Root(int x)
{
return data[x] == x ? x : data[x] = Root(data[x]);
}
public bool Same(int x,int y)
{
return Root(x) == Root(y);
}
public int Size(int x)
{
return size[Root(x)];
}
public void Unite(int x,int y)
{
x = Root(x);
y = Root(y);
if (x == y) return;
if (rank[x] < rank[y])
{
data[x] = y;
}
else
{
data[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
int tmp = size[x];
size[x] += size[y];
size[y] += tmp;
}
}
// Array.Sort(s,new Comparer());の形で使う独自のComparer
class Comparer : IComparer<string>{
public int Compare(string l,string m){
return l.Length - m.Length;
}
}
// var map = new Map<int, int>();
// https://atcoder.jp/contests/abc210/submissions/24288120
// https://qiita.com/Camypaper/items/de6d576fe5513743a50e
public class Map<TKey, TValue> : Dictionary<TKey, TValue>
{
public new TValue this[TKey key]
{
get
{
TValue o;
return TryGetValue(key, out o) ? o : default(TValue);
}
set { base[key] = value; }
}
}
// 最短共通祖先
// var lca = new LeastCommonAncestorTree(int 頂点数,List<long>[n] map);で起動
// lca.dist(v1,v2)で2頂点間の距離を出せる
// https://atcoder.jp/contests/abc014/submissions/531033
// ※扱いやすいよう全変数をlong型にしているが、シフト処理の為内部的にはint以上の桁数は扱えない
class LeastCommonAncestorTree // no loop
{
long n, m;
long[][] parent;
long[] dep;
public LeastCommonAncestorTree(long n, List<long>[] e) // e : 0-indexed
{
this.n = n;
parent = new long[n][];
dep = new long[n];
m = (long)Math.Log(n + 1, 2) + 1;
for (long i = 0; i < n; i++)
{
parent[i] = new long[m];
dep[i] = n + 1;
for (long j = 0; j < m; j++)
parent[i][j] = -1;
}
long depmax = 0;
dep[0] = 0;
var q = new Queue<long>();
q.Enqueue(0);
while (q.Count > 0)
{
var p = q.Dequeue();
foreach (var item in e[p])
{
if (dep[item] > dep[p] + 1)
{
dep[item] = dep[p] + 1;
depmax = Math.Max(depmax, dep[item]);
parent[item][0] = p;
q.Enqueue(item);
}
}
}
for (long i = 1; 1 << (int)i <= depmax; i++)
for (long j = 0; j < n; j++)
if (dep[j] >= 1 << (int)i)
parent[j][i] = parent[parent[j][i - 1]][i - 1];
}
long climb(long a, long d)
{
if (d == 0) return a;
long i = 0;
while (1 << (int)i <= d) ++i;
--i;
return climb(parent[a][i], d - (1 << (int)i));
}
long subdist(long a, long b)
{
if (a == b) return 0;
if (parent[a][0] == parent[b][0]) return 2;
for (long i = 1; i < m; i++)
if (parent[a][i - 1] != parent[b][i - 1] && parent[a][i] == parent[b][i])
return (1 << (int)i) + subdist(parent[a][i - 1], parent[b][i - 1]);
return -1;
}
public long dist(long a, long b)
{
long p = a, q = b, c = 0;
if (dep[p] < dep[q])
{
c += dep[q] - dep[p];
q = climb(q, dep[q] - dep[p]);
}
else if (dep[p] > dep[q])
{
c += dep[p] - dep[q];
p = climb(p, dep[p] - dep[q]);
}
return c + subdist(p, q);
}
}
// 平衡二分探索木+multiset
// https://yambe2002.hatenablog.com/entry/2017/02/07/122421
/// <summary>
/// Self-Balancing Binary Search Tree
/// (using Randamized BST)
/// </summary>
public class SB_BinarySearchTree<T> where T : IComparable
{
public class Node
{
public T Value;
public Node LChild;
public Node RChild;
public int Count; //size of the sub tree
public Node(T v)
{
Value = v;
Count = 1;
}
}
static Random _rnd = new Random();
public static int Count(Node t)
{
return t == null ? 0 : t.Count;
}
static Node Update(Node t)
{
t.Count = Count(t.LChild) + Count(t.RChild) + 1;
return t;
}
public static Node Merge(Node l, Node r)
{
if (l == null || r == null) return l == null ? r : l;
if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
{
l.RChild = Merge(l.RChild, r);
return Update(l);
}
else
{
r.LChild = Merge(l, r.LChild);
return Update(r);
}
}
/// <summary>
/// split as [0, k), [k, n)
/// </summary>
public static Tuple<Node, Node> Split(Node t, int k)
{
if (t == null) return new Tuple<Node, Node>(null, null);
if (k <= Count(t.LChild))
{
var s = Split(t.LChild, k);
t.LChild = s.Item2;
return new Tuple<Node, Node>(s.Item1, Update(t));
}
else
{
var s = Split(t.RChild, k - Count(t.LChild) - 1);
t.RChild = s.Item1;
return new Tuple<Node, Node>(Update(t), s.Item2);
}
}
public static Node Remove(Node t, T v)
{
if (Find(t, v) == null) return t;
return RemoveAt(t, LowerBound(t, v));
}
public static Node RemoveAt(Node t, int k)
{
var s = Split(t, k);
var s2 = Split(s.Item2, 1);
return Merge(s.Item1, s2.Item2);
}
public static bool Contains(Node t, T v)
{
return Find(t, v) != null;
}
public static Node Find(Node t, T v)
{
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0) t = t.LChild;
else if (cmp < 0) t = t.RChild;
else break;
}
return t;
}
public static Node FindByIndex(Node t, int idx)
{
if (t == null) return null;
var currentIdx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
if (currentIdx == idx) return t;
if (currentIdx > idx)
{
t = t.LChild;
currentIdx -= (Count(t == null ? null : t.RChild) + 1);
}
else
{
t = t.RChild;
currentIdx += (Count(t == null ? null : t.LChild) + 1);
}
}
return null;
}
public static int UpperBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var ret = Int32.MaxValue;
var idx = Count(t) - Count(t.RChild) - 1;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp > 0)
{
ret = Math.Min(ret, idx);
t = t.LChild;
idx -= (Count(t == null ? null : t.RChild) + 1);
}
else if (cmp <= 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
}
}
return ret == Int32.MaxValue ? Count(torg) : ret;
}
public static int LowerBound(Node t, T v)
{
var torg = t;
if (t == null) return -1;
var idx = Count(t) - Count(t.RChild) - 1;
var ret = Int32.MaxValue;
while (t != null)
{
var cmp = t.Value.CompareTo(v);
if (cmp >= 0)
{
if (cmp == 0) ret = Math.Min(ret, idx);
t = t.LChild;
if (t == null) ret = Math.Min(ret, idx);
idx -= t == null ? 0 : (Count(t.RChild) + 1);
}
else if (cmp < 0)
{
t = t.RChild;
idx += (Count(t == null ? null : t.LChild) + 1);
if (t == null) return idx;
}
}
return ret == Int32.MaxValue ? Count(torg) : ret;
}
public static Node Insert(Node t, T v)
{
var ub = LowerBound(t, v);
return InsertByIdx(t, ub, v);
}
static Node InsertByIdx(Node t, int k, T v)
{
var s = Split(t, k);
return Merge(Merge(s.Item1, new Node(v)), s.Item2);
}
public static IEnumerable<T> Enumerate(Node t)
{
var ret = new List<T>();
Enumerate(t, ret);
return ret;
}
static void Enumerate(Node t, List<T> ret)
{
if (t == null) return;
Enumerate(t.LChild, ret);
ret.Add(t.Value);
Enumerate(t.RChild, ret);
}
}
/// <summary>
/// C-like set
/// </summary>
public class Set<T> where T : IComparable
{
protected SB_BinarySearchTree<T>.Node _root;
public T this[int idx]{ get { return ElementAt(idx); } }
public int Count()
{
return SB_BinarySearchTree<T>.Count(_root);
}
public virtual void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else
{
if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
_root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
public void Clear()
{
_root = null;
}
public void Remove(T v)
{
_root = SB_BinarySearchTree<T>.Remove(_root, v);
}
public bool Contains(T v)
{
return SB_BinarySearchTree<T>.Contains(_root, v);
}
public T ElementAt(int k)
{
var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
if (node == null) throw new IndexOutOfRangeException();
return node.Value;
}
public int Count(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int LowerBound(T v)
{
return SB_BinarySearchTree<T>.LowerBound(_root, v);
}
public int UpperBound(T v)
{
return SB_BinarySearchTree<T>.UpperBound(_root, v);
}
public Tuple<int, int> EqualRange(T v)
{
if (!Contains(v)) return new Tuple<int, int>(-1, -1);
return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
}
public List<T> ToList()
{
return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
}
}
/// <summary>
/// C-like multiset
/// </summary>
public class MultiSet<T> : Set<T> where T : IComparable
{
public override void Insert(T v)
{
if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
else _root = SB_BinarySearchTree<T>.Insert(_root, v);
}
}
// thanks
// https://atcoder.jp/contests/abc171/submissions/14526247
// https://atcoder.jp/contests/abc171/submissions/14526315
// https://atcoder.jp/contests/abc171/submissions/14527040
// https://atcoder.jp/contests/abc171/submissions/14527118
Discussion