二次联通门 : LibreOJ #6192. 「美团 CodeM 复赛」城市网络
/* LibreOJ #6192. 「美团 CodeM 复赛」城市网络 二分 + 单调栈 离线操作 维护一个严格单调的栈 对于一个询问的答案 就是以当前价值为限的单调栈的大小 二分实现即可 (我不会说是我不会倍增而硬是乱搞的) */ #include <cstdio> #include <iostream> #include <vector> #define INF 1e9 const int BUF = 12312312; char Buf[BUF], *buf = Buf; using std :: max; inline void read (int &now) { for (now = 0; !isdigit (*buf); ++ buf); for (; isdigit (*buf); now = now * 10 + *buf - '0', ++ buf); } #define Max 100010 struct E { E *n; int to; }; E *list[Max], poor[Max << 1], *Ta = poor; int key[Max], deep[Max]; struct Data { int x, y; }; inline void In (int u, int v) { ++ Ta, Ta->to = v, Ta->n = list[u], list[u] = Ta; ++ Ta, Ta->to = u, Ta->n = list[v], list[v] = Ta; } Data Stack[Max]; int N, top, Answer[Max]; struct Q { int to, key, Id; Q () {} Q (int x, int y, int z) { to = x, key = y, Id = z; } }; std :: vector <Q> data[Max]; void Dfs (int now, int Father) { int l = 0, r = top + 1, Mid, pos; for (; l + 1 < r; ) { Mid = l + r >> 1; if (Stack[Mid].x > key[now]) l = Mid; else r = Mid; } int t = top; top = r; Data res = Stack[r]; Stack[top].x = key[now], Stack[top].y = now; if (now == 7) { for (int i = 1; i <= top; ++ i) printf ("%d %d ", Stack[i].x, Stack[i].y); puts (""); } for (std :: vector <Q> :: iterator i = data[now].begin (); i != data[now].end (); ++ i) { int _l = 0, _r = top + 1, _Mid; for (; _l + 1 < _r; ) { _Mid = (_l + _r + 1) >> 1; if (Stack[_Mid].x > (*i).key) _l = _Mid; else _r = _Mid; } int __l = 0, __r = top + 1, __Mid; for (; __l + 1 < __r; ) { __Mid = (__l + __r + 1) >> 1; if (deep[Stack[__Mid].y] < deep[(*i).to]) __l = __Mid; else __r = __Mid; } if (now == 7) printf (" %d %d ", _l, __l); Answer[(*i).Id] = max (0, _l - __l); } for (E *e = list[now]; e; e = e->n) if (e->to != Father) { deep[e->to] = deep[now] + 1; Dfs (e->to, now); } Stack[top] = res, top = t; } int Main () { freopen ("1.in", "r", stdin); fread (buf, 1, BUF, stdin); int x, y, M; int z; read (N), read (M); register int i, j; for (i = 1; i <= N; ++ i) read (key[i]); for (i = 1; i < N; ++ i) { read (x), read (y); In (x, y); } for (i = 1; i <= M; ++ i) { read (x), read (y), read (z); data[x].push_back (Q (y, z, i)); } deep[1] = 0, Stack[0].x = INF, Stack[0].y = 0; for (Dfs (1, 0), i = 1; i <= M; ++ i) printf ("%d ", Answer[i]); return 0; } int ZlycerQan = Main (); int main (int argc, char *argv[]) {;}