题解 | #排列询问#

一.题目描述
NC540排列询问
牛妹有一个长度为n的排列p，她有q个询问。
每个询问包含l1，r1，l2，r2.她想知道从[l1,r1]中选取x，[l2,r2]中选取y,有多少组(x,y)满足min(x,y)==gcd(x,y)?
返回一个vector代表对这q个询问的答案
图片说明
二.算法(暴力)

读懂题目我们可以采用暴力的方法来解决本题目，我们可以两重循环的方式进行求解，我们遍历q次查询，找到每一次遍历的数对个数，并判断是否满足条件(这块有一点我们需要注意，对于判断是否满足条件我们不能暴力判断，两个数的最小值是否等于两个是的最小公倍数，那样会超时，我们要想到等式一边的值一定是min(a,b)中的a或者b，所以判断等价于(a%b==0||b%a==0),这样就不会超时)。下面是完整代码：

class Solution {
public:
    vector<int> PermutationQuery(int n, int q, vector<int>& p, vector<int>& l1, vector<int>& r1, vector<int>& l2, vector<int>& r2) {
        vector<int> ans(q,0);
        for(int i=0;i<q;i++){
            for(int j=l1[i];j<=r1[i];j++){
                int a=p[j];
                for(int k=l2[i];k<=r2[i];k++){
                    int b=p[k];
                    //不能直接判断会超时
                    //分析后的判断a%b==0||b%a==0
                    if(a%b==0||b%a==0){
                        ans[i]++;
                    }
                }
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^{2})$ 对于每一次都需要二重循环
空间复杂度： $O(n)$ 需要额外开辟数组返回答案
优缺点：时间复杂度高，但是便于实现
三.算法(java实现)
同样也可以采用java去实现，下面是完整代码：

import java.util.*;


public class Solution {
    //java的静态代码块和静态成员变量
    static final int[] num;
    static{
       num=new int[100005];
    }
    public int[] PermutationQuery (int n, int q, int[] p, int[] l1, int[] r1, int[] l2, int[] r2) {
        for(int i=0;i<q;i++){
            for(int j=l1[i];j<=r1[i];j++){
                int a=p[j];
                for(int k=l2[i];k<=r2[i];k++){
                    int b=p[k];
                    //不能直接判断会超时
                    //分析后的判断a%b==0||b%a==0
                    if(a%b==0||b%a==0){
                        num[i]++;
                    }
                }
            }
        }
        //为了使返回值符合要求
        int[] ans=new int[q];
        for(int i=0;i<q;i++){
            ans[i]=num[i];
        }
        return ans;
    }
}

时间复杂度： $O(n^{2})$ 对于每一次都需要二重循环
空间复杂度： $O(n)$ 需要额外开辟数组返回答案(java的返回值相比于c++还比较麻烦)
优缺点：时间复杂度高，但是便于实现