{"id":430,"date":"2009-03-28T20:05:21","date_gmt":"2009-03-28T12:05:21","guid":{"rendered":"http:\/\/sinyalee.com\/blog\/?p=430"},"modified":"2009-03-28T20:05:21","modified_gmt":"2009-03-28T12:05:21","slug":"apio-2008-%e7%8f%a0%e9%93%be%e4%ba%a4%e6%8d%a2%e5%99%a8%ef%bc%88beads%ef%bc%89-%e8%a7%a3%e9%a2%98%e6%8a%a5%e5%91%8a","status":"publish","type":"post","link":"https:\/\/sinyalee.com\/blog\/?p=430","title":{"rendered":"APIO 2008 \u73e0\u94fe\u4ea4\u6362\u5668\uff08beads\uff09 \u89e3\u9898\u62a5\u544a"},"content":{"rendered":"

\u9898\u76ee\u4e0e\u6570\u636e\u79fb\u6b65APIO\u5b98\u65b9\u7f51\u7ad9\uff1ahttp:\/\/www.apio.olympiad.org\/<\/a> <\/p>\n

\u9996\u5148\u6211\u4eec\u5f02\u5e38\u5bb9\u6613\u5c31\u60f3\u5230\u53ef\u4ee5\u9884\u5904\u7406\u7684\u65f6\u5019\uff0c\u5bf9\u6bcf\u4e2a\u73e0\u5b50\u5217\u51fa\u4e00\u5f20\u8868\uff0c\u50a8\u5b58\u8fd9\u4e2a\u73e0\u5b50\u7ecf\u8fc7\u6bcf\u4e2a\u4ea4\u6362\u5668\u4e4b\u540e\u7684\u72b6\u6001\u3002\u7136\u540e\u6bcf\u6b21\u8be2\u95ee\uff0c\u5c31\u5bf9\u8fd9\u4e2a\u73e0\u5b50\u6240\u5728\u7684\u8868\u6765\u505a\u4e8c\u5206\u67e5\u627e\u3002 <\/p>\n

\u7136\u540e\u53d1\u73b0\u5982\u679c\u62ff\u4e00\u5f20N*M\uff08\u5c31\u662f300000*300000*2*4\/1024\/1024\/1024\u2248670.5 GB\uff09\u7684\u8868\uff0c\u4f30\u8ba1\u8981\u51e0\u5341\u5e74\u540e\u7684\u7535\u8111\u624d\u53ef\u4ee5\u5b9e\u73b0\uff0c\u8fd9\u9053\u9898\u7684\u5185\u5b58\u9650\u5236\u662f256MB, \u663e\u7136\u5f00\u4e0d\u51fa\u6765\u3002 <\/p>\n

\u4f46\u662f\u6211\u4eec\u53d1\u73b0\uff0c\u521a\u5f00\u59cb\u5c31N\u9879\uff0c\u6bcf\u4e2a\u4ea4\u6362\u5668\u53c8\u4ea7\u751f2\u4e2a\u72b6\u6001\uff0c\u6240\u4ee5\u72b6\u6001\u6570\u6700\u591a\u662fN+2M\u4e2a\u3002\u6240\u4ee5\u6211\u4eec\u53ef\u4ee5\u628a\u8fd9n\u5f20\u8868\u5934\u5c3e\u76f8\u63a5\u7ed9\u5f04\u6210\u4e00\u4e2aN+2M\u957f\u5ea6\u76841\u7ef4\u6570\u7ec4\u3002\u7136\u540e\u518d\u8bb0\u5f55\u6bcf\u5f20\u8868\u5728\u8fd9\u4e2a\u6570\u7ec4\u4e2d\u7684\u59cb\u672b\u4f4d\u7f6e\u3002 <\/p>\n

\u53ef\u4ee5\u9884\u5904\u7406\u7684\u65f6\u5019\uff0c\u7528now[i]\u5b58\u50a8\u8fd9\u4e00\u6761\u9053\u73b0\u5728\u662f\u7b2c\u51e0\u4e2a\u73e0\u5b50\u3002\u7136\u540e\u6ca1\u5904\u7406\u4e00\u4e2a\u4ea4\u6362\u5668\uff0c\u4fbf\u6dfb\u52a0\u5728\u8fd9\u4e2a\u4ea4\u6362\u5668\u4ea4\u6362\u76842\u4e2a\u73e0\u5b50\u7684\u8868\u4e0a\u6dfb\u52a0\u4e00\u9879\u3002\u6b64\u65f6\u7528\u94fe\u8868\u5b9e\u73b0\uff0c\u6240\u6709\u4ea4\u6362\u5668\u5904\u7406\u5b8c\uff0c\u518d\u628a\u94fe\u8868\u4e2d\u7684\u4fe1\u606f\u8f6c\u79fb\u5230\u4e8c\u5206\u67e5\u627e\u7528\u5230\u7684\u8868\u4e2d\u3002 <\/p>\n

\u7a0b\u5e8f\u5982\u4e0b\uff1a <\/p>\n

{
ID: sinya1
PROG: beads
LANG:PASCAL
} <\/p>\n

uses
  math,
  beadslib; <\/p>\n

const
  maxn=300000;
  maxm=300000;
  maxl=maxn+maxm+maxm; <\/p>\n

var
  n,m,i,j,k,h,q:longint;
  now:array[1..maxn]of longint;
  pos1,swp1,next:array[1..maxl]of longint;
  tail:array[1..maxn]of longint;
  pos,swp:array[1..maxl]of longint;
  be:array[0..maxn]of longint; <\/p>\n

procedure swap(var x,y:longint);var z:longint;begin
  z:=x;x:=y;y:=z;
end; <\/p>\n

procedure add(const x,p:longint);begin
  inc(h);
  pos1[h]:=p;swp1[h]:=i;next[h]:=-1;
  next[tail[x]]:=h;
  tail[x]:=h;
end; <\/p>\n

procedure init;begin
  assign(input,’beads.in’);reset(input); <\/p>\n

  readln(n,m); <\/p>\n

  for i:=1 to n do now[i]:=i;
  h:=n;
  for i:=1 to n do begin
    swp1[i]:=0;pos1[i]:=i;next[i]:=-1;
    tail[i]:=i;
  end; <\/p>\n

  for i:=1 to m do begin
    readln(j);
    add(now[j],j+1);
    add(now[j+1],j);
    swap(now[j],now[j+1]);
  end; <\/p>\n

  be[0]:=1;
  for i:=1 to n do begin
    be[i]:=be[i-1];
    j:=i;
    while j>=0 do begin
      pos[be[i]]:=pos1[j];
      swp[be[i]]:=swp1[j];
      inc(be[i]);
      j:=next[j];
    end;
  end; <\/p>\n

  close(input);
end; <\/p>\n

function search(const k,j:longint):longint;var l,r,m:longint;begin
  l:=be[k-1];r:=be[k];
  while r-l>1 do begin
    m:=(r+l)shr 1;
    if swp[m]<=j then l:=m
    else r:=m;
  end;
  exit(pos[l]);
end; <\/p>\n

procedure work;begin
  q:=getNumQuestions();
  while q>0 do begin
    getQuestion(k,j);
    answer(search(k,j));
    dec(q);
  end;
end; <\/p>\n

begin
  init;
  work;
end. <\/p>\n

\u5173\u4e8e\u4e92\u4ea4\u5f0f<\/h4>\n

\uff08\u8bf7\u628a\u6240\u6709\u201c\u4e92\u4ea4\u201d\u8bf7\u81ea\u5df1\u4ee3\u6362\u6210\u201c\u4ea4\u4e92\u201d\uff09 <\/p>\n

\u8fd9\u662f\u6211\u7b2c\u4e00\u6b21\u5199\u4e92\u4ea4\u5f0f\u7684\u7a0b\u5e8f\u3002\u59da\u8001\u5e08\u8ddf\u6211\u8bf4\u4e92\u4ea4\u5f0f\u7684\u95ee\u9898\u8ddf\u4e00\u822c\u7684\u95ee\u9898\u6ca1\u6709\u533a\u522b\uff0c\u53ef\u662f\u5b9e\u9645\u4e0a\u8fd8\u662f\u6709\u5f88\u5927\u7684\u533a\u522b\u7684\u3002\u56e0\u4e3a\u4e92\u4ea4\u5f0f\uff0c\u5c31\u662f\u8981\u8981\u6c42\u6211\u4eec\u7528\u5728\u7ebf\u7b97\u6cd5\uff0c\u5728\u6bcf\u6b21\u8be2\u95ee\u90fd\u5fc5\u987b\u7acb\u5373\u56de\u7b54\u3002\u4e0d\u53ef\u4ee5\u50cf\u4e00\u822c\u7684\u95ee\u9898\u4e00\u6837\uff0c\u628a\u95ee\u9898\u6392\u5e8f\u540e\u6216\u8005\u600e\u4e48\u6837\u624d\u6765\u505a\u3002 <\/p>\n

\u5b9e\u9645\u4e0a\u90a3\u4e2a\u6807\u51c6\u4e92\u4ea4\u5e93\u4e5f\u662f\u8fd9\u4e48\u5199\u7684\uff0c\u4ed6\u628a\u90a3\u4e2a\u95ee\u9898\u6587\u4ef6\u505aquestions-9545431.txt\uff0c\u540e\u9762\u90a3\u4e00\u4e32\u5bc6\u7801\u7684\u5b58\u5728\uff0c\u5c31\u662f\u8981\u9632\u6b62\u6211\u4eec\u7684\u7a0b\u5e8f\u76f4\u63a5\u8bbf\u95ee\u95ee\u9898\u6587\u4ef6\u3002\u7136\u540e\u90a3\u4e2atxt\u91cc\u9762\u8fd8\u6709\u52a0\u5bc6\uff0c\u8981\u7528\u4e09\u4e2amagic number\u89e3\u5bc6\u624d\u53ef\u4ee5\u77e5\u9053\u91cc\u9762\u5199\u4ec0\u4e48\uff0c\u8fd9\u4e9b\u90fd\u662f\u4e3a\u4e86\u9632\u6b62\u6211\u4eec\u5077\u770b\u95ee\u9898\u5217\u8868\u3002 <\/p>\n

\u81f3\u4e8ecena\u5305\uff0c\u5176\u5b9e\u53ea\u8981\u6539\u5199\u4e00\u4e0b\u90a3\u4e2a\u5e93\u6587\u4ef6\uff0c\u8ba9\u4ed6\u628a\u7ed3\u679c\u8f93\u51fa\u5230\u4e00\u4e2a\u6587\u4ef6\u4e2d\u5c31\u53ef\u4ee5\u4e86\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u9898\u76ee\u4e0e\u6570\u636e\u79fb\u6b65APIO\u5b98\u65b9\u7f51\u7ad9\uff1ahttp:\/\/www.apio.olympiad.org\/ \u9996\u5148\u6211\u4eec\u5f02\u5e38\u5bb9\u6613\u5c31 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[23,131,344],"class_list":["post-430","post","type-post","status-publish","format-standard","hentry","category-13","tag-apio","tag-131","tag-344"],"_links":{"self":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/430","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=430"}],"version-history":[{"count":0,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/430\/revisions"}],"wp:attachment":[{"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=430"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=430"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sinyalee.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=430"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}