两侧覆盖问题解

时间:2022-11-18 00:04:10

线段树 + 生成树染色,标准O(nlogn),再也不用担心会被卡了。。。

#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;
	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;
}