Codeforces Round#111(Div.2)E題Buses and People線分ツリー+離散化
この問題は一見離散化加線段樹であるが,どのように木を建てるかは確かに考えられなかった.しかし、busごとに時刻が異なるのを見ると、ヒントがあるかもしれません.
その後、神牛のコードを真似て書いた.
まず、busとpersonの起止座標を一緒に1つの配列に取り出し、それから離散化して、一人一人のbusにidを記録して、それからこれらの座標を並べ替えて、重くして、配列の大きさは線分の木の長さで、木を建てることができます.それから二分検索でbusと人の起止座標を配列の中の位置を探し出して、記録して、元の座標を置き換えて、それから人とbusを起点座標に従って左から右に構造体のソートを行います.
次に、セグメントツリーの部分であり、セグメントツリーの各ノードに格納される情報は集合であり、各要素はbusの時間とidによって形成されたpairである.木を建てるとき、最初は各ノードにbusが上書きされていなかったので、時間は無限大で、idは-1になりました.そして先ほど並べた構造体の配列で人を挙げ、各人に対して、出発駅が人の右側にないbusの情報を線分樹に挿入します.このようなbusだけが目的地に人を連れて行く可能性があります.また、busも順番に並べられているので、一人にとって、彼の前の人が乗れるbusが挿入されたら、これらのbusを繰り返し挿入する必要はありません.このようなメリットは明らかです.すべて挿入してクエリーを行うと、各ノードのset要素が多くなり、タイムアウトを招きます.このように最適化しても、最終的にはTLEに近いからです.挿入方法は簡単で、bus終点を含むすべての区間をそのbusの時間とidに挿入すればよい.
一人一人にとって、挿入が完了するとクエリーが行われ、クエリーの区間は必ずこの人が着く場所からセグメントツリーの末尾まで、そしてそのサブ区間に含まれるbus時間とidに対して、最小値を取ればよい.
全体的に,複雑度はn log(n)log(n)レベルである.
その中の1つのlog(n)はsetのinsertとlowerですbound関数がもたらした.
その後、神牛のコードを真似て書いた.
まず、busとpersonの起止座標を一緒に1つの配列に取り出し、それから離散化して、一人一人のbusにidを記録して、それからこれらの座標を並べ替えて、重くして、配列の大きさは線分の木の長さで、木を建てることができます.それから二分検索でbusと人の起止座標を配列の中の位置を探し出して、記録して、元の座標を置き換えて、それから人とbusを起点座標に従って左から右に構造体のソートを行います.
次に、セグメントツリーの部分であり、セグメントツリーの各ノードに格納される情報は集合であり、各要素はbusの時間とidによって形成されたpairである.木を建てるとき、最初は各ノードにbusが上書きされていなかったので、時間は無限大で、idは-1になりました.そして先ほど並べた構造体の配列で人を挙げ、各人に対して、出発駅が人の右側にないbusの情報を線分樹に挿入します.このようなbusだけが目的地に人を連れて行く可能性があります.また、busも順番に並べられているので、一人にとって、彼の前の人が乗れるbusが挿入されたら、これらのbusを繰り返し挿入する必要はありません.このようなメリットは明らかです.すべて挿入してクエリーを行うと、各ノードのset要素が多くなり、タイムアウトを招きます.このように最適化しても、最終的にはTLEに近いからです.挿入方法は簡単で、bus終点を含むすべての区間をそのbusの時間とidに挿入すればよい.
一人一人にとって、挿入が完了するとクエリーが行われ、クエリーの区間は必ずこの人が着く場所からセグメントツリーの末尾まで、そしてそのサブ区間に含まれるbus時間とidに対して、最小値を取ればよい.
全体的に,複雑度はn log(n)log(n)レベルである.
その中の1つのlog(n)はsetのinsertとlowerですbound関数がもたらした.
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 2000000000
#define MAXN 100005
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int tmp [4 * MAXN], cnt;
int ans[MAXN];
set<pair<int,int> >::iterator it;
struct Bus
{
int s, f, t, id;
bool operator <(const Bus a) const{
return s < a.s;
}
}bus[MAXN];
struct Person
{
int l, r, b, id;
bool operator <(const Person a) const{
return l < a.l;
}
}p[MAXN];
struct node
{
int left, right, mid;
set<pair<int, int> >v;
}tree[16 * MAXN];
int bi_search(int v)
{
int left = 0, right = cnt - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(tmp[mid] >= v) right = mid - 1;
else left = mid + 1;
}
return left;
}
void make_tree(int s, int e, int C)
{
tree[C].left = s;
tree[C].right = e;
tree[C].mid = (s + e) >> 1;
tree[C].v.insert(make_pair(INF, -1));
if(s == e) return ;
make_tree(s, tree[C].mid, L(C));
make_tree(tree[C].mid + 1, e, R(C));
}
void update(int p, pair<int, int > v, int C)
{
if(tree[C].left <= p && tree[C].right >= p) tree[C].v.insert(v);
if(tree[C].left == tree[C].right) return;
if(p <= tree[C].mid) update(p, v, L(C));
else update(p, v, R(C));
}
pair<int, int > query(int s, int e, int p, int C)
{
if(tree[C].left >= s && tree[C].right <= e)
{
it = tree[C].v.lower_bound(make_pair(p, -1));
return *it;
}
pair<int, int > x(INF, -1), y(INF, -1);
if(tree[C].mid >= s) x = query(s, e, p, L(C));
if(tree[C].mid < e) y = query(s, e, p, R(C));
return x.first < y.first ? x : y;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
cnt = 0;
for(int i = 0; i < n; i++)
{
scanf("%d%d%d", &bus[i].s, &bus[i].f, &bus[i].t);
bus[i].id = i + 1;
tmp[cnt++] = bus[i].s;tmp[cnt++] = bus[i].f;
}
for(int i = 0; i < m; i++)
{
scanf("%d%d%d", &p[i].l, &p[i].r, &p[i].b);
p[i].id = i + 1;
tmp[cnt++] = p[i].l;tmp[cnt++] = p[i].r;
}
sort(tmp, tmp + cnt);
cnt = unique(tmp, tmp + cnt) - tmp;
make_tree(0, cnt - 1, 1);
for(int i = 0; i < n; i++)
{
bus[i].s = bi_search(bus[i].s);
bus[i].f = bi_search(bus[i].f);
}
for(int i = 0; i < m; i++)
{
p[i].l = bi_search(p[i].l);
p[i].r = bi_search(p[i].r);
}
int pos = 0;
sort(bus, bus + n);
sort(p, p + m);
for(int i = 0; i < m; i++)
{
while(pos < n && bus[pos].s <= p[i].l)
{
update(bus[pos].f, make_pair(bus[pos].t, bus[pos].id), 1);
pos++;
}
pair<int, int> t = query(p[i].r, cnt - 1, p[i].b, 1);
ans[p[i].id] = t.second;
}
for(int i = 1; i <= m; i++)
{
if(i > 1) putchar(' ');
printf("%d", ans[i]);
}
puts("");
return 0;
}