BZOJ1594【USACO2008 Jan】猜数游戏 <二分答案+线段树>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【Usaco2008 Jan】猜数游戏

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  162  MB\mathrm{Memory\;Limit:\;162\;MB}

Description

为了提高自己低得可怜的智商，奶牛们设计了一个新的猜数游戏，来锻炼她们的逻辑推理能力。
游戏开始前，一头指定的奶牛会在牛棚后面摆N  (1≤N≤106)N\;(1\le N\le 10^6)堆干草，每堆有若干捆，并且没有哪两堆中的草一样多。
所有草堆排成一条直线，从左到右依次按1∼N1\sim N编号，每堆中草的捆数在[1,109][1,10^9]之间。
然后，游戏开始。
另一头参与游戏的奶牛会问那头摆干草的奶牛Q  (1≤Q≤25000)Q\;(1\le Q\le 25000)个问题，问题的格式如下：
编号为Ql∼Qh  (1≤Ql≤Qh≤N)Q_l\sim Q_h\;(1\le Q_l\le Q_h\le N)的草堆中，最小的那堆里有多少捆草？
对于每个问题，摆干草的奶牛回答一个数字AA，但或许是不想让提问的奶牛那么容易地得到答案，又或许是她自己可能记错每堆中干草的捆数，总之，她的回答不保证是正确的。
请你帮助提问的奶牛判断一下，摆干草的奶牛的回答是否有自相矛盾之处。

Input

  • 第11行: 22个用空格隔开的整数：NN和QQ
  • 第2∼Q+12\sim Q+1行: 每行为33个用空格隔开的整数Ql,Qh,AQ_l,Q_h,A，描述了一个问题以及它对应的回答

Output

如果摆干草的奶牛有可能完全正确地回答了这些问题，输出00；否则输出11个1∼Q1\sim Q中的数，表示这个问题的答案与它之前的那些回答有冲突之处。
注意：如果有冲突出现输出一个数mm，使得前m−1m-1个命题不冲突。

Sample Input

1
2
3
4
5
20 4
1 10 7
5 19 7
3 12 8
11 15 12

Sample Output

1
3

Source

Gold

标签：二分答案 线段树

Solution

二分答案，设二分到mm，需要判断第1∼m1\sim m个条件是否不存在矛盾（最后答案加一）。

将第1∼m1\sim m个条件按AA从大到小排序，每次找出一段AA相同的条件，求其区间的并。可知值为AA的数一定在这个并中。因此若这个并不存在，则一定矛盾。另一种矛盾的情况是存在一个包含这个并的区间，其答案大于AA。对于这种情况，我们在每次操作完一组AA相同的条件后，对这些区间的交做标记。若一组AA相同的条件的区间并完全被打上标记，意味着其被前面的AA更大的区间覆盖，即存在一个包含该并的区间，其答案大于AA。这个标记可以在线段树上维护。

综上，check的复杂度是O(mlog⁡N)O(m\log{N})，总时间复杂度为O(Qlog⁡Nlog⁡Q)O(Q\log{N}\log{Q})。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
#define MAX_M 25000
#define MAX_N 1000000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m; bool tr[MAX_N<<2];
struct node {int l, r, mi;} a[MAX_M+5], b[MAX_M+5];
bool cmp(const node &x, const node &y) {return x.mi > y.mi;}
void modify(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {tr[v] = true; return;}
    if (l <= mid) modify(v<<1, s, mid, l, r);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
    if (!tr[v]) tr[v] = tr[v<<1]&tr[v<<1|1];
}
bool query(int v, int s, int t, int l, int r) {
    if (tr[v] || (s >= l && t <= r)) return tr[v];
    bool ret = true;
    if (l <= mid) ret &= query(v<<1, s, mid, l, r);
    if (r >= mid+1) ret &= query(v<<1|1, mid+1, t, l, r);
    return ret;
}
bool chk(int nn) {
    for (int i = 1; i <= nn; i++) b[i] = a[i];
    sort(b+1, b+nn+1, cmp); memset(tr, 0, sizeof tr);
    for (int s = 1, t, l = 1, r = n; s <= nn; s = t+1, l = 1, r = n) {
        for (t = s; t < nn && b[t+1].mi == b[s].mi; t++) ;
        for (int i = s; i <= t; i++)
            l = max(l, b[i].l), r = min(r, b[i].r);
        if (l > r || query(1, 1, n, l, r)) return false;
        for (int i = s; i <= t; i++)
            l = min(l, b[i].l), r = max(r, b[i].r);
        modify(1, 1, n, l, r);
    }
    return true;
}
int bi_search() {
    int s = 1, t = m, ret = 0;
    while (s <= t)
        if (!chk(mid)) t = mid-1;
        else ret = mid, s = mid+1;
    return (ret+1)%(m+1);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= m; i++)
        read(a[i].l), read(a[i].r), read(a[i].mi);
    return printf("%d\n", bi_search()), 0;
}