传送门
良心题解
#include <set> #include <cstdio> #include <iostream> #include <algorithm> #define N 100001 #define LL long long #define INF (~(1 << 31)) using namespace std; int n, c, h = 1, ans, ans1; int f[N], sum[N]; struct node }p[N]; multiset <node> s; multiset <node> :: iterator it; inline bool operator < (const node &a, const node &b) inline int read() inline int find(int x) inline int merge(int x, int y) } int main() sort(p + 1, p + n + 1); s.insert(node(INF, 0)); s.insert(node(INF, 0)); for(i = 1; i <= n; i++) y = p[i].y; it = s.lower_bound(node(p[i].y, i)); node r = *it, l = *it; if(r.x y <= c) merge(r.y, i); if(y l.x <= c) merge(l.y, i); s.insert(node(p[i].y, i)); } for(i = 1; i <= n; i++) sum[find(i)]++; for(i = 1; i <= n; i++) ans1 = max(ans1, sum[i]); printf("%d %d\n", ans, ans1); return 0; }
上一篇：【模板】AC自动机
下一篇：[BZOJ1583] [Usaco2009 Mar]Moon Mooing 哞哞叫（队列）
stl 好题 并查集
