华师一附中OI组

标题: P2898 [USACO08JAN]haybale猜测Haybale Guessing [打印本页]
作者: admin    时间: 2018-9-3 18:06
标题: P2898 [USACO08JAN]haybale猜测Haybale Guessing
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
来一发pas的程序
  1. program syj; {erfen ans+range covering_using bingcha set}
  2. const
  3. maxn=25000+5;
  4. var n,q,nn,l,r,mid,i:longint;
  5.     x,c,p,f,color:array[0..maxn*4]of longint;
  6.     a:array[1..maxn]of longint;
  7. procedure sort1(l,r:longint);
  8. var i,j,k,z:longint;
  9. begin
  10. i:=l;j:=r;k:=x[(l+r) div 2];
  11. repeat
  12.   while x[i]<k do inc(i);
  13.   while x[j]>k do dec(j);
  14.   if i<=j then begin
  15.    z:=x[i];x[i]:=x[j];x[j]:=z;
  16.    z:=c[i];c[i]:=c[j];c[j]:=z;
  17.    inc(i);dec(j);
  18.   end;
  19. until i>j;
  20. if l<j then sort1(l,j);
  21. if i<r then sort1(i,r);
  22. end;
  23. procedure sort2(l,r:longint);
  24. var i,j,k,kk,z:longint;
  25. begin
  26. i:=l;j:=r;k:=a[c[(l+r) div 2]];kk:=p[c[(l+r) div 2]];
  27. repeat
  28.   while (a[c[i]]>k) or (a[c[i]]=k)and(p[c[i]]<kk) do inc(i);
  29.   while (a[c[j]]<k) or (a[c[j]]=k)and(p[c[j]]>kk) do dec(j);
  30.   if i<=j then begin
  31.    z:=c[i];c[i]:=c[j];c[j]:=z;
  32.    inc(i);dec(j);
  33.   end;
  34. until i>j;
  35. if l<j then sort2(l,j);
  36. if i<r then sort2(i,r);
  37. end;
  38. function find(x:longint):longint;
  39. begin
  40. if f[x]<>x then f[x]:=find(f[x]); find:=f[x];
  41. end;
  42. function check(kk:longint):boolean;
  43. var u,i,j,k,l,r,ii,ll,rr:longint;
  44.      ok:boolean;
  45. begin
  46. for i:=1 to kk do c[i]:=i;
  47. sort2(1,kk);
  48. for i:=1 to nn do begin f[i]:=i;color[i]:=0; end;
  49. k:=1;
  50. for i:=1 to kk do if (i=kk)or(a[c[i]]<>a[c[i+1]])  then begin
  51. l:=p[c[k]];r:=p[c[k]+q];ll:=l;rr:=r;
  52. for u:=k+1 to i do begin
  53.   ii:=c[u];
  54.   if p[ii]>ll then ll:=p[ii];
  55.   if p[ii+q]<rr then rr:=p[ii+q];
  56.   if ll>rr then exit(false);
  57.   if p[ii+q]>r then r:=p[ii+q];
  58. end;
  59. j:=find(r);
  60. while j>=l do begin
  61.   if color[j]=0 then color[j]:=a[c[i]]; f[j]:=l; j:=find(j-1);
  62. end;
  63. ok:=false;
  64. for ii:=ll to rr do if color[ii]=a[c[i]] then begin ok:=true;break;  end;
  65. if not ok then exit(false);
  66. k:=i+1;
  67. end;
  68. check:=true;
  69. end;
  70. begin
  71. readln(n,q);
  72. for i:=1 to q do begin
  73.   readln(x[i],x[i+q],a[i]);
  74.   c[i]:=i;c[i+q]:=i+q;
  75. end;
  76. sort1(1,q*2);
  77. for i:=1 to q*2 do
  78. p[c[i]]:=p[c[i-1]]+ord(x[i]<>x[i-1])*(ord(x[i]-x[i-1]>1)+1);
  79. nn:=p[c[q*2]];
  80. l:=1;r:=q;
  81. while l<r do begin
  82. mid:=(l+r+1) div 2;
  83. if check(mid) then l:=mid
  84.   else r:=mid-1;
  85. end;
  86. if l=q then l:=0 else inc(l);
  87. writeln(l);
  88. close(input);
  89. close(output);
  90. end.

复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2