树状数组 偏序    发布于 2019-09-08   436人围观   0条评论

题目大意

给定一个1---n的排列和m次询问,每次询问区间 [l,r]之间min(pi,pj) = gcd(pi,pj)的数对的个数。

题解

一开始看到是数对问题还以为是莫队,不过话说回来莫队WA了而不是T是怎么回事……

首先我们需要注意min(pi,pj) = gcd(pi,pj)可以转化为pi和pj互为因数和倍数的关系(这样可以做一点常数上面的优化,也更好判断总体的数对的个数)。

然后我们要知道,所有的数对个数大概是O(nlogn)级别的。

于是我们可以枚举每个数的倍数预处理出所有的数对的位置对(i,j),我们尽量让i比j大,这有利于下面的思路。

然后有没有发现这个位置对很像是二维平面上的坐标啊……

欸,貌似询问也可以转化成二维坐标(r,l)啊……。

那如果我们都像上面把所有数对和询问都转化成二维坐标的话……那么就成了下面的经典二维偏序问题:

平面上有若干个点,求问横坐标小于等于r,纵坐标大于等于l的点的个数有多少。

于是我们对坐标按照横坐标排序,询问按照先r后l从小到大排序,然后横向扫一遍所有横坐标上的点,用树状数组维护当前扫过的所有点的个数。每一次询问的答案都是query(n) - query(l-1)。

非常经典的二维偏序问题,时间复杂度是O(nlogn),我还给想成了莫队,真的惭愧,果然还是练的太少……

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int maxn = 1e5+5;
struct quest{
    int l,r,id;
    bool operator < (const quest &b)const{
        return (this->r == b.r) ? (this->l < b.l) : (this->r < b.r);
    }
}q[maxn];
int cnt = 0;
int a[maxn];
int c[maxn];
int ans[maxn];
int lowbit(int x){
    return x & -x;
}
struct point{
    int x,y;
    bool operator < (const point &b) const{
        return (this->x == b.x) ? (this->y
查看更多