A simple Blog for wyx I've been down the bottle hoping.
4881: [Lydsy2017年5月月赛]线段游戏 线段树 二分图判定
发表于: | 分类: Oi | 评论:0 | 阅读:65

首先我们对于相交的两条线段之间连一条边然后考虑检验生成的图形是否是二分图

这个原理就是考虑我们取出的东西必然在一侧,否则必然相交,如果不是二分图就说明形成的奇环中必然会使得取出的边相交

然后就是怎么快点二分图染色的问题了

考虑大力线段树,每次找出可能符合条件的两个点然后如果合法就递归

每次递归必然要删掉一个点然后总的询问次数不超过$2n$所以复杂度没毛病

然后就是思博题了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int mod = 998244353;
const int N = 1e5+5;
const int M = N << 2;
using namespace std;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int n;
int Max[M], Min[M], a[N];
int col[N];

inline int merge_mx(int x,int y) {
    if(!x || !y) return x + y;
    return a[x] > a[y] ? x : y;
}

inline int merge_mn(int x,int y) {
    if(!x || !y) return x + y;
    return a[x] < a[y] ? x : y;
}

inline void updata(int k) {
    Max[k] = merge_mx(Max[k<<1], Max[k<<1|1]);
    Min[k] = merge_mn(Min[k<<1], Min[k<<1|1]);
}

int pos[N];

inline void build(int k,int l,int r) {
    if(l==r) {
        Max[k] = Min[k] = l;
        pos[l] = k;
        return;
    }
    int mid = (l+r) >> 1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

inline void del(int k) {
    k = pos[k];
    Min[k] = Max[k] = 0;
    for(k>>=1;k;k>>=1) updata(k);
}

int ans;

inline void ask_mx(int k,int l,int r,int x,int y) {
    if(x <= l && r <= y) {
        ans = merge_mx(ans, Max[k]);
        return ;
    }
    int mid = (l+r) >> 1;
    if(x <= mid) ask_mx(k<<1,l,mid,x,y);
    if(y > mid) ask_mx(k<<1|1,mid+1,r,x,y);
}

inline void ask_mn(int k,int l,int r,int x,int y) {
    if(x <= l && r <= y) {
        ans = merge_mn(ans, Min[k]);
        return;
    }
    int mid = (l+r) >> 1;
    if(x <= mid) ask_mn(k<<1,l,mid,x,y);
    if(y > mid) ask_mn(k<<1|1,mid+1,r,x,y);
}

inline void DFS(int x,int y) {
    del(x);
    col[x] = y;
    y = 3 - y;
    while(1) {
        ans = 0;
        ask_mn(1,1,n,x,n);
        if(ans && a[ans] < a[x]) DFS(ans, y); 
        else break;
    }
    while(1) {
        ans = 0;
        ask_mx(1,1,n,1,x);
        if(ans && a[ans] > a[x]) DFS(ans, y);
        else break;
    }
}

int f[20];

int main() {
    n = read();
    for(int i=1;i<=n;++i) a[i] = read();
    build(1,1,n);
    int cnt = 0;
    for(int i=1;i<=n;++i) {
        if(!col[i]) {
            DFS(i,1);
            cnt ++;
        }
    }
    for(int i=1;i<=n;++i) {
        if(a[i] < f[col[i]]) return 0*puts("0");
        f[col[i]] = a[i];
    }
    ans = 1;
    while(cnt --) {
        ans = ans << 1;
        ans %= mod;
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP