線段樹 + 生成樹染色，標准O(nlogn)，再也不用擔心會被卡了。。。 [cpp] #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> /* #include <ctime> #include <cctype> #include <map> #include <set> #include <string> #include <queue> #include <iostream> #include <fstream> */ #include <algorithm> using namespace std; #ifdef WIN32 #define fmt64 "%I64d" #else #define fmt64 "%lld" #endif #define PI M_PI #define oo 0x13131313 #define PB push_back #define PO pop_back #define MP make_pair #define iter iterator #define fst first #define snd second #define cstr(a) (a).c_str() #define FOR(i, j, k) for (i = (j); i <= (k); ++i) #define ROF(i, j, k) for (i = (j); i >= (k); --i) #define FER(e, d, u) for (e = d[u]; e; e = e->n) #define FRE(i, a) for (i = (a).begin(); i != (a).end(); ++i) typedef unsigned int uint; typedef long long int64; typedef unsigned long long uint64; typedef long double real; template<class T> inline bool minim(T &a, const T &b) {return b < a ? a = b, 1 : 0;} template<class T> inline bool maxim(T &a, const T &b) {return b > a ? a = b, 1 : 0;} template<class T> inline T sqr(const T &a) {return a * a;} #define maxn 300005 #define updatex(p) (p->x = ll[p->s->x] < ll[p->t->x] ? p->s->x : p->t->x) #define updatey(p) (p->y = rr[p->s->y] > rr[p->t->y] ? p->s->y : p->t->y) int n, m; int ll[maxn], rr[maxn]; int lx[maxn], rx[maxn]; int ly[maxn], ry[maxn]; struct node {node *s, *t, *f; int l, r, x, y;}; node ns[maxn*2], *nt = ns, *root, *bk[maxn]; int pt, lt, rt; char c[maxn]; int p[maxn], q[maxn], hd, tl; node *build(int l, int r) { node *p = ++nt; p->l = l, p->r = r; if (l == r) return bk[l] = p; (p->s = build(l, (l+r) >> 1))->f = p; return (p->t = build(((l+r) >> 1)+1, r))->f = p; } void insertx(int u) { node *p = bk[rr[u]]; lx[p->x] = u, rx[u] = p->x, p->x = u; for (p = p->f; p; p = p->f) updatex(p); } void inserty(int u) { node *p = bk[ll[u]]; ly[p->y] = u, ry[u] = p->y, p->y = u; for (p = p->f; p; p = p->f) updatey(p); } void remove(int u) { node *p = bk[rr[u]]; bool flag = u == p->x; rx[lx[u]] = rx[u], lx[rx[u]] = lx[u]; if (flag) { p->x = rx[u]; for (p = p->f; p; p = p->f) updatex(p); } p = bk[ll[u]], flag = u == p->y; ry[ly[u]] = ry[u], ly[ry[u]] = ly[u]; if (flag) { p->y = ry[u]; for (p = p->f; p; p = p->f) updatey(p); } } void query(node *p) { if (lt < p->l && p->r < rt) { for (; ll[p->x] < lt; remove(p->x)) c[q[++tl] = p->x] = -c[pt]; for (; rr[p->y] > rt; remove(p->y)) c[q[++tl] = p->y] = -c[pt]; } else { if (lt < p->s->r && (ll[p->s->x] < lt || rr[p->s->y] > rt)) query(p->s); if (rt > p->t->l && (ll[p->t->x] < lt || rr[p->t->y] > rt)) query(p->t); } } int a[maxn], b[maxn]; int tx, ty; int top, stk[maxn]; bool cmp(int i, int j) { return ll[i] < ll[j] || (ll[i] == ll[j] && rr[i] > rr[j]); } void solve(int *a, int n) { sort(a + 1, a + n + 1, cmp); stk[top = 1] = a[1]; for (int i = 2; i <= n; ++i) { for (; top && rr[a[i]] > rr[stk[top]]; --top) if (ll[a[i]] < rr[stk[top]]) puts("NIE"), exit(0); } } void bfs(int S) { for (c[q[hd = tl = 1] = S] = 1; hd <= tl; ++hd) remove(pt = q[hd]), lt = ll[pt], rt = rr[pt], query(root); tx = ty = 0; for (int i = 1; i <= tl; ++i) if (~c[q[i]]) a[++tx] = q[i]; else b[++ty] = q[i]; solve(a, tx), solve(b, ty); } bool bigger1(int i, int j) {return ll[i] > ll[j];} bool bigger2(int i, int j) {return rr[i] < rr[j];} int main() { freopen("aut.in", "r", stdin); freopen("aut.out", "w", stdout); scanf("%d%d", &n, &m); int i; www.2cto.com FOR(i, 1, m) scanf("%d%d", ll + i, rr + i), p[i] = i; ll[0] = oo, rr[0] = -oo; root = build(1, n); sort(p + 1, p + m + 1, bigger1); FOR(i, 1, m) insertx(p[i]); sort(p + 1, p + m + 1, bigger2); FOR(i, 1, m) inserty(p[i]); FOR(i, 1, m) if (!c[i]) bfs(i); FOR(i, 1, m) puts(c[i] < 0 ? "N" : "S"); return 0; }
