2013
11-13

# Haybale Guessing

The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.

A designated ‘Hay Cow’ hides behind the barn and creates N (1 ≤ N ≤ 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.

The other cows then ask the Hay Cow a series of Q (1 ≤ Q ≤ 25,000) questions about the the stacks, all having the same form:

What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ≤ QlN; QlQhN)?

The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.

Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.

* Line 1: Two space-separated integers: N and Q
* Lines 2..Q+1: Each line contains three space-separated integers that represent a single query and its reply: Ql, Qh, and A

* Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise, print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.

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


3


//* @author
/*题目问题可以转化为判断questions是否矛盾, 然后二分找到最先发生矛盾的question.
*那如何判断矛盾? 若我们把questions依照Ai值从大到小的顺序进行区间覆盖, 若一个区间加入时,
* 此区间已被完全覆盖, 则说明此区间的取

*值均比Ai大, 故questions矛盾, 否则一定可以构造出一个取值分布.
*区间覆盖最好的方法应该是线段树, 然而此题只需要判断某段区间是否被覆盖, 所以可以用并查集维护.
*复杂度O(aQlogQ)(a为并查集系数)
*/
/**
* @version 2009/08/22
* @author sbzlyessit
*/

import java.io.*;
import java.util.*;

public class Main {

private static final int        MAX_N = 25000;

private static StringTokenizer  st;
private static int[][]          que = new int[MAX_N][3];
private static int[]            x = new int[2 * MAX_N];
private static Integer[]        list = new Integer[MAX_N];
private static int[]            r = new int[2 * MAX_N];
private static boolean[]        used = new boolean[2 * MAX_N];
private static int              N, xSize;

public static void main(String[] argv) throws Exception {
solve();
}

private static void readIn() throws Exception {
int i, temp;
nextInt();
N = nextInt();
for (xSize = 0, i = 0; i < N; i++) {
que[i][0] = x[xSize++] = nextInt();
que[i][1] = x[xSize++] = nextInt() + 1;
que[i][2] = nextInt();
list[i] = i;
}
Arrays.sort(x, 0, xSize);
for (temp = xSize, xSize = i = 1; i < temp; i++) {
if (x[i] != x[i - 1]) {
x[xSize++] = x[i];
}
}
for (i = 0; i < N; i++) {
que[i][0] = Arrays.binarySearch(x, 0, xSize, que[i][0]);
que[i][1] = Arrays.binarySearch(x, 0, xSize, que[i][1]);
}
Arrays.sort(list, 0, N, new Comparator(){
public int compare(Integer a, Integer b) {
return que[a][2] < que[b][2] ? 1 : -1;
}
});
}

private static void solve() {
int min = 0, max = N - 1, mid;
while (min < max) {
mid = (min + max + 1) / 2;
if (check(mid)) {
min = mid;
} else {
max = mid - 1;
}
}
if (min == N - 1) {
System.out.println(0);
} else {
System.out.println(min + 2);
}
}

private static boolean check(int pos) {
int     i, j, x, min, max;
boolean found;
for (i = 0; i < xSize - 1; i++) {
r[i] = -1;
used[i] = false;
}
for (i = 0; i < N; i++) {
x = list[i];
if (i == 0 || que[x][2] != que[list[i - 1]][2]) {
min = Integer.MIN_VALUE;
max = Integer.MAX_VALUE;
for (j = i; j < N && que[list[j]][2] == que[x][2]; j++) {
if (list[j] <= pos) {
min = Math.max(min, que[list[j]][0]);
max = Math.min(max, que[list[j]][1]);
}
}
if (min != Integer.MIN_VALUE) {
for (found = false, j = min; j < max; j++) {
if (!used[j]) {
used[j] = found = true;
insert(j);
}
j = find(j);
}
if (!found) {
return false;
}
}
}
if (x <= pos) {
for (j = que[x][0]; j < que[x][1]; j++) {
if (!used[j]) {
used[j] = true;
insert(j);
}
j = find(j);
}
}
}
return true;
}

private static void insert(int pos) {
if (pos > 0 && used[pos - 1]) {
r[pos - 1] = pos;
}
if (pos < xSize - 2 && used[pos + 1]) {
r[pos] = find(pos + 1);
}
}

private static int find(int x) {
int y = x, z;
while (r[y] != -1) {
y = r[y];
}
while (x != y) {
z = x;
x = r[x];
r[z] = y;
}
return y;
}

private static int nextInt() throws Exception {
while (st == null || !st.hasMoreTokens()) {
}
return Integer.parseInt(st.nextToken());
}

}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

3. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？