fork download
copy 
  1. const fi='dquery.inp';
  2.       fo='dquery.out';
  3.         maxn=30000;
  4. type manglon=array[0..1000000]of longint;
  5.     mangdulieu=array[0..230000]of longint;
  6.     mangit=array[0..300000]of longint;
  7. var pos:manglon;
  8.     a,cs,cstv,loai,res:mangdulieu;
  9.     it:mangit;
  10.  
  11.     nn,q,n:longint;
  12. procedure mo;
  13.     begin
  14.         assign(input,fi);reseT(input);
  15.         assign(output,fo);rewrite(output);
  16.     end;
  17. procedure dong;
  18.     begin
  19.         closE(input);close(output);
  20.     end;
  21. procedure swap(Var i,j:longint);
  22.     var t:longint;
  23.         begin
  24.             t:=i;
  25.             i:=j;
  26.             j:=t;
  27.         end;
  28. procedure qs(l,r:longint);
  29.     var i,j,m,x,y:longint;
  30.         begin
  31.             i:=l;
  32.             j:=r;
  33.             m:=random(r-l)+1+l;
  34.             x:=cs[i];
  35.             y:=loai[i];
  36.             repeat
  37.                 while (cs[i]<x) or ((cs[i]=x) and (loai[i]<y)) do inc(I);
  38.                 while (x<cs[j]) or ((x=cs[j]) and (y<loai[j])) do dec(j);
  39.                 if i<=j then
  40.                     begin
  41.                         swap(cs[i],cs[j]);
  42.                         swap(loai[i],loai[j]);
  43.                         swap(a[i],a[j]);
  44.                         swap(cstv[i],cstv[j]);
  45.                         inc(i);dec(j);
  46.                     end;
  47.             until i>j;
  48.             if i<r then qs(i,r);
  49.             if l<j then qs(l,j);
  50.         end;
  51. procedure nhap;
  52. var i:longint;
  53.     begin
  54.         readln(n);
  55.         for i:=1 to n do read(a[i]);
  56.         for i:=1 to n do
  57.             begin
  58.                 cs[i]:=i;loai[i]:=1;
  59.             end;
  60.         readln(Q);
  61.         for i:=n+1 to n+q do
  62.             begin
  63.                 read(a[i],cs[i]);
  64.                 loai[i]:=2;
  65.             end;
  66.         nn:=n;
  67.         n:=n+q;
  68.         for i:=1 to n do cstv[i]:=i;
  69.         qs(1,n);
  70.     end;
  71. procedure update(u,w,l,r,i:longint);
  72.     var mid:longint;
  73.         begin
  74.             if (u=l) and (l=r) then
  75.                 begin
  76.                     it[i]:=w;
  77.                     exit;
  78.                 end;
  79.             if (r<u) or (u<l) then exit;
  80.             mid:=(l+r) div 2;
  81.             update(u,w,l,mid,i*2);
  82.             update(u,w,mid+1,r,i*2+1);
  83.             it[i]:=it[i*2]+it[i*2+1];
  84.         end;
  85. function find(u,v,l,r,i:longint):longint;
  86.     var mid:longint;
  87.         begin
  88.             if (r<u) or (v<l) then exit(0);
  89.             if (u<=l) and (r<=v) then exit(it[i]);
  90.             mid:=(l+r) div 2;
  91.             exit(find(u,v,l,mid,i*2)+find(u,v,mid+1,r,i*2+1));
  92.         end;
  93. procedure xuli;
  94.     var i:longint;
  95.         begin
  96.             for i:=1 to n do
  97.                 if loai[i]=1 then
  98.                     begin
  99.                         if pos[a[i]]=0 then
  100.                             begin
  101.                                 update(cs[i],1,1,maxn,1);
  102.                                 pos[a[i]]:=cs[i];
  103.                             end
  104.                         else
  105.                             begin
  106.                                 update(pos[a[i]],0,1,maxn,1);
  107.                                 pos[a[i]]:=cs[i];
  108.                                 update(cs[i],1,1,maxn,1);
  109.                             end;
  110.                     end
  111.                 else
  112.                     begin
  113.                         res[cstv[i]]:=find(a[i],cs[i],1,maxn,1);
  114.                     end;
  115.                 for i:=nn+1 to n do writeln(res[i]);
  116.         end;
  117. begin
  118.    // mo;
  119.     nhap;
  120.     xuli;
  121.    // dong;
  122. end.
  123.  
  124.  
Success #stdin #stdout 0s 9856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yiJZuN
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!