2821: 作诗(Poetize)

Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 1078 Solved: 348
[Submit][Status]

Description

神犇SJY虐完HEOI之后给傻×LYD出了一题：
SHY是T国的公主，平时的一大爱好是作诗。
由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。
LYD这种傻×当然不会了，于是向你请教……
问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。

Input

输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。

Output

输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
0
0
0
1

HINT

对于100%的数据，1<=n,c,m<=10^5

Source

By lydrainbowcat

挖个坑，以后来填。。。

本来用这题来练分块的，结果完全被二分坑到了QAQ。。。TLE...哪天有空A了这题

我的代码：

1.二分自己yy的

 {$inline on}

 const maxn=+;

 type node=record

      p,v:longint;

      end;

 var b:array[..maxn] of node;

     a,belong,v,head,tail:array[..maxn] of longint;

     mark:array[..maxn] of boolean;

     f:array[..,..] of longint;

     l,r:array[..] of longint;

     i,j,n,m,tot,ans,ll,rr,block,cnt,x:longint;

 function max(x,y:longint):longint;inline;

  begin

  if x>y then exit(x) else exit(y);

  end;

 procedure swap(var x,y:longint);inline;

  var t:longint;

  begin

  t:=x;x:=y;y:=t;

  end;

 function cmp(x,y:node):boolean;inline;

  begin

   if x.v=y.v then exit(x.p<y.p) else exit(x.v<y.v);

  end;

 procedure sort(l,r:longint);inline;

  var i,j:longint;x,y:node;

  begin

    i:=l;j:=r;x:=b[(i+j)>>];

    repeat

      while cmp(b[i],x) do inc(i);

      while cmp(x,b[j]) do dec(j);

      if i<=j then

       begin

         y:=b[i];b[i]:=b[j];b[j]:=y;

         inc(i);dec(j);

       end;

    until i>j;

    if i<r then sort(i,r);

    if j>l then sort(l,j);

  end;

 procedure init;

  begin

    readln(n,m,m);

    for i:= to n do

     begin

       read(a[i]);

       b[i].p:=i;b[i].v:=a[i];

     end;

    readln;

    sort(,n);

    block:=trunc(sqrt(n)*ln(n)/ln());

    cnt:=(n-) div block+;

    for i:= to n do belong[i]:=(i-) div block+;

    for i:= to cnt do

     begin

       l[i]:=(i-)*block+;r[i]:=i*block;

     end;

    r[cnt]:=n;

    for i:= to n do

     begin

      x:=b[i].v;

      if head[x]= then head[x]:=i;

      tail[x]:=i;

     end;

  end;

 procedure prepare;

  begin

   for i:= to cnt do

    begin

      fillchar(v,sizeof(v),);

      tot:=;

      for j:=l[i] to r[cnt] do

       begin

        inc(v[a[j]]);

        if (v[a[j]] and =) and (v[a[j]]<>) then dec(tot)

        else if v[a[j]] and = then inc(tot);

        f[i,belong[j]]:=tot;

       end;

    end;

  end;

 function findup(z,x:longint):longint;inline;

  var l,r,mid:longint;

  begin

   if x>=b[tail[z]].p then exit(tail[z]);

   l:=head[z];r:=tail[z];

   while l<r do

    begin

     mid:=(l+r)>>;

     if b[mid].p<x then l:=mid+

     else if b[mid].p>x then r:=mid

     else exit(mid);

    end;

   exit(l-);

  end;

 function finddown(z,x:longint):longint;inline;

  var l,r,mid:longint;

  begin

   l:=head[z];r:=tail[z];

   while l<r do

    begin

     mid:=(l+r)>>;

     if b[mid].p<x then l:=mid+

     else if b[mid].p>x then r:=mid

     else exit(mid);

    end;

   exit(l);

  end;

 function find(z,x,y:longint):longint;inline;

  begin

   find:=max(findup(z,y)-finddown(z,x)+,);

  end;

 procedure query(x,y:longint);inline;

  var i,bx,by,t1,t2,z:longint;

  begin

  ans:=;

  bx:=belong[x];by:=belong[y];

  if by-bx<= then

    begin

      fillchar(v,sizeof(v),);

      for i:=x to y do

       begin

        inc(v[a[i]]);

        if (v[a[i]] and =) and (v[a[i]]<>) then dec(ans)

        else if v[a[i]] and = then inc(ans);

       end;

    end

  else

    begin

      fillchar(mark,sizeof(mark),false);

      ans:=f[bx+,by-];

      for i:=x to r[bx] do

       begin

        z:=a[i];if mark[z] then continue;mark[z]:=true;

        t1:=find(z,x,y);t2:=find(z,l[bx+],r[by-]);

        if (t1 and =) and (t2 and =) and (t2<>) then dec(ans)

        else if (t1 and =) and ((t2 and =) or (t2=)) then inc(ans);

       end;

      for i:=l[by] to y do

       begin

        z:=a[i];if mark[z] then continue;mark[z]:=true;

        t1:=find(z,x,y);t2:=find(z,l[bx+],r[by-]);

        if (t1 and =) and (t2 and =) and (t2<>) then dec(ans)

        else if (t1 and =) and ((t2 and =) or (t2=)) then inc(ans);

       end;

    end;

  end;

 procedure main;

  begin

    ans:=;

    for i:= to m do

     begin

       readln(ll,rr);

       ll:=(ll+ans) mod n+;rr:=(rr+ans) mod n+;

       if ll>rr then swap(ll,rr);

       query(ll,rr);

       writeln(ans);

     end;

  end;

 begin

   assign(input,'input.txt');assign(output,'output.txt');

   reset(input);rewrite(output);

   init;

   prepare;

   main;

   close(input);close(output);

 end.

2.二分摘抄自hzwer

 {$inline on}

 const maxn=+;

 type node=record

      p,v:longint;

      end;

 var b:array[..maxn] of node;

     a,belong,v,head,tail:array[..maxn] of longint;

     mark:array[..maxn] of boolean;

     f:array[..,..] of longint;

     l,r:array[..] of longint;

     i,j,n,m,tot,ans,ll,rr,block,cnt,x:longint;

 function max(x,y:longint):longint;inline;

  begin

  if x>y then exit(x) else exit(y);

  end;

 procedure swap(var x,y:longint);inline;

  var t:longint;

  begin

  t:=x;x:=y;y:=t;

  end;

 function cmp(x,y:node):boolean;inline;

  begin

   if x.v=y.v then exit(x.p<y.p) else exit(x.v<y.v);

  end;

 procedure sort(l,r:longint);inline;

  var i,j:longint;x,y:node;

  begin

    i:=l;j:=r;x:=b[(i+j)>>];

    repeat

      while cmp(b[i],x) do inc(i);

      while cmp(x,b[j]) do dec(j);

      if i<=j then

       begin

         y:=b[i];b[i]:=b[j];b[j]:=y;

         inc(i);dec(j);

       end;

    until i>j;

    if i<r then sort(i,r);

    if j>l then sort(l,j);

  end;

 procedure init;

  begin

    readln(n,m,m);

    for i:= to n do

     begin

       read(a[i]);

       b[i].p:=i;b[i].v:=a[i];

     end;

    readln;

    sort(,n);

    block:=trunc(sqrt(n)*ln(n)/ln());

    cnt:=(n-) div block+;

    for i:= to n do belong[i]:=(i-) div block+;

    for i:= to cnt do

     begin

       l[i]:=(i-)*block+;r[i]:=i*block;

     end;

    r[cnt]:=n;

    for i:= to n do

     begin

      x:=b[i].v;

      if head[x]= then head[x]:=i;

      tail[x]:=i;

     end;

  end;

 procedure prepare;

  begin

   for i:= to cnt do

    begin

      fillchar(v,sizeof(v),);

      tot:=;

      for j:=l[i] to r[cnt] do

       begin

        inc(v[a[j]]);

        if (v[a[j]] and =) and (v[a[j]]<>) then dec(tot)

        else if v[a[j]] and = then inc(tot);

        f[i,belong[j]]:=tot;

       end;

    end;

  end;

 function findup(z,x:longint):longint;inline;

  var l,r,mid,tmp:longint;

  begin

   l:=head[z];r:=tail[z];tmp:=;

   while l<=r do

    begin

     mid:=(l+r)>>;

     if b[mid].p>x then l:=mid+

     else begin tmp:=mid;r:=mid-;end;

    end;

   exit(tmp);

  end;

 function finddown(z,x:longint):longint;inline;

  var l,r,mid,tmp:longint;

  begin

   l:=head[z];r:=tail[z];tmp:=maxlongint;

   while l<=r do

    begin

     mid:=(l+r)>>;

     if b[mid].p<x then l:=mid+

     else begin tmp:=mid;r:=mid-;end;

    end;

   exit(tmp);

  end;

 function find(z,x,y:longint):longint;inline;

  begin

   find:=max(findup(z,y)-finddown(z,x)+,);

  end;

 procedure query(x,y:longint);inline;

  var i,bx,by,t1,t2,z:longint;

  begin

  ans:=;

  bx:=belong[x];by:=belong[y];

  if by-bx<= then

    begin

      fillchar(v,sizeof(v),);

      for i:=x to y do

       begin

        inc(v[a[i]]);

        if (v[a[i]] and =) and (v[a[i]]<>) then dec(ans)

        else if v[a[i]] and = then inc(ans);

       end;

    end

  else

    begin

      fillchar(mark,sizeof(mark),false);

      ans:=f[bx+,by-];

      for i:=x to r[bx] do

       begin

        z:=a[i];if mark[z] then continue;mark[z]:=true;

        t1:=find(z,x,y);t2:=find(z,l[bx+],r[by-]);

        if (t1 and =) and (t2 and =) and (t2<>) then dec(ans)

        else if (t1 and =) and ((t2 and =) or (t2=)) then inc(ans);

       end;

      for i:=l[by] to y do

       begin

        z:=a[i];if mark[z] then continue;mark[z]:=true;

        t1:=find(z,x,y);t2:=find(z,l[bx+],r[by-]);

        if (t1 and =) and (t2 and =) and (t2<>) then dec(ans)

        else if (t1 and =) and ((t2 and =) or (t2=)) then inc(ans);

       end;

    end;

  end;

 procedure main;

  begin

    ans:=;

    for i:= to m do

     begin

       readln(ll,rr);

       ll:=(ll+ans) mod n+;rr:=(rr+ans) mod n+;

       if ll>rr then swap(ll,rr);

       query(ll,rr);

       writeln(ans);

     end;

  end;

 begin

   assign(input,'input.txt');assign(output,'output.txt');

   reset(input);rewrite(output);

   init;

   prepare;

   main;

   close(input);close(output);

 end.

巴特西

2821: 作诗(Poetize)