BZOJ3693: 圆桌会议(Hall定理线段树)

题意

Sol

好的又是神仙题。。。

我的思路：对于区间分两种情况讨论，一种是完全包含，另一种是部分包含。
第一种情况非常好判断，至于计算对于一个区间[l, r]的$\sum a[i]$就可以了，但是后两种呢？qwq。想了半天也没想出来。
看了下题解，果然还有更高端的操作！

首先这题可以看是二分图匹配，最暴力的写法是对于每个a[i]，直接拆成a[i]个点，然后分别向$[l_i, r_i]$连边，最后看是否能完全匹配。

有一个专门判断这玩意儿的定理：

Hall定理：
二部图G中的两部分顶点组成的集合分别为$X, Y$, $X = \{X1, X2, X3,X4,.........,Xm\},$Y=\{y1, y2, y3, y4 ,.........,yn\},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是：
X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)

对于此题来说，直接应用Hall定理得到的推论为：对于任意的x个人，都至少对应x条边与其相连

然而这样好像还是不好搞，考虑一步步推广

1、对于任意一个询问$[l, r], a_i$，若$a_i$满足要求，那么任意的$x <= a_i$，都满足要求。

这是显然的，因为每个$a_i$连的点都是相同的

2、对于任意的区间$[l, r]$，若他们包含的$a[i]$, $\sum a[i] <= r - l + 1$满足条件，则去掉任意的$a[i]$后，该区间仍然满足条件。

同样显然。

这样我们就把给出的问题转化为：判断对于任意$[l_j, r_i]$，是否满足条件

对所有询问按右端点排序后线段树维护

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<vector>

#include<cstring>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

#define LL long long

using namespace std;

const int MAXN =  * 1e6 + , mod = 1e9 + ;

inline LL read() {

    char c = getchar(); LL x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

#define ls k << 1

#define rs k << 1 | 1

int T, N, M;

int mx[MAXN], f[MAXN], date[MAXN];

struct Qu {

    int l, r, a;

    bool operator < (const Qu &rhs) const {

        return r == rhs.r ? l < rhs.l : r < rhs.r;

    }

}q[MAXN];

void update(int k) {

    mx[k] = max(mx[ls], mx[rs]);

}

void add(int k, int val) {

    mx[k] += val, f[k] += val;

}

void pushdown(int k) {

    if(f[k]) add(ls, f[k]), add(rs, f[k]), f[k] = ;

}

void IntAdd(int k, int ll, int rr, int l, int r, int val) {

    if(ll <= l && r <= rr) {add(k, val); return ;}

    int mid = l + r >> ;

    pushdown(k);

    if(ll <= mid) IntAdd(ls, ll, rr, l, mid, val);

    if(rr >  mid) IntAdd(rs, ll, rr, mid + , r, val);

    update(k);

}

int Query(int k, int ll, int rr, int l, int r) {

    if(ll <= l && r <= rr) return mx[k];

    int mid = l + r >> ;

    pushdown(k);

    if(ll > mid) return Query(rs, ll, rr, mid + , r);

    else if(rr <= mid) return Query(ls, ll, rr, l, mid);

    else return max(Query(ls, ll, rr, l, mid), Query(rs, ll, rr, mid + , r));

}

main() {

T = read();

while(T--) {

    memset(mx, , sizeof(mx));

    memset(f, , sizeof(f));

    N = read(); M = read();

    int cnt = , tot = ;

    LL sum = ;

    for(int i = ; i <= N; i++) {

        q[++cnt].l = read(), q[cnt].r = read(), q[cnt].a = read();

        sum += q[cnt].a;

        if(q[cnt].l > q[cnt].r) q[cnt].r += M;

        else if(q[cnt].r < M) q[cnt + ] = (Qu) {q[cnt].l + M, q[cnt].r + M, q[cnt].a}, cnt++;

    }

    if(sum > M) {puts("No"); continue;}

    for(int i = ; i <= cnt; i++) q[i].l++, q[i].r++, date[++tot] = q[i].l, date[++tot] = q[i].r;

    for(int i = ; i <=  * N; i++) date[++tot] = i;

    sort(q + , q + cnt + );

    sort(date + , date + tot + );

    tot = unique(date + , date + tot + ) - date - ;

    int cur = , flag = ;

    for(int i = ; i <= cnt; i++) {

        int l = q[i].l, r = q[i].r;

        l = lower_bound(date + , date + tot + , l) - date;

        r = lower_bound(date + , date + tot + , r) - date;

        while(cur < r) cur++, IntAdd(, cur, cur, , tot, date[cur] - );

        IntAdd(, , l, , tot, q[i].a);

        int val = Query(, , r, , tot);

        if(val > date[r]) {puts("No"); flag = ; break;}

    }

    if(!flag) puts("Yes");

}

    return ;

}

巴特西

BZOJ3693: 圆桌会议(Hall定理线段树)

题意

Sol

最新文章

热门文章

巴特西

BZOJ3693: 圆桌会议(Hall定理 线段树)

题意

Sol

最新文章

热门文章

BZOJ3693: 圆桌会议(Hall定理线段树)