P2898 [USACO08JAN]haybale猜测Haybale Guessing

admin · 发表于 2018-9-3 18:06:07

https://www.luogu.org/problemnew/show/P2898

题目描述
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 ≤ Ql ≤ N; Ql ≤ Qh ≤ N)?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.

给一段长度为n，每个位置上的数都不同的序列a[1..n]和q和问答，每个问答是(x, y, r)代表RMQ(a, x, y) = r, 要你给出最早的有矛盾的那个问答的编号。

输入输出格式
输入格式：
* 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.

输入输出样例
输入样例#1：
20 4
1 10 7
5 19 7
3 12 8
11 15 12
输出样例#1：
3

admin · 发表于 2018-9-3 18:08:17

来一发pas的程序

program syj; {erfen ans+range covering_using bingcha set}
const
maxn=25000+5;
var n,q,nn,l,r,mid,i:longint;
x,c,p,f,color:array[0..maxn*4]of longint;
a:array[1..maxn]of longint;
procedure sort1(l,r:longint);
var i,j,k,z:longint;
begin
i:=l;j:=r;k:=x[(l+r) div 2];
repeat
while x[i]<k do inc(i);
while x[j]>k do dec(j);
if i<=j then begin
z:=x[i];x[i]:=x[j];x[j]:=z;
z:=c[i];c[i]:=c[j];c[j]:=z;
inc(i);dec(j);
end;
until i>j;
if l<j then sort1(l,j);
if i<r then sort1(i,r);
end;
procedure sort2(l,r:longint);
var i,j,k,kk,z:longint;
begin
i:=l;j:=r;k:=a[c[(l+r) div 2]];kk:=p[c[(l+r) div 2]];
repeat
while (a[c[i]]>k) or (a[c[i]]=k)and(p[c[i]]<kk) do inc(i);
while (a[c[j]]<k) or (a[c[j]]=k)and(p[c[j]]>kk) do dec(j);
if i<=j then begin
z:=c[i];c[i]:=c[j];c[j]:=z;
inc(i);dec(j);
end;
until i>j;
if l<j then sort2(l,j);
if i<r then sort2(i,r);
end;
function find(x:longint):longint;
begin
if f[x]<>x then f[x]:=find(f[x]); find:=f[x];
end;
function check(kk:longint):boolean;
var u,i,j,k,l,r,ii,ll,rr:longint;
ok:boolean;
begin
for i:=1 to kk do c[i]:=i;
sort2(1,kk);
for i:=1 to nn do begin f[i]:=i;color[i]:=0; end;
k:=1;
for i:=1 to kk do if (i=kk)or(a[c[i]]<>a[c[i+1]]) then begin
l:=p[c[k]];r:=p[c[k]+q];ll:=l;rr:=r;
for u:=k+1 to i do begin
ii:=c[u];
if p[ii]>ll then ll:=p[ii];
if p[ii+q]<rr then rr:=p[ii+q];
if ll>rr then exit(false);
if p[ii+q]>r then r:=p[ii+q];
end;
j:=find(r);
while j>=l do begin
if color[j]=0 then color[j]:=a[c[i]]; f[j]:=l; j:=find(j-1);
end;
ok:=false;
for ii:=ll to rr do if color[ii]=a[c[i]] then begin ok:=true;break; end;
if not ok then exit(false);
k:=i+1;
end;
check:=true;
end;
begin
readln(n,q);
for i:=1 to q do begin
readln(x[i],x[i+q],a[i]);
c[i]:=i;c[i+q]:=i+q;
end;
sort1(1,q*2);
for i:=1 to q*2 do
p[c[i]]:=p[c[i-1]]+ord(x[i]<>x[i-1])*(ord(x[i]-x[i-1]>1)+1);
nn:=p[c[q*2]];
l:=1;r:=q;
while l<r do begin
mid:=(l+r+1) div 2;
if check(mid) then l:=mid
else r:=mid-1;
end;
if l=q then l:=0 else inc(l);
writeln(l);
close(input);
close(output);
end.

复制代码

		自动登录	找回密码
密码			立即注册