#C231116B. 排列(perm)

前言（Front talk)

这道题自己推了大部分，但是后面因为方向错了，以及不注重细节的缘故，导致想出了正解但是自身没有意识到，还以为时间超了。

网址（Website）

题目详情 - 排列(perm) - Super

题解 - 排列(perm) - Super

题目（Problem）

给定一个长度为的排列与个询问。

每次询问给定一个区间，，求的值。

其中

其中定义如下：

当时，其值为；
当时，其值为；
若无限循环，将其值看作。

对于的数据，；；。

题解（Solution）

当时是这么分析的：

然后就可以推理出：

$为奇为偶$

看起来非常的复杂，其实除了的情况外，剩下的情况的比例为：容易发现规律，便为上面总结的公式。

但是，把上面的公式再进行总结，就可以得出：

这个点应该是在开始讲的，但是为了还原我的思维过程（当时我注意到了这个点，但是没在意），我放到最后来讲，这里的是，容易证明对于来说，提取一个出来，原来的答案并不会受影响，因此，我们有了这一条思路：

int d=gcd(x,y);
if(x/d+y/d==2^k)
	f(x,y)=(int)log2((x+y)/d)

这样就可以只从质数的角度来思考问题

然后思考如何将通过此题：

枚举的所有的次幂；for(int k=2;k<=20;k++)
枚举奇数，满足，为什么偶数不行呢？因为要互质。
枚举，并将值与值所对应的位置连边，，注意从右到左连，方便后续处理。因为题目条件是==排列==，因此才可以在这样的时间内枚举完。这也是我当时忽略的地方。

接下来就是处理每一条连边，或者说每一个区间，对于每一个询问，我们可以先将询问离线，然后遍历每个，每次先将区间加入树状数组处理，记录前缀区间数量，相减即得最终答案。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;++i)
#define Rof(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
inline int input(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int N = 1012345;
vector<pair<int,int>> ft[N],que[N];
int n,q,c[N],a[N],id[N];
int ans[N];

//树状数组 
inline int lbt(int x){return x&(-x);}
void update(int x,int k){for(int i=x;i<=n;i+=lbt(i))c[i]+=k;}
inline int ask(int x){int res=0;for(int i=x;i;i-=lbt(i))res+=c[i];return res;}

signed main(){
	freopen("perm.in","r",stdin);
	freopen("perm.out","w",stdout);
	
	n=input();For(i,1,n) id[a[i]=input()]=i;
	q=input();For(i,1,q){
		int l=input(),r=input();
		que[r].emplace_back(l,i);
	}for(int k=2;(1<<k)<=n*2;++k){//每次的贡献  时间复杂度 O(logn) 
		int sum=(1<<k);//相当于 2^k 
		for(int j=1;j*2<=sum;j+=2){//枚举所有的奇数 
			for(int x=j,y=sum-j;y<=n;x+=j,y+=sum-j){//因为是排列，所以可以枚举因数d（其实就是倍数），然后直接连边 
				int l=min(id[x],id[y]),r=max(id[x],id[y]);
				ft[r].emplace_back(l,k);
			}
		}
	}For(r,1,n){
		for(auto p:ft[r]){
			int l=p.first,v=p.second;
			update(l,v);
		}for(auto p:que[r]){
			int l=p.first;
			ans[p.second]=ask(r)-ask(l-1);
		}
	}For(i,1,q) printf("%lld\n",ans[i]);
	return 0; 
}