当前位置： 移动技术网 > IT编程>开发语言>C/C++ > BZOJ3693: 圆桌会议(Hall定理 线段树)

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

2018年09月21日  | 移动技术网IT编程  | 我要评论

非常了得报名,电影下载 迅雷下载,假性尖锐湿疣会痒吗

题意

题目链接

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 = 2 * 1e6 + 10, mod = 1e9 + 7;
inline ll read() {
    char c = getchar(); ll x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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] = 0;
}
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 >> 1;
    pushdown(k);
    if(ll <= mid) intadd(ls, ll, rr, l, mid, val);
    if(rr >  mid) intadd(rs, ll, rr, mid + 1, 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 >> 1;
    pushdown(k);
    if(ll > mid) return query(rs, ll, rr, mid + 1, 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 + 1, r));
}
main() {
t = read(); 
while(t--) {
    memset(mx, 0, sizeof(mx));
    memset(f, 0, sizeof(f));
    n = read(); m = read();
    int cnt = 0, tot = 0;
    ll sum = 0;
    for(int i = 1; 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 + 1] = (qu) {q[cnt].l + m, q[cnt].r + m, q[cnt].a}, cnt++;
    }
    if(sum > m) {puts("no"); continue;}
    for(int i = 1; i <= cnt; i++) q[i].l++, q[i].r++, date[++tot] = q[i].l, date[++tot] = q[i].r;
    for(int i = 1; i <= 2 * n; i++) date[++tot] = i;

    sort(q + 1, q + cnt + 1);
    sort(date + 1, date + tot + 1);
    tot = unique(date + 1, date + tot + 1) - date - 1;
    
    
    int cur = 0, flag = 0;
    for(int i = 1; i <= cnt; i++) {
        int l = q[i].l, r = q[i].r;
        l = lower_bound(date + 1, date + tot + 1, l) - date;
        r = lower_bound(date + 1, date + tot + 1, r) - date;
        while(cur < r) cur++, intadd(1, cur, cur, 1, tot, date[cur] - 1);
        intadd(1, 1, l, 1, tot, q[i].a);
        int val = query(1, 1, r, 1, tot);
        if(val > date[r]) {puts("no"); flag = 1; break;}
    }
    if(!flag) puts("yes");
 
}
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网