1

ここに問題があり、ここに解決策があります。

最初の部分は簡単です。どんなに頑張っても手に入らない第二部です。基本的に 2 つの間隔のセットがあり、1 つの間隔が別の間隔内に完全に収まっていない交差点をすべて見つける必要があります。

目が充血するまで問題設定コードを見つめていました。まだこのビットを理解できません:

for(int L=n;L>=1;L--) {
   FOR(it, r[L]) add(*it, -1);
   add(L, 1);
   r[left[L]].push_back(L);
   ans += ask(right[L]-1);
}

それはどのように機能しますか？アルゴリズムは何ですか？

社説には、インターバルツリーまたは「バイナリインデックスツリー」を使用してこれを解決できることが記載されています。間隔ツリーとは何か、またどのように役立つかについては、多かれ少なかれ理解しています。しかし、プロブレム セッターは明らかにそれを使用しておらず、「バイナリ インデックス ツリー」は検索に表示されません。関連性があることは確かですが、その方法がわかりません）。

何か助けはありますか？読む必要のある文献へのポインタはありますか?

4

2 に答える 2

1

はい、わかった。これはバイナリ インデックス ツリーです - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees。そして、はい、それは関連しています。

于 2014-08-12T21:46:26.113 に答える