题解 | #排列询问#

思路：

题目的主要信息：

p有n个数，一共有q次询问
每次询问从 $[l1,r1]$ 中选取 $x$ ， $[l2,r2]$ 中选取 $y$ ,求有多少组 $(x,y)$ 满足 $min(x,y)==gcd(x,y)$ ，每个区间都是p的下标，从0开始

方法一：暴力法
具体做法：
遍历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> res(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];
                    if(a % b == 0 || b % a == 0)  //最小与gcd比较是否相等
                        res[i]++;
                }
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(q*n^2)$ ， $q$ 次询问，每次询问都是两层遍历，最坏情况下每个区间长度都是 $n$
空间复杂度： $O(1)$ ，res属于返回必要空间，不属于额外空间

方法二：贪心
具体做法：
对于任意一个排列p，满足 $min(x,y)==gcd(x,y)$ 的最多只有 $nlog_2n$ 对，我们可以在 $O(nlog_2n)$ 的时间内暴力的求出这些符合条件的组合，记录到数组v中，然后就是在区间内选 $x$ 与 $y$ 。
如果我们以 $f(l,r)$ 表示从区间 $[l,r]$ 中选取不同的满足上述条件数对的数量，于是依据容斥原理我们求这个就可以了： $f(l1,r2)-f(l1,l2-1)-f(r1+1,r2)+f(r1+1,l2-1)$ 。
我们可以把拆分后的询问Q按照右端点大小进行排序，并且之前记录在数组v中的结果也按右端点排序。从左到右枚举右端点的位置，把满足条件数对中右端点为 $i$ 的，在树状数组（即v)中左端点位置处的值+1，如果处理后右端点刚好为i，利用上述公式计算值，代码中是Sum函数计算的减价。

class Solution {
public:
    int pos[200010], s[200010];
    vector<int> v[200010];
    struct node{
        int l, r, id, flag;
        node(){l = 0, r = 0, id = 0, flag = 0;}
        node(int a, int b, int c, int d) : l(a), r(b), id(c), flag(d){}
        bool friend operator <(node a, node b) { //按照右边排序
            return a.r < b.r;
    }
}Q[200010 * 4]; //查询的结构
    int N = 200010;
    void add(int k, int num) {
        for(; k < N; k += k & (-k))
             s[k] += num;
    }
    int Sum(int k) {
        int sum = 0;
        for(; k > 0; k -= k & (-k))
            sum += s[k];
        return sum;
    }
    vector<int> PermutationQuery(int n, int q, vector<int>& p, vector<int>& l1, vector<int>& r1, vector<int>& l2, vector<int>& r2) {
        vector<int> res(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 all = 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[++all] = {b + 1, c - 1, i , 1};  //公式的几个数
            Q[++all] = {a, c - 1, i, -1};
            Q[++all] = {b + 1, d, i, -1};
            Q[++all] = {a, d, i, 1};
        }
        sort(Q + 1, Q + all + 1); //排序
        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 <= all && Q[pos].r == i) {//处理拆分后询问的右端点为i的
                res[Q[pos].id] += Q[pos].flag * (Sum(Q[pos].r) - Sum(Q[pos].l - 1));
                pos++;
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n(log_2n)^2+q)$ ，最坏时间为处理的时候 $n$ 遍历，里面两个 $O(log_2n)$ ，外面还有一个 $q$ 次询问的遍历
空间复杂度： $O(nlog_2n)$ ，最多的空间是存储那 $nlog_2n$ 对满足要求的数组