CODE FESTIVAL 2014 予選B
コンテストページ http://code-festival-2014-qualb.contest.atcoder.jp/
解説 http://www.slideshare.net/chokudai/codefestival2014qual-b
Cが全然わからず38位。Dの方が明らかに簡単だった。
A - あるピアニスト
maxとるだけ
puts gets.split(' ').map(&:to_i).max
B - 歩く人
和をとっていくだけ
C - 錬金術士
本番中に通せたけどたぶん嘘解法。テストケースがガバガバで明らかに間違ってる方法でも通っちゃう。フローでも解けるとの情報を得たので考えてみた。
文字の位置は必要ないので各文字の出現回数だけカウントしておく。
上図のようなグラフを生やしてs-tフローが2*N流れればS1,S2 から S3 が錬金できる。
D - 登山家
本番ではRMQで二分探索してO(n (log n)^2)で通した。segtree内で二分探索するかsparse tableを使えばO(n log n)になる。
stackを使う解法の解説がスライド一枚で済んじゃってるので簡単に解説でもしてみる。
各位置i(i=0,1,..,n-1)について降順にそこからどこまで東の小屋が見えるかを求めることを考える。スライドの操作１のスタックをpopし続ける操作について説明すると、popする条件によりスタックに詰まれているindexは昇順、対応する高さも昇順になっている。
したがってh[i]を超えるスタックに積まれている中での最初のindexを求めるにはスライドの通り操作すればよいことがわかる。ここでpopされたindexは二度と調べられないが、そのようにして問題ない理由はpopされたindexはdp[j](j<i)の解とはなり得ないから。各jについてh[j]を超える最初のindexを求めるときj<a<b,h[a]>h[b]のようなa,bの組が存在していた場合、h[j]<h[b]となっていたとしてもそれよりaの地点で先にh[j]を超えているためbは解とはなり得ないので二度と調べなくて良いことがわかる。アルゴリズムの正当性はわかったので次に計算量を考察する。比較、スタックのpush,popをそれぞれ１として各dp[i]を計算する際にpopされる要素数を とすると全体のコストは
となりここで
はnを超えないので
であることからstackを使うアルゴリズムはO(n)であることがわかる。
要するに高々pushした分だけしかpopできないんだから均しO(1)でしょということです。
コンテスト解説一覧
解説がどこにあるのかわからないことが少なくないので
no title
TopCoder https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive
Codeforces 問題ページ右の「Tutorial」
CodeChef Editorials
GCJ analysis
FHC 「facebook hacker cup solutions 2012」とかで検索
Yandex Algorithm 2015r1 2015r2
PCK 問題と解説
JOI 問題と解説 解説 IOI系ページまとめ
ICPC 講評 リンク集→
UTPC 解説
KUPC 解説
WUPC 解説
UAPC2009Spring 解説
UAPC2010 解説
OUPC2012(立命合宿day2) 解説 ジャッジデータ
OUPC2013(立命合宿day2) 解説
立命セット(会津,立命合宿)
NPCA#02 解説
NPCA#03 解説
Typical DP Contest 一言解説 togetter
洋菓子店 論文 スライド
ついでにマラソン系コンテスト一覧
MarathonMatch ハル研プロコン CodeVS ICFPC SamurAICoding CEDEC_AI_CHALLENGE
機械学習,データマイニング系
MarathonMatch Kaggle CrowdSolving HackerRank(よく知らない)
ライブラリverify用問題集
典型アルゴリズムそのままの問題はここOnline Programming Lesson
・エラトステネスの篩
アジア地区2002A
・連立合同式(ライツアウト系)
PCK2006
アジア地区2010D 解説
夏合宿2008day2J(mod7,ジャッジ未対応)
・2点を通る半径rの円
国内予選2004D
・円と円の交点
国内予選2012E(線分の交差判定も) 解説
国内予選2013E 解説
・円と円の共通接線
模擬国内2010E
・点と線分の距離
PCK2006
・線分と線分の距離
国内予選2008E
模擬国内2012D
・ccw
PCK2004予選11
・凸包
PCK2004本選41
・ボロノイ図
夏合宿2009day2F 解説
・ローリングハッシュ
Cf166div2D PROBLEMSET271D Editorial
・Z algorithm
Cf246div2D PROBLEMSET432D
・KMP
Cf201div2D PROBLEMSET346B
Cf246div2D PROBLEMSET432D(failure linkでDP,ロリハも必要)
・Aho-Corasick
UTPC2010I 解説
模擬国内2011F 解説
・SuffixArray(+高さ配列)
Cf94D PROBLEMSET128B
夏合宿2014day4F
SPOJ
codemonk
・最大流
国内予選2009E(二部マッチング)
SRM589div1med(二部グラフの最小点カバー) Editorial
夏合宿2007day3D
ABC10D
・最小費用流
RUPC2012day1E 解説
RUPC2014day3G 解説
幾何コンB(実数コスト)
・強連結成分分解
Cf190div2E PROBLEMSET228E(2-SAT)
・トポロジカルソート
PCK2005(|V|<=20,|E|<=100)
JOI 2006(|V|<=5000,|E|<=100000)
模擬国内2006C 解説
・重心分解
Cf190E PROBLEMSET321C
・Heavy-Light Decomposition
TAQTREE
White Falcon And Tree
夏合宿2012day4D 解説
・meldable heap
夏合宿2009day3F(非想定解)
・２次元RMQ(密)
UAPC2011G
・動的segtree 資料
UAPC2012day2I
・範囲代入segtree
Cf207A PROBLEMSET356A
・遅延評価segtree
・平衡二分探索木
PCK2005 (nth_element)
アジア地区2007A (nth_element)
UTPC2013I (prevvalue,nextvalue)
ARC33C (nth_element)
・永続配列
Cf368div2D PROBLEMSET707D
・永続union-find
AGC#002D(半永続)
・永続平衡二分木
コピー＆ペースト
グラフではない
・ウェーブレット行列 最速攻略 ウェーブレット木の世界
CodeChefLong TRIQUERY(rank_less_than)
夏合宿2012day2C(rangefreq)
K-th Number
Coloring Tree(区間内distinct)
Cf267E(Div2only) PROBLEMSET467E(nextvalue)
ACPC2014Day2I
・符号付ウェーブレット行列
L番目の数字 解説
CF326div2E PROBLEMSET587C
・動的ウェーブレット行列
Library Query(insert,erase,quantile)
Cf260div1D PROBLEMSET455D(insert,erase,rank)
G番目の数字(insert,persistent,linesweap)
・サイコロ
AOJ COURSE
JOI2005予選3 解説
国内予選2012C
国内予選2014F
・シンプソン則
模擬地区2006E 解説
立命合宿2013day2I 解説
・FFT
SRM436div1hard Forum
データ構造メモ（平衡二分木&ヒープ）
※自分用メモなので人に見せる体裁にはしてないです。あまり確認してないので間違ったこと書いてるかも
平衡二分木
備考
節点に部分木のサイズを持たせるなどすればrank_less_thanやkth_elementなどの追加の機能も可。
動的な列を扱うことも可能で要素の挿入削除、列の併合分割ができる動的なsegtreeとしても使える。
プログラミングコンテストでのデータ構造 2 http://www.slideshare.net/iwiwi/2-12188757
npca2013 木のはなし http://www.npca.jp/2013/
Algorithms with Python http://www.geocities.jp/m_hiroi/light/index.html#python_algo
AVL tree
赤黒木と比べれば圧倒的に実装しやすい、赤黒木より遅い印象はないけどよく知らない。
赤黒木
場合わけえぐいやつ。実装する気起きない。葉にだけ要素を持たせればmerge/splitもできる
treap
乱数で割り振る優先度に対してヒープになってるやつ期待値O(log n),merge/split可能、融合永続不可
randomized binary search tree(RBST)
どっちを根にするか乱択するやつ、merge/split可能、融合永続可
treapより好きだけど毎回乱数生成するからそれで遅くなったりするのかな？
splay tree
link-cut treeで使うやつ、ならしO(log n)、merge/split可能らしい
scapegoat tree
平衡でなくなったらその部分を壊して再構築。ならしO(log n)
kd treeは最悪O(n)だがこの方法でならしO(log n)にできるらしい
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120901/1346460700
https://topcoder.g.hatena.ne.jp/spaghetti_source/20120908/1347059626
skip list
木ではないけど似たようなことができる。競技では使うことないだろうけど分散処理がしやすいらしい。
van Emde Boas tree
二分木じゃないけど各種操作がO(log log u),(uは普遍集合のサイズ)でできる謎木。
実測でも速いらしい
http://catupper.hatenablog.com/entry/20120830/1346338855
ヒープ
binary heap
pushとpopだけならこれが最強。固定長配列でよければさらに速くなる。
leftist heap
meld を最悪O(log n)で処理できる。永続化するならこれ
skew heap
ならしO(log n)になる代わりにメンバ変数が減ってコードがより短くなる。
http://hos.ac/blog/#blog0001
binomial heap
meld を最悪O(log n)で処理できるけど上2つと比べてそんなに速いわけでもなくて実装面倒。
pairing heap
meldable heapの中で最速らしいけど多分いらない
relaxed heap
insertを最悪O(1)で実行できる。使うことなさそうだし日本語の資料もないし実装する気ない。
http://emoken.net/blog2/item_2137.html
fibonacchi heap
観賞用
interval heap
minとmaxの取得、削除ができる。ビームサーチで使えそう？
https://topcoder.g.hatena.ne.jp/spaghetti_source/20121006/1349491389
ICPC2013国内予選F
F問題が良問だったので解説記事を書くことにしました。
no title
解法は
Fは典型に区間DPで[s,t]を文字cに出来るかをやって最後に一致させるのをまたDPするだけ
という神々の言葉を聞いてなんとかわかりましたがヒントなしじゃとても解ける気がしないです。
この問題を解くには最初にCYK法で全ての部分区間についてある文字に変えられるかを調べる必要があります。
標準的なCYK法では書き換えルールは xy→z のように2文字から1文字に変えるルールしかないので、CYK内部で部分区間[i,j]をxy→zで書き換えられるかは Any(dp[i][k][x] And dp[k+1][j][y]) (k=i,i+1..,j-1)
で判定できますが、この問題では書き換え前の列の長さが2より大きいものがルールに含まれるので上記の方法ではできません。
ですがCYK法は区間DPなのである区間について考えるときその部分区間がある文字に書き換えられるかは全て求まっています。
なのでCYK内部で、ある区間をあるルールで書き換えられるかという問題は「文字列についてそれぞれの区間がある文字に変換できるという条件下で、与えられた文字列をある文字列に変換できるか」という問題として表せます。
これなら普通にコンテストの問題として出そうだしそれほど難しくもないDPで解けます。
つまりCYK内部である区間をあるルールで書き換え可能かの判定のためにさらにDPするわけです。
次にこの問題の厄介そうなルールに「回転」がありますがこれはあまり考えなくていいです。
というのも循環させて見れば回転しても並びの順番は変わらないからです。
ただし典型区間DPでは[a,b] (a<=b) というような区間しか考えないのですが(a>b)のような場合でも回転することによって(a<b)にできるので(a>b)となる区間も調べる必要があります。
区間DPではある区間はそれより短い区間に依存するので区間の長さが短い順に確定させていけば何も考えなくてもトポロジカル順序を満たすので、区間DPを[a,b] (a>b)にも対応できるように拡張するのは簡単にできます。
あとはnm通りの回転の仕方について2つの列を最長一致させるDPすればいいだけですね。
実装面では数列に現れる数値の範囲は1～30なので変換できる値はビットフラグで持っています。
これによって最後の2つの列を一致させる部分にビット毎の論理積を使えるので高速化できます。
計算量は O((n^4+m^4)rk + n^3m^3)
コメントなしの読みにくいコードですが見たい人はどうぞ
#include<iostream> #include<cstring> #include<vector> #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; struct Rule{ vector<int> x; int y; }; void CYK(int trans[25][25],vector<Rule> &rule,vector<int> s){ memset(trans,0,sizeof(int)*25*25); rep(i,s.size()){ trans[i][i] |= 1<<s[i]; } bool dp[26][11]; rep(j,s.size()){ rep(i,s.size()){ rep(k,rule.size()){ if(j+1<rule[k].x.size())continue; memset(dp,false,sizeof(dp)); dp[0][0]=true; rep(g,j+1){ rep(h,rule[k].x.size()){ if(!dp[g][h])continue; rep(f,j+1-g){ if(trans[(i+g)%s.size()][(i+g+f)%s.size()]>>rule[k].x[h]&1) dp[g+f+1][h+1]=true; } } } if(dp[j+1][rule[k].x.size()]) trans[i][(i+j)%s.size()] |= 1<<rule[k].y; } } } } int main(){ int n,m,r; vector<int> a,b; vector<Rule> rule; int transa[25][25],transb[25][25]; int dp[26][26]; while(cin>>n>>m>>r,n|m|r){ a.resize(n); b.resize(m); rep(i,n)cin>>a[i]; rep(i,m)cin>>b[i]; rule.resize(r); rep(i,r){ int k,v; cin>>k; rule[i].x.resize(k); rep(j,k){ cin>>v; rule[i].x[j]=v; } cin>>rule[i].y; } CYK(transa,rule,a); CYK(transb,rule,b); int ans=-1; int sa=a.size(),sb=b.size(); rep(i,n){ rep(j,m){ memset(dp,-1,sizeof(dp)); dp[0][0]=0; rep(k,n){ rep(f,m){ if(dp[k][f]==-1)continue; rep(g,n-k){ rep(h,m-f){ if(transa[(i+k)%sa][(i+k+g)%sa] & transb[(j+f)%sb][(j+f+h)%sb]) dp[k+g+1][f+h+1]=max(dp[k+g+1][f+h+1],dp[k][f]+1); } } } } ans=max(ans,dp[n][m]); } } cout<<ans<<endl; } return 0; }
TCO2013 Round1B
TCO2013 Round1B
250
ソートして両端から取るだけ
500
縦の選び方を決めると横の選び方はgreedyに求まるのでビット全探索
int getMoves(vector <string> board, int R, int C) { int h=board.size(),w=board[0].size(); int ans=INF; vector<int> b(h); rep(i,h){ int m=0; rep(j,w)if(board[i][j]=='X')m|=1<<j; b[i]=m; } rep(i,1<<h){ int m=0; for(int j=0;j<h;){ if(i&1<<j){ j+=R; }else { m|=b[j]; j++; } } int s=0; rep(j,h)if(i&1<<j)s++; for(int j=0;j<w;){ if(m&1<<j){ s++; j+=C; }else j++; } ans=min(ans,s); } return ans; }
1000
反転の操作は可逆だから例えばredotopcとodcpoterを同じ文字列にできる場合はそれぞれを操作して取り得る文字列の集合は等しくなる。また、可逆であることから異なる集合は必ず互いに素となる。よって集合毎の個数をカウントし奇数個となっている集合の個数が答えとなる。また、文字列は２文字ごとに見れば末尾からgreedyに当てはめて任意の順にソートでき、各集合は互いに素だから適当に正規化しておけば効率的にカウントできる。
int getMin(vector <string> words) { map<vector<pair<char,char> > ,int> mp; map<vector<pair<char,char> > ,int>::iterator it; rep(i,words.size()){ string &s=words[i]; vector<pair<char,char> > v; rep(j,s.size()/2){ v.push_back(make_pair(min(s[j*2],s[j*2+1]),max(s[j*2],s[j*2+1]))); } sort(v.begin(),v.end()); if(s.size()&1){ v.push_back(make_pair(s[s.size()-1],'\0')); } ++mp[v]; } int ans=0; for(it=mp.begin();it!=mp.end();++it){ if(it->second&1)ans++; } return ans; }
ウェーブレット行列を実装した
元のデータに対して十分小さいサイズでありながら各種操作を高速に処理でき、文字列のみならず2次元データやグラフデータまで表現できるというウェーブレット行列を実装してみた。「高速文字列解析の世界」とかブログとか読んでやっとのことで実装した。
ウェーブレット行列の各操作のオーダーの表記では、文字集合のサイズをσ、文字列長をnとしている。
2014/8/25:プログラム修正
inline int popCount(unsigned int x){ x = (x>>1 & 0x55555555)+(x & 0x55555555); x = (x>>2 & 0x33333333)+(x & 0x33333333); x = (x>>4 & 0x0f0f0f0f)+(x & 0x0f0f0f0f); x = (x>>8 & 0x00ff00ff)+(x & 0x00ff00ff); return (x>>16)+(x & 0x0000ffff); } inline int kthRightmostPop(unsigned int pop1,int k){ unsigned int pop2,pop4,pop8,pop16; int pos=0; pop2 = (pop1>>1 & 0x55555555)+(pop1 & 0x55555555); pop4 = (pop2>>2 & 0x33333333)+(pop2 & 0x33333333); pop8 = (pop4>>4 & 0x0f0f0f0f)+(pop4 & 0x0f0f0f0f); pop16= (pop8>>8 & 0x00ff00ff)+(pop8 & 0x00ff00ff); if((pop16 &0x0000ffff) <= k){ k -= (pop16 &0x0000ffff); pos |= 16; } if((pop8>>pos&0x000000ff) <= k){ k -= (pop8>>pos&0x000000ff); pos |= 8; } if((pop4>>pos&0x0000000f) <= k){ k -= (pop4>>pos&0x0000000f); pos |= 4; } if((pop2>>pos&0x00000003) <= k){ k -= (pop2>>pos&0x00000003); pos |= 2; } if((pop1>>pos&0x00000001) <= k)pos |= 1; return pos; } //簡潔ビットベクトル //メモリ使用量:2nビット class BitVector{ int n; int blocks; vector<unsigned int> B; vector<int> r; public: BitVector(){} BitVector(int size){ init(size); } void init(int size){ n = size; blocks = (n>>5)+1; B.assign(blocks ,0); r.assign(blocks ,0); } void set(int k){ B[k>>5] |= 1<<(k&31); } void build(){ r[0]=0; for(int i=1;i<blocks;i++){ r[i] = popCount(B[i-1]) + r[i-1]; } } bool access(int k)const{ return B[k>>5] & 1<<(k&31); } //[0,k)の1の個数 int rank(int k)const{ return r[k>>5] + popCount(B[k>>5] & ((1<<(k&31))-1)); } //k+1番目の１の場所 //O(log n) int select1(int k)const{ int lb=0,ub=blocks; if(k==-1)return -1; while(ub-lb>1){ int m = (lb+ub)/2; if(k<r[m])ub=m; else lb=m; } k -= r[lb]; return lb<<5 | kthRightmostPop(B[lb],k); } //O(log n) int select0(int k)const{ int lb=0,ub=blocks; if(k==-1)return -1; while(ub-lb>1){ int m = (lb+ub)/2; if(k<(m<<5)-r[m])ub=m; else lb=m; } k -= (lb<<5)-r[lb]; return lb<<5 | kthRightmostPop(~B[lb],k); } }; //ウェーブレット行列 //Σ=[A-Za-z] class WaveletMatrix{ static const int BITLEN = 6;//文字のビット長 int len; BitVector bv[BITLEN]; int encode(char c)const{//6bit if('A'<=c&&c<='Z')return c-'A'; return c-'a'+('Z'-'A'+1); } char decode(int n)const{ if(0<=n&&n<26)return n+'A'; return n-26+'a'; } struct Node{ int height,s,e,code; Node(){} Node(int a,int b,int c,int d):height(a),s(b),e(c),code(d){}; bool operator <(Node a)const{return e-s<a.e-a.s;} }; public: int length()const{ return len; } WaveletMatrix(const string &str){ init(str); } //O(n logσ) void init(const string &str){ len = str.size(); for(int i=0;i<BITLEN;i++){ bv[i].init(str.size()); } int *bucket; bucket = new int[2*len]; int *cur,*next; cur = bucket; next = bucket+len; int rank0[BITLEN]={0}; for(int i=0;i<len;i++){ int n = encode(str[i]); cur[i] = n; for(int j=BITLEN-1;j>=0;j--){ if((n&1<<j)==0)rank0[j]++; } } for(int i=BITLEN-1;;i--){ for(int j=0;j<len;j++){ if(cur[j]&1<<i)bv[i].set(j); } bv[i].build(); if(i==0)break; int idx0=0,idx1=rank0[i]; for(int j=0;j<len;j++){ if(cur[j]&1<<i)next[idx1++]=cur[j]; else next[idx0++]=cur[j]; } swap(cur,next); } delete[] bucket; } //O(logσ) char access(int k)const{ int code=0; for(int i=BITLEN-1;i>0;i--){ if(bv[i].access(k)){ code |= 1<<i; k = len-bv[i].rank(len)+bv[i].rank(k); }else{ k = k-bv[i].rank(k); } } if(bv[0].access(k))code |= 1; return decode(code); } //[s,e)中のcの個数 //O(logσ) int rank(char c,int s,int e)const{ int n = encode(c); for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } } return e-s; } //k+1番目のcの位置 //O(log n logσ) int select(char c,int k)const{ int n = encode(c); int s=0,e=len; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } } int p = s+k; if(e<=p)return -1; for(int i=0;i<BITLEN;i++){ if(n&1<<i)p = bv[i].select1(p-(len-bv[i].rank(len))); else p = bv[i].select0(p); } return p; } //[s,e)中で出現頻度が多い順にk個返す //O(min(e-s,σ)logσ) ,頻度が偏っていればO(klogσ) vector<pair<char,int> > topk(int s,int e,int k)const{ vector<pair<char,int> > res; priority_queue<Node> pq; pq.push(Node(BITLEN-1,s,e,0)); while(!pq.empty() && 0<=k){ Node a = pq.top(); pq.pop(); if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = a.s-ssum; pq.push(Node(a.height-1,s,s+num0,a.code)); s = len-bv[a.height].rank(len) + ssum; pq.push(Node(a.height-1,s,s+num1,a.code|1<<a.height)); } return res; } //[s,e)中のr+1番目に大きい文字 //O(logσ) char quantile(int s,int e,int r)const{ int code=0; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); int num1 = esum-ssum; if(num1<=r){ r -= num1; s = s-ssum; e = e-esum; }else{ code |= 1<<i; s = len-bv[i].rank(len) + ssum; e = s + num1; } if(s==e)return '\0'; } return decode(code); } //[s,e)中のx未満の文字の個数 int rank_lt(int s,int e,char x)const{ int n = encode(x); int res=0; for(int i=BITLEN-1;i>=0;i--){ int ssum = bv[i].rank(s); int esum = bv[i].rank(e); if(n&1<<i){ res += e-s-(esum-ssum); s = len-bv[i].rank(len) + ssum; e = s + esum-ssum; }else{ s = s-ssum; e = e-esum; } if(s==e)return res; } return res; } //[s,e)中の x<=c<y となる文字の個数 //O(logσ) int rangefreq(int s,int e,char x,char y)const{ return rank_lt(s,e,y)-rank_lt(s,e,x); } //[s,e)中に出現する文字を大きい順に頻度と共にk個返す //O(k logσ) vector<pair<char,int> > rangemaxk(int s,int e,int k)const{ Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,s,e,0); while(sp && 0<=k){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = a.s-ssum; if(num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); s = len-bv[a.height].rank(len) + ssum; if(num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); } return res; } //[s,e)中に出現する文字を小さい順に頻度と共にk個返す //O(k logσ) vector<pair<char,int> > rangemink(int s,int e,int k)const{ Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,s,e,0); while(sp && 0<=k){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); k--; continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = len-bv[a.height].rank(len) + ssum; if(num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); s = a.s-ssum; if(num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); } return res; } //[s,e)中のx<=c<yとなる文字cを頻度と共に列挙する //返す文字種類をkとすると O(k logσ) vector<pair<char,int> > rangelist(int s,int e,char x,char y)const{ int ub = encode(y); int lb = encode(x); Node sta[BITLEN+1]; int sp=0; vector<pair<char,int> > res; sta[sp++] = Node(BITLEN-1,0,len,0); while(sp){ Node a = sta[--sp]; if(a.height==-1){ res.push_back(make_pair(decode(a.code),a.e-a.s)); continue; } int ssum = bv[a.height].rank(a.s); int esum = bv[a.height].rank(a.e); int num1 = esum-ssum; int num0 = a.e-a.s-num1; int s = len-bv[a.height].rank(len) + ssum; if((a.code|1<<a.height)<ub && num1)sta[sp++] = Node(a.height-1,s,s+num1,a.code|1<<a.height); s = a.s-ssum; if(lb<=(a.code) && num0)sta[sp++] = Node(a.height-1,s,s+num0,a.code); } return res; } };
