0_0_21719184_24141\Main.java:1: ´íÎó: ÕÒ²»µ½·ûºÅ
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.lang.reflect.Array;import java.util.Comparator;import java.util.Random;import java.util.StringTokenizer;class BITSinglePoint{private int N;private final int size;private final int[]nodes;public BITSinglePoint(int size){N=size;this.size=size;nodes=new int[size+1];nodes[0]=0;}private static int lower_bit(int x){return x&-x;}public void init(int val){for(int i=1;i<=N;++i)nodes[i]=val*lower_bit(i);}public void init(int val,int N){assert 0<N&&N<size:"Out of bound of array";this.N=N;init(val);}public void init(int[]A){for(int i=1;i<=N;++i)nodes[i]=sum(i-1)+A[i];}public void init(int[]A,int N){assert 0<N&&N<size:"Out of bound of array";this.N=N;init(A);}public void initWithPrefixSum(int[]PS){for(int i=1;i<=N;++i)nodes[i]=PS[i]-PS[i-lower_bit(i)];}public void initWithPrefixSum(int[]PS,int N){assert 0<N&&N<size:"Out of bound of array";this.N=N;initWithPrefixSum(PS);}public int sum(int x){int ret=0;for(;x>0;x^=lower_bit(x))ret+=nodes[x];return ret;}public int sum(int lft,int rht){if(lft>rht)return 0;return sum(rht)-sum(lft-1);}public void add(int x,int v){if(x<=0)return;for(;x<=N;x+=lower_bit(x))nodes[x]+=v;}public void set(int x,int v){if(x<=0)return;int delta=v-nodes[x];add(x,delta);}}class JosephCircle{private static int min(int x,int y){return x<y?x:y;}private final int size;private final BITSinglePoint bit;private int start;private int step;private int N;public JosephCircle(int size){this.size=size;bit=new BITSinglePoint(size);this.N=size;}public void init(int start,int N){assert 1<=start&&start<=size:"Out of bound of array";this.N=N;this.start=start;bit.init(1,N);}public void init(int start,int N,int step){this.step=step;init(start,N);}public int next(int step){int target=-1;while(step>0){target=min(start+step-1,N);step-=bit.sum(start,target);if(step<=0)break;start=target%N+1;}bit.add(target,-1);return target;}public int next(){return next(step);}}class RandomShuffle{protected final Random random=new Random();protected final JosephCircle jc;protected final int[]assist_array;public RandomShuffle(int size){jc=new JosephCircle(size);assist_array=new int[size+1];}protected void init(int start,int N){jc.init(start,N);}protected void init(int N){jc.init(1,N);}public void shuffle(int[]targets,int offset,int length){assert offset>=0&&offset<targets.length&&offset+length<targets.length:"Out of bound of array";init(length);System.arraycopy(targets,offset,assist_array,1,length);for(int size=length,i=offset;size>0;--size,++i){int step=random.nextInt(size)+1;int next=jc.next(step);targets[i]=assist_array[next];}}public static void main(String[]args){final int size=20;final int[]A=new int[size+1];final RandomShuffle rs=new RandomShuffle(size);int offset=2,N=15;for(int i=0;i<N;++i)A[i+offset]=i;rs.init(N);rs.shuffle(A,offset,N);for(int i=0;i<N;++i)System.out.print(A[i+offset]+" ");System.out.println();}}interface RankTreeMethods<T,Node>{T kth(int k);int rank(T x);}abstract class BSTBase<T,Node extends BSTNode<T>>implements BSTMethods<T,Node>{@Override public void forEachNode(NodeHandler<Node>handler){this.nodeHandler=handler;forEachWithNode(root,0,1);this.nodeHandler=null;}@Override public void forEachElement(ElementHandler<T>handler){this.elementHandler=handler;forEachWithElement(root,0,1);this.elementHandler=null;}@Override public void clear(){size=0;factory.clear();factory.initRoot(root);}@Override public Node search(T x){return search(root,0,x);}@Override public int toArray(T[]targets){assert targets.length>=size:"Out of bound of array.";return toArray(root,0,targets,0);}@Override public T[]toArray(Class<T>classType){T[]targets=(T[])Array.newInstance(classType,size);toArray(root,0,targets,0);return targets;}@Override public Node lower_bound(T x){return lower_bound(root,0,x);}@Override public Node upper_bound(T x){return upper_bound(root,0,x);}@Override public Node begin(){Node target=(Node)root.son[0];if(target==null)return null;return(Node)target.min();}@Override public Node end(){return root;}public void extend(BSTBase<T,Node>target){target.forEachElement((ElementHandler)(idx,o)->insert((T)o));}protected final Comparator<T>comparator;protected final Maintainer<Node>maintainer;protected final NodeFactory<T,Node>factory;protected NodeHandler<Node>nodeHandler;protected ElementHandler<T>elementHandler;protected final Node root;protected int size;public BSTBase(Comparator<T>comparator,Maintainer<Node>maintainer,NodeFactory<T,Node>factory){this.maintainer=maintainer;this.comparator=comparator;this.factory=factory;this.root=factory.newRoot();this.size=0;}protected void link(Node father,Node son,int d){father.son[d]=son;if(son!=null)son.father=father;}protected void maintain(Node o){maintainer.maintain(o);}protected void rotate(Node o,int d){assert d==0||d==1;Node father=(Node)o.father;Node son=(Node)o.son[d^1];int d2=o.getSonIndex();link(o,(Node)son.son[d],d^1);link(son,o,d);link(father,son,d2);maintain(o);maintain(son);}protected Node search(Node father,int d,T x){Node o=(Node)father.son[d];if(o==null)return null;int delta=comparator.compare(x,o.value);if(delta==0)return o;d=delta<0?0:1;return search(o,d,x);}protected Node lower_bound(Node father,int d,T x){Node o=(Node)father.son[d];if(o==null)return null;int delta=comparator.compare(x,o.value);d=delta>=0?0:1;Node ans=lower_bound(o,d,x);if(d==0&&ans==null)ans=o;return ans;}protected Node upper_bound(Node father,int d,T x){Node o=(Node)father.son[d];if(o==null)return null;int delta=comparator.compare(x,o.value);d=delta>0?0:1;Node ans=upper_bound(o,d,x);if(d==0&&ans==null)ans=o;return ans;}protected int forEachWithNode(Node father,int d,int idx){Node o=(Node)father.son[d];if(o==null)return idx;idx=forEachWithNode(o,0,idx);nodeHandler.handle(idx,o);return forEachWithNode(o,1,idx+1);}protected int forEachWithElement(Node father,int d,int idx){Node o=(Node)father.son[d];if(o==null)return idx;idx=forEachWithElement(o,0,idx);elementHandler.handle(idx,o.value);return forEachWithElement(o,1,idx+1);}protected int toArray(Node father,int d,T[]targets,int idx){Node o=(Node)father.son[d];if(o==null)return idx;idx=toArray(o,0,targets,idx);targets[idx++]=o.value;idx=toArray(o,1,targets,idx);return idx;}}class BSTNode<T>{public T value;public BSTNode<T>father;public BSTNode<T>[]son=new BSTNode[2];public int getSonIndex(){return father.son[0]==this?0:1;}public BSTNode<T>min(){BSTNode<T>ret=this;while(ret.son[0]!=null)ret=ret.son[0];return ret;}public BSTNode<T>max(){BSTNode<T>ret=this;while(ret.son[1]!=null)ret=ret.son[1];return ret;}public BSTNode<T>next(){if(son[1]!=null)return son[1].min();BSTNode<T>o=this;BSTNode<T>father=o.father;while(father!=null&&father.son[1]==o){o=father;father=o.father;}return father;}public BSTNode<T>prev(){if(son[0]!=null)return son[0].max();BSTNode<T>o=this;BSTNode<T>father=o.father;while(father!=null&&father.son[0]==o){o=father;father=o.father;}return father;}}class Treap<T,Node extends Treap.TreapNode<T>>extends BSTBase<T,Node>{public static class TreapNode<T>extends BSTNode<T>{int rank;}public static class DefaultMaintainer<Node>implements Maintainer<Node>{@Override public void maintain(Node o){}}private static class DefaultNodeFactory<T,Node extends TreapNode<T>>implements NodeFactory<T,Node>{protected final Random random=new Random();public Node newNode(T value){Node o=(Node)new TreapNode<T>();o.value=value;o.rank=random.nextInt();o.son[0]=o.son[1]=null;return o;}@Override public Node newRoot(){return newNode(null);}}@Override public void insert(T x){insert(root,0,x);++size;}@Override public void insert(Node o){insert(root,0,o);++size;}@Override public int erase(T x){int cnt=erase(root,0,x);size-=cnt;return cnt;}@Override public int erase(Node o){int cnt=erase((Node)o.father,o.getSonIndex());size-=cnt;return cnt;}protected void insert(Node father,int d,T x){if(father.son[d]==null){Node son=factory.newNode(x);link(father,son,d);}else{Node o=(Node)father.son[d];int delta=comparator.compare(x,o.value);d=delta<0?0:1;insert(o,d,x);if(((Node)o.son[d]).rank>o.rank)rotate(o,d^1);else maintain(o);}}protected void insert(Node father,int d,Node x){if(father.son[d]==null){link(father,x,d);}else{Node o=(Node)father.son[d];int delta=comparator.compare(x.value,o.value);d=delta<0?0:1;insert(o,d,x);if(((Node)o.son[d]).rank>o.rank)rotate(o,d^1);else maintain(o);}}protected int erase(Node father,int d){Node o=(Node)father.son[d];Node lson=(Node)o.son[0];Node rson=(Node)o.son[1];if(lson==null)link(father,rson,d);else if(rson==null)link(father,lson,d);else{int d2=lson.rank>rson.rank?1:0;rotate(o,d2);erase((Node)o.father,d2);}maintain(father);return 1;}protected int erase(Node father,int d,T x){Node o=(Node)father.son[d];if(o==null)return 0;int delta=comparator.compare(x,o.value);int cnt=0;if(delta==0){cnt+=erase(father,d);cnt+=erase(father,d,x);}else{d=delta<0?0:1;cnt+=erase(o,d,x);maintain(father);}return cnt;}protected Treap(Comparator<T>comparator,Maintainer<Node>maintainer,NodeFactory<T,Node>factory){super(comparator,maintainer,(NodeFactory<T,Node>)factory);}public static<T,Node extends Treap.TreapNode<T>>Treap<T,Node>createTreap(Comparator<T>comparator,Maintainer<Node>maintainer,NodeFactory<T,Node>factory){return new Treap<T,Node>(comparator,maintainer,factory);}public static<T,Node extends Treap.TreapNode<T>>Treap<T,Node>createTreap(Comparator<T>comparator,NodeFactory<T,Node>factory){Maintainer<Node>maintainer=new DefaultMaintainer<>();return new Treap<T,Node>(comparator,maintainer,factory);}public static<T,Node extends Treap.TreapNode<T>>Treap<T,Node>createTreap(Comparator<T>comparator,Maintainer<Node>maintainer){NodeFactory<T,Node>factory=new DefaultNodeFactory<>();return new Treap<T,Node>(comparator,maintainer,factory);}public static<T,Node extends Treap.TreapNode<T>>Treap<T,Node>createTreap(Comparator<T>comparator){NodeFactory<T,Node>factory=new DefaultNodeFactory<>();Maintainer<Node>maintainer=new DefaultMaintainer<>();return new Treap<T,Node>(comparator,maintainer,factory);}}class RankTree<T,Node extends RankTree.RankTreeNode<T>>extends Treap<T,Node>implements RankTreeMethods<T,Node>{public s
|
