排列询问题解_牛客博客

解法1：AC
首先需要知道的是 $pair(x,y)$ 满足 $min(x,y)==gcd(x,y)$ 对于一个排列来说最多只有 $nlogn$ 对，所以我们可以暴力把这 $nlogn$ 对 $S$ 存下来，紧接着是如何处理在 $[l1,r1]$ 里面选 $x$ ， $[l2,r2]$ 里面选 $y$ 。对于这个容斥就好了。根据容斥定理可以转化为求 $F(l1,r2)-F(l1,l2-1)-F(r1+1,r2)+F(r1+1,l2-1)$ 。其中 $F(l,r)$ 代表从 $[l,r]$ 里面选取不同的 $x,y$ 并且满足 $min(x,y)==gcd(x,y)$ 的对数。
那么现在问题又转化为了如何快速求 $[l,r]$ 里面里面存在多少对 $(x,y)$ 满足 $min(x,y)==gcd(x,y)$ 。这个我们可以把拆分后的询问 $Q$ 按照右端点排个序，并且把之前暴力求得 $S$ 对也按照右端点排个序存下来。我们从左到右枚举右端点的位置 $Pos$ ，对于 $Pos==S[i].r$ 的时候的时候，我们在一个树状数组中 $add(S[i].l,1)$ ；然后对于 $Q[i].r==Pos$ ，贡献为 $Sum(Q[i].r)-Sum(Q[i].l-1)$ 。
时间复杂度 $O(n*logn*logn)$ ,空间复杂度 $O(n*logn)$ .
虽然说了那么多但是代码并不长。

const int N = 2e5+55;
int pos[N],c[N],ans[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:
    void add(int k,int num) {
        for(; k<N; c[k]+=num,k+=k&(-k));
    }
    int Sum(int k) {
        int sum=0;
        for(; k>0; sum+=c[k],k-=k&(-k));
        return sum;
    }
    vector<int> PermutationQuery(int n, int q, int* p, int pLen, int* l1, int l1Len, int* r1, int r1Len, int* l2, int l2Len, int* r2, int r2Len) {
        // write code here
        for(int i=1;i<=n;i++) pos[p[i-1]]=i;
        for(int i=1;i<=n;i++) {//处理nlogn组S
            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);
                val+=i;
            }
        }
        int tot=0;
        for(int i=0;i<q;i++) {//拆分询问
            int a=l1[i],b=r1[i],c=l2[i],d=r2[i];
            a++,b++,c++,d++;
            if(c-b>1) Q[++tot]={b+1,c-1,i,1};
            Q[++tot]={a,c-1,i,-1};
            Q[++tot]={b+1,d,i,-1};
            Q[++tot]={a,d,i,1};
        }
        sort(Q+1,Q+1+tot);
        int pos=1;
        for(int i=1;i<=n;i++) {//从左到右枚举右端点位置
            for(auto j:v[i]) add(j,1);//把S中右端点为i的，在树状数组中左端点位置处的值+1
            while(pos<=tot&&Q[pos].r==i) {//处理拆分后询问的右端点为i的
                ans[Q[pos].id]+=Q[pos].fg*(Sum(Q[pos].r)-Sum(Q[pos].l-1));
                pos++;
            }
        }
        vector<int>v;
        for(int i=0;i<q;i++) v.push_back(ans[i]);
        return v;
    }
};

解法2：TLE
对于每一个值存下这个值出现的位置，然后对于每组询问枚举长度较小的区间去判断因子/倍数是不是在另外一个区间中就好了。
时间复杂度 $O(nsqrtn*q)$ ，空间复杂度 $O(n)$ 。

const int N = 2e5+55;
int pos[N];
class Solution {
public:
    vector<int> PermutationQuery(int n, int q, int* p, int pLen, int* l1, int l1Len, int* r1, int r1Len, int* l2, int l2Len, int* r2, int r2Len) {
        // write code here
        vector<int>v;
        for(int i=0;i<n;i++) pos[p[i]]=i;
        for(int id=0;id<q;id++) {
            int cnt=0;
            if(r1[id]-l1[id]>r2[id]-l2[id] ) {//遍历小的区间
                swap(l1[id],l2[id]);
                swap(r1[id],r2[id]);
            }
            for(int i=l1[id];i<=r1[id];i++) {
                int val=p[i];
                for(int j=2;j*j<=val;j++) {//找因子的贡献
                    if(val%j==0) {
                        if(j*j!=val) {
                            if(l2[id]<=pos[j]&&pos[j]<=r2[id]) cnt++;
                            if(l2[id]<=pos[val/j]&&pos[val/j]<=r2[id]) cnt++;
                        }else if(l2[id]<=pos[j]&&pos[j]<=r2[id]) cnt++;
                    }
                }
                if(l2[id]<=pos[1]&&pos[1]<=r2[id]) cnt++;//特判1的贡献
                val+=p[i];
                while(val<=n) {//找p[i]的倍数的贡献
                    if(l2[id]<=pos[val]&&pos[val]<=r2[id]) cnt++;
                    val+=p[i];
                }
            }
            v.push_back(cnt);
        }
        return v;
    }
};