The Preliminary Contest for ICPC Asia Xuzhou 2019 I.query 树状数组 二维偏序
树状数组 偏序   发布于 2019-09-08   430人围观  0条评论
树状数组 偏序   发表于 2019-09-08   430人围观  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 < b.y) : (this->x < b.x);
    }
}p[maxn*30];
void update(int pos,int x){
    while(pos <= n){
        c[pos] += x;
        pos += lowbit(pos);
    }
    return;
}
int query(int pos){
    int res = 0;
    while(pos > 0){
        res += c[pos];
        pos -= lowbit(pos);
    }
    return res;
}
int pos[maxn];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        pos[a[i]] = i;
    }
    for(int i = 1;i <= n;++i){
        int x = pos[i];
        for(int j = 2;j * i <= n;++j){
            int y = pos[j*i];
            p[++cnt].x = x;
            p[cnt].y = y;
            if(p[cnt].x < p[cnt].y)swap(p[cnt].x,p[cnt].y);
        }
    }
    for(int i = 1;i <= m;++i){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    memset(ans,0,sizeof(ans));
    sort(p+1,p+cnt+1);
    sort(q+1,q+m+1);
    int now = 1;
    for(int i = 1;i <= m;++i){
        int r = q[i].r;
        for(;now <= cnt && p[now].x <= r;++now){
            update(p[now].y,1);
        }
        ans[q[i].id] = query(n) - query(q[i].l-1);
    }
    for(int i = 1;i <= m;++i){
        cout << ans[i] << "\n";
    }
    return 0;
}

 

上一篇: The 2019 Asia Nanchang First Round Online Programming Contest A.Enju With math problem 思维题 欧拉筛

下一篇: 2018 ACM/ICPC Asia Jiaozuo Regional K.Counting Failures on a Trie Trie 思维题 倍增 Hash

立即登录,发表评论
没有帐号?立即注册
0 条评论