求助

回复帖子

@团队官方账号 2020-05-24 10:27 回复

这道题是昨天code+7的第4题,蒟蒻听大佬讲的,可还是不懂。

#include <bits/stdc++.h>
using namespace std;
int n, m, mn[100010], lg[100010], st[20][100010];
int c[100010], l[1000010], r[1000010];
vector<int> M[1000010];
void add(int p) {
    for (; p <= n; p += p & -p) c[p]++;
}
int sum(int p) {
    int s = 0;
    for (;p; p -= p & -p) s += c[p];
    return s;
}
int main() {
    scanf("%d %d", &n, &m);
    memset(mn, 0x3f, sizeof(mn));
    for (int i = 1, op, x, y; i <= m; i++) {
        scanf("%d %d", &op, &x);
        if (op == 1) {
            if (mn[x] < 1e9) continue;
            mn[x] = i;
        } else {
            scanf("%d", &y);
            l[i] = x, r[i] = y;
        }
    }
    for (int i = 1; i <= n; i++) {
        st[0][i] = mn[i];
        if (i > 1) lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
        }
    }
    auto query = [&](int l, int r) {
        int k = lg[r - l + 1];
        return min(st[k][l], st[k][r - (1 << k) + 1]);
    };
    for (int i = 1; i <= n; i++) {
        int mx = 0;
        for (int l = 1; l <= n; l += i) {
            int r = min(n, l + i - 1);
            mx = max(mx, query(l, r));
            if (mx > 1e9) break;
            M[mx].push_back(i);
        }
    }
    for (int i = 1; i <= n; i++) add(i);
    for (int i = 1; i <= m; i++) {
        for (int j : M[i]) add(j);
        if (l[i]) printf("%d\n", sum(r[i]) - sum(l[i] - 1));
    }
    return 0;
}
void add(int p) {
    for (; p <= n; p += p & -p) c[p]++;
}
int sum(int p) {
    int s = 0;
    for (;p; p -= p & -p) s += c[p];
    return s;
}

是啥意思啊,求教

@yzyjh  2020-05-24 10:55 回复 举报

那整个程序是啥意思呢,能不能私信教教蒟蒻

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。