题解 | #排列询问#

题目描述
牛妹有一个长度为n的排列p，她有q个询问。
每个询问包含l1，r1，l2，r2.她想知道从[l1,r1]中选取x，[l2,r2]中选取y,有多少组(x,y)满足min(x,y)==gcd(x,y)?

返回一个vector代表对这q个询问的答案

方法一：暴力求解

求解思路
对于本题目的求解，我们可以采用暴力循环的方式进行求解，我们遍历q次查询，遍历每一个区间的下标，与第二个区间的下标两两结合，并判断是否满足条件。根据上述思路即可得到本题目的答案。

图片说明

解题代码

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> myres(q, 0);
        for(int i = 0; i < q; i++)
        {
            for(int j = l1[i]; j <= r1[i]; j++)
            {   //遍历第一个区间
                int i1 = p[j];
                for(int k = l2[i]; k <= r2[i]; k++)
                {   //遍历第二个区间
                    int j1 = p[k];
                    if(i1 % j1 == 0 || j1 % i1 == 0) // 最小与gcd比较是否相等
                        myres[i]++;
                }
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：常数级内存空间，因此空间复杂度为 $O(1)$

方法二：贪心思想求解

求解思路
对于本题我们也可以使用贪心的思想进行求解，我们可以把拆分后的询问按照右端点大小进行排序，并且记录之前在数组V中的结果，并且从左到右枚举右端点的位置，把满足条件数对中右端点为i的进行记录，并且计算gcd值，按照上述思路，即可得到本问题的答案。

图片说明

解题代码

const int N = 2e5 + 10;
int pos[N], c[N];
vector<int> v[N];
struct node
{
    int l, r, id, fg;
    node(){}
    node(int a, int b, int c, int d) : l(a), r(b), id(c), fg(d){}
    bool friend operator < (node a, node b) // 为方便题目的解答，重载操作符
    {   //按照右边排序
        return a.r < b.r;
    }
}Q[N * 4];
class Solution {
public:
    int Sum(int k)
    {
        int sum = 0; //.记录结果
        for(; k > 0; k -= k & (-k))
            sum += c[k];
        return sum;
    }
    void add(int k, int num) // 定义add方法
    {
        for(; k < N; k += k & (-k))
             c[k] += num;
    }
    vector<int> PermutationQuery(int n, int q, vector<int>& p, vector<int>& l1, vector<int>& r1, vector<int>& l2, vector<int>& r2) {
        vector<int> myres(q, 0);
        for(int i = 0; i < n; i++) // 记录位置
            pos[p[i]] = i + 1;
        for(int i = 1; i <= n; i++)
        {   //处理nlogn组满足要求的
            int val = i + i;
            while(val <= n)
            {
                int l = pos[val]; // 记录左端点
                int r = pos[i]; // 记录右端点
                if(l > r) 
                    swap(l,r);
                v[r].push_back(l); // 存储nlogn对
                val += i;
            }
        }
        int total = 0;
        for(int i = 0; i < q; i++)
        {   //q次询问
            int a = l1[i], b = r1[i], c = l2[i], d = r2[i];
            a++, b++, c++, d++;
            if(c - b > 1)
                Q[++total] = {b + 1, c - 1, i , 1}; // 公式的几个数
            Q[++total] = {a, c - 1, i, -1};
            Q[++total] = {b + 1, d, i, -1};
            Q[++total] = {a, d, i, 1};
        }
        sort(Q + 1, Q + 1 + total); // 快排
        int pos = 1;
        for(int i = 1; i <= n; i++)
        {   //从左到右枚举右端点位置
            for(int j = 0; j < v[i].size(); j++)
                add(v[i][j], 1); // 把右端点为i的，在树状数组中左端点位置处的值+1
            while(pos <= total && Q[pos].r == i)
            {   //处理拆分后询问的右端点为i的
                myres[Q[pos].id] += Q[pos].fg * (Sum(Q[pos].r) - Sum(Q[pos].l - 1));
                pos++;
            }
        }
        return myres; // 返回结果
    }
};

复杂度分析
时间复杂度：遍历的时候一层循环加两次贪心时间(logn),因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：对数组进行存储，因为涉及到左右端点，因此空间复杂度为 $O(nlogn)$