query 线段树 + 区间排序

https://nanti.jisuanke.com/t/41391

这个题目没有很难想，比较暴力，但是要会算复杂度，不会算复杂度，就会觉得自己的算法会超时，实际上不会。

这个题目就是直接暴力求出每一个数的在1e5以内的所有的约数和倍数，然后更新，就像之前写过的E - No Pain No Game 线段树离线处理区间排序一样

算一下复杂度，调和级数要用两次，一次来求约数一次来求倍数，复杂度都是n*logn 所以平均下来每一个的约数大约就是logn

因为有个两倍的关系所以就是2*logn

线段树的复杂度，每次更新是logn ，要遍历一次

所以总的复杂度就是2*n*logn*logn，这个肯定不会超时的。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <iostream>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
vector<int>num[maxn];
int a[maxn], vis[maxn], c[maxn], ans[maxn];
int n, m;
struct node
{
    int l, r, id;
    node(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
}ex[maxn];
bool cmp(node a,node b)
{
    return a.r < b.r;
}

int lowbit(int x)
{
    return x & (-x);
}

void update(int x,int k)
{
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int ans = 0;
    while (x > 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

int main()
{
    for (int i = 1; i < maxn; ++i) {
        for (int j = 2*i; j < maxn; j += i) {
            num[j].push_back(i);//先把每个数的因子有哪些打个表，由调和级数可知复杂度为o(nlog n)
        }
    }
    for (int i = 1; i < maxn; ++i) {
        for (int j = 2 * i; j < maxn; j += i) {
            num[i].push_back(j);
        }
    }
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        ex[i] = node(l, r, i);
    }
    memset(vis, -1, sizeof(vis));
    sort(ex + 1, ex + 1 + m, cmp);
    int now = 1;
    for (int i = 1; i <= n; i++) {
        int x = a[i];
        for (int j = 0; j < num[x].size(); j++) {
            int y = num[x][j];
            if (vis[y] != -1) update(vis[y], 1);
        }
        vis[x] = i;
        while (now <= m && i == ex[now].r) {
            int res = getsum(ex[now].r) - getsum(ex[now].l - 1);
            ans[ex[now].id] = res;
            now++;
        }
    }
    for (int i = 1; i <= m; i++) printf("%d
", ans[i]);
    return 0;
}

View Code

query 线段树 + 区间排序

推荐阅读