Codeforces Round #136 (Div. 2)
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
好欢乐的一场CF，不过玩过头了，最后还是跪了。
这份题解来得有点晚，最近状态很差
A：Little Elephant and Function
一个递归，开始看错了，是先递归，然后再交换。
可以发现就是先交换前两个，然后依次下去，最后交换最后两个
序列为n,1,2,……n-1
B. Little Elephant and Numbers
简单数学题。直接暴力枚举n的约数，sqrt(n)的复杂度，然后判断是否有相同的数字
C. Little Elephant and Problem
直接把原数组排序之后，然后依次比对，如果有两位以上不同的， 说明一次交换不能完成，否则交换一次就可以了
D. Little Elephant and Array
当时欢乐过头了，然后就SB了。开始以为是统计区间不同数字的个数，迅速敲了一个线段树，然后样例不能过。然后就开始SB。后来看懂题意之后，觉得之前的线段树还有利用价值，就保留了，奠定了悲剧，之后的线段树+SET常数过大。最终还是T了。
其实可以发现1+2+……450>10^5。所以有效的数字肯定不超过450个，只要预处理找到这些数字，然后对于每一次查询枚举这些数字就可以了。但是可以知道，每一次查询，也是可以预处理的，当然可以用线段树之类的，dp[i][j]表示第i个数在1……j这j个位置中出现了多少次。
这样预处理的复杂度上限为450*n,每一次查询的复杂度为O(450)。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<cmath>#include<string>#include<vector>#include<algorithm>#include<map>#include<set>#define N 100005#define eps 1e-8#define inf 1<<30#define zero(a) fabs(a)<epsusing namespace std;struct N1{int step,pos;N1(){}N1(int x,int y):step(x),pos(y){}bool friend operator<(const N1 &a,const N1 &b){return a.step>b.step;}};struct N2{int step,pos;N2(){}N2(int x,int y):step(x),pos(y){}bool friend operator<(const N2 &a,const N2 &b){return a.step<b.step;}};priority_queue<N1>q1;priority_queue<N2>q2;int a[N],b[N],in[N],n;int main(){while(scanf("%d",&n)!=EOF){while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();for(int i=0;i<n;i++){scanf("%d",&a[i]);in[a[i]]=i;}for(int i=0;i<n;i++){scanf("%d",&b[i]);if(i>in[b[i]]) q1.push(N1(i-in[b[i]],i));else q2.push(N2(i-in[b[i]],i));}for(int i=0;i<n;i++){int ans=inf;if(!q1.empty()) ans=min(ans,abs(q1.top().step-i));if(!q2.empty()) ans=min(ans,abs(q2.top().step-i));printf("%d\n",ans);q1.push(N1(n+i-in[b[i]],inf));while(!q1.empty()&&(q1.top().pos<=i||q1.top().step-i-1<=0)){if(q1.top().pos<=i){q1.pop();continue;}q2.push(N2(q1.top().step,q1.top().pos));q1.pop();}while(!q2.empty()&&q2.top().pos<=i) q2.pop();}}return 0;}