当前位置:编程学习 > C/C++ >>

两侧覆盖问题解

线段树 + 生成树染色,标准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.zzzyk.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);  
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,