#C231116B. 排列(perm)

标签（Label）

数学推理
值域转下标

前言（Front talk)

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

网址（Website）

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

题解 - 排列(perm) - Super

题目（Problem）

给定一个长度为 $n$ 的排列 $A$ 与 $q$ 个询问。

每次询问给定一个区间 $l$，$r$，求 $F(l,r)$ 的值。

其中 $F(l,r)=\sum\limits_{i=l}^r\sum\limits_{j=i+1}^r f(a_i,a_j)$

其中 $f(x,y)$ 定义如下：

当 $x=y$ 时，其值为 $1$；
当 $x\not=y$ 时，其值为 $f(x+y-|x-y|,|x-y|)+1$；
若无限循环，将其值看作 $0$。

对于 $100%$ 的数据，$1 \leq n \leq 3\times 10^5$；$1 \leq q \leq 10^6$；$1 \leq l \leq r \leq n$。

题解（Solution）

当时是这么分析的：

$$
f(x,y)=
\begin{cases}
f(2y,x-y)+1 & x>y \\
f(2x,y-x)+1 & x<y \\
1 & x=y
\end{cases}
$$

然后就可以推理出：

$$
f(x,y)==k\Rightarrow
\begin{cases}
y=(2^k-1)\times x & x<y\\
\begin{cases}
2k_xx=(k_y+1)y,k_x+k_y=2^k,k为奇\\
2k_xx=(k_y-1)y,k_x+k_y=2^k,k为偶
\end{cases} & x>y
\end{cases}
$$

看起来非常的复杂，其实除了 $x<y$ 的情况外，剩下的情况 $x,y$ 的比例为：$1:1\ , 1:3 ,\ 3:5 ,\ 5:11 ,\ 11:21 ,\ 21:43 ,\ 43:85\dots$ 容易发现规律，便为上面总结的公式。

但是，把上面的公式再进行总结，就可以得出：
$$
f(x,y)=
\begin{cases}
k & (x+y)=2^k\times d\ (d\in N)\\
0 & (x+y)\not=2^k\times d\ (d\in N)
\end{cases}
$$
这个点应该是在开始讲的，但是为了还原我的思维过程（当时我注意到了这个点，但是没在意），我放到最后来讲，这里的 $d$ 是 $gcd(x,y)$ ，容易证明对于 $f(x,y)$ 来说，提取一个 $d$ 出来，原来的答案并不会受影响，因此，我们有了这一条思路：

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

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

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

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

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

代码（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; 
}