将此神题作为博客园的第一篇文章，至此，数据结构基本学完了（或者说数据结构轮流虐了我一次！）

 

人生第一道7K代码题！

 

没什么，就是treap套个trie，然后tle是因为一定要用指针当时p党谁会用那么丑的指针，所以作罢。然后光荣tle（用自己的数据和云神的对拍是没有错的），然后竟然是第一个尝试写此题的p党！

 

好吧。oi路也算是步入正轨（虽然一开始就必须走在翻盘的路上……noip就不想说了……），那么接下来就重新回归基础，把图论那些东西重新搞好♂搞深♂入♂……

 

然后来看看3217第一个死掉的p党的代码吧（语言歧视题！）

好多个第一！

const  maxd=31;  maxn1=30233333;  maxn2=322333;  number=233333;  mm=1048576; var  son:array[0..maxn1,0..1]of longint;  sum,pp:array[0..maxn1]of longint;  size,root,left,right,p1,p2,value,fi,se,key:array[0..maxn2]of longint;  tot,tot1,tot2,sum1,sum2,n,m,sroot,big1,big2:longint; function new1:longint;begin  inc(tot);  exit(tot);end; function new2:longint;var  i:longint;begin  if sum1>0 then begin    i:=pp[sum1];    dec(sum1);    sum[i]:=0;    son[i][0]:=0;    son[i][1]:=0;    exit(i);  end;  inc(sum2);  exit(sum2);end; procedure clear(x:longint);begin  if x=0 then exit;  inc(sum1);  pp[sum1]:=x;  clear(son[x][0]);  clear(son[x][1]);end; function max(x,y:longint):longint;begin  if x
     
      >i and 1;    if sum[son[x][j xor 1]]>0 then begin      inc(ans,1<
      
       >i and 1;    if son[t][j]=0 then son[t][j]:=new2;    t:=son[t][j];  end;end; procedure del(var x:longint;h,y:longint);begin  dec(sum[x]);  if sum[x]=0 then begin    clear(x);    x:=0;    exit;  end;  if h=-1 then exit;  del(son[x][y>>h and 1],h-1,y);end; procedure calc(var x,y:longint;z:longint);begin  if z>y then begin    if z>x then begin      y:=x;      x:=z;    end    else y:=z;  end;end; procedure merge(var x:longint;ll,rr:longint);begin  x:=new2;  sum[x]:=sum[ll]+sum[rr];  if sum[son[ll][0]]+sum[son[rr][0]]>0 then merge(son[x][0],son[ll][0],son[rr][0]);  if sum[son[ll][1]]+sum[son[rr][1]]>0 then merge(son[x][1],son[ll][1],son[rr][1]);end; procedure up(x:longint);begin  if x=0 then exit;  fi[x]:=fi[left[x]];  se[x]:=se[left[x]];  calc(fi[x],se[x],value[x]);  calc(fi[x],se[x],fi[right[x]]);  calc(fi[x],se[x],se[right[x]]);  size[x]:=size[left[x]]+size[right[x]]+1;end; procedure update(x:longint);begin  merge(root[x],root[left[x]],root[right[x]]);  add(root[x],value[x]);  up(x);end; procedure lt(var x:longint);var  k:longint;begin  k:=right[x];  right[x]:=left[k];  left[k]:=x;  size[k]:=size[x];  fi[k]:=fi[x];  se[k]:=se[x];  clear(root[k]);  root[k]:=root[x];  update(x);  x:=k;end; procedure rt(var x:longint);var  k:longint;begin  k:=left[x];  left[x]:=right[k];  right[k]:=x;  size[k]:=size[x];  fi[k]:=fi[x];  se[k]:=se[x];  clear(root[k]);  root[k]:=root[x];  update(x);  x:=k;end; procedure insert(var x:longint;y,z:longint);begin  if x=0 then begin    x:=new1;    value[x]:=z;    key[x]:=random(number);    left[x]:=0;    right[x]:=0;    add(root[x],z);    fi[x]:=z;    se[x]:=0;    size[x]:=1;    exit;  end;  if y<=size[left[x]]+1 then begin    insert(left[x],y,z);    if key[left[x]]>key[x] then rt(x);  end  else begin    insert(right[x],y-size[left[x]]-1,z);    if key[right[x]]>key[x] then lt(x);  end;  add(root[x],z);  inc(size[x]);  calc(fi[x],se[x],z);end; function change(x,y,new:longint):longint;var  old:longint;begin  if y=size[left[x]]+1 then begin    old:=value[x];    del(root[x],maxd,old);    add(root[x],new);    value[x]:=new;    up(x);    exit(old);  end;  if y<=size[left[x]] then old:=change(left[x],y,new)    else old:=change(right[x],y-size[left[x]]-1,new);  del(root[x],maxd,old);  add(root[x],new);  up(x);  exit(old);end; function find(x,y:longint):longint;begin  if y=size[left[x]]+1 then exit(value[x]);  if y<=size[left[x]] then exit(find(left[x],y))    else exit(find(right[x],y-size[left[x]]-1));end; function delete(var x:longint;y:longint):longint;var  old:longint;begin  if y=size[left[x]]+1 then begin    old:=value[x];    if left[x]=0 then x:=right[x]    else    if right[x]=0 then x:=left[x]    else begin      if key[left[x]]>key[right[x]] then begin        rt(x);        delete(right[x],y-size[left[x]]-1);      end      else begin        lt(x);        delete(left[x],y);      end;      del(root[x],maxd,old);    end;    up(x);    exit(old);  end;  if y<=size[left[x]] then old:=delete(left[x],y)    else old:=delete(right[x],y-size[left[x]]-1);  del(root[x],maxd,old);  up(x);  exit(old);end;  procedure before(x,l,r:longint);var  lsum:longint;begin  if x=0 then exit;  lsum:=size[left[x]]+1;  if r
       
        lsum then before(right[x],l-lsum,r-lsum)        else          if (l=1) and (r=size[x]) then begin            inc(tot1);            p1[tot1]:=x;            calc(big1,big2,fi[x]);            calc(big1,big2,se[x]);          end          else begin            inc(tot2);            p2[tot2]:=value[x];            calc(big1,big2,value[x]);            if l
        
         lsum then before(right[x],1,r-lsum);          end;end; function query(l,r:longint):longint;var  ll,rr,mid,ans,i:longint;begin  tot1:=0;  tot2:=0;  big1:=0;  big2:=0;  before(sroot,l,r);  ans:=0;  //writeln(big2);  if big2=0 then exit(0);  for i:=1 to tot1 do p1[i]:=root[p1[i]];  for i:=1 to tot1 do ans:=max(ans,ask(p1[i],big2));  for i:=1 to tot2 do ans:=max(ans,p2[i] xor big2);  exit(ans);end; procedure into;var  i,j:longint;begin  //randomize;  readln(n,m);  tot:=0;  sroot:=0;  for i:=1 to n do begin    read(j);    insert(sroot,i,j);  end;end; procedure work;var  last,x,y:longint;  ch:char;begin  last:=0;  readln;  while m>0 do begin    dec(m);    read(ch);    case ch of      'I':begin            readln(x,y);            //x:=x mod n+1;            x:=(x+last mod n) mod n+1;            y:=(y+last mod mm) mod mm;            //writeln(x,' ',y);            insert(sroot,x,y);            inc(n);      end;      'C':begin            readln(x,y);            //x:=x mod n+1;            x:=(x+last mod n) mod n+1;            y:=(y+last mod mm) mod mm;            //writeln(x,' ',y);            change(sroot,x,y);      end;      'D':begin            readln(x);            //x:=x mod n+1;            x:=(x+last mod n) mod n+1;            //writeln(x);            delete(sroot,x);            dec(n);      end;      'F':begin            readln(x,y);            //x:=x mod n+1;            //y:=y mod n+1;            x:=(x+last mod n) mod n+1;            y:=(y+last mod n) mod n+1;            if x>y then swap(x,y);            //writeln(x,' ',y);            last:=query(x,y);            writeln(last);      end;    end;  end;end; begin  into;  work;end.
        
       
      
     

 14.12.13……竟然没发现云神比较神奇的build操作（之前还以为慢了呢！）

procedure build(var x:longint;ll,rr:longint);var  mid,i:longint;begin  mid:=(ll+rr)>>1;  x:=mid;  value[x]:=num[mid];  key[x]:=random(number);  left[x]:=0;  right[x]:=0;  if ll
     
      key[x] then swap(key[left[x]],key[x]);  end;  if rr>mid then begin    build(right[x],mid+1,rr);    if key[right[x]]>key[x] then swap(key[right[x]],key[x]);  end;  update(x)end;
     

结果还是tle……（搞到数据了……云14s蒟蒻18s……）