51Nod-1533-一堆的堆

ACM模版

描述

题解

离线处理，先将数据离散化，也就是根据 a 排序即可。因为要维护 k 叉最小堆，所以我们需要从小到大进行处理，加入树状数组中，先一遍循环访问这些结点的孩子所在区间有多少不合法，然后再将这些结点插入，以此而往，这里需要强调的是，这些指的不是所有，而是值一样的结点， 将所有值一样的结点分批次处理，也就是一个循环的问题，访问完一批添加一批而已。这里需要说的是，对于树状数组，我们要求某一个区间 [l,r] 的不合法结点个数时只需要通过求 [1,r]、[1,l−1] 之差就好了，这里不难理解。

大致上就这样，可以加一下输入外挂，十分好的一道题，貌似有人用主席树也可解，反正我不是特别会……%%%

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;

int n;
int arr[MAXN];
int ans[MAXN];
pii a[MAXN];

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

void add(int x, int d)
{
    while (x < MAXN)
    {
        arr[x] += d;
        x += lowbit(x);
    }
}

int query(int x)
{
    int ans = 0;
    while (x)
    {
        ans += arr[x];
        x -= lowbit(x);
    }
    return ans;
}

void solve ()
{
    memset(arr, 0, sizeof (arr));
    memset(ans, 0, sizeof (ans));

    for (int i = 1; i <= n; )
    {
        int tmp = i;
        while (tmp <= n && a[tmp].first == a[i].first)
        {
            tmp++;
        }
        for (int j = i; j < tmp; j++)
        {
            int v = a[j].second;
            for (int k = 1; k <= n - 1 && k * (v - 1) + 2 <= n; k++)
            {
                ans[k] += query(min(n, k * v + 1)) - query(k * (v - 1) + 1);
            }
        }
        for (int j = i; j < tmp; j++)
        {
            add(a[j].second, 1);
        }
        i = tmp;
    }
}

template <class T>
inline bool scan_d(T &ret)
{
    char c;
    int sgn;
    if (c = getchar(), c == EOF)
    {
        return 0; //EOF
    }
    while (c != '-' && (c < '0' || c > '9'))
    {
        c = getchar();
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0');
    }
    ret *= sgn;
    return 1;
}

int main(void)
{
    scan_d(n);

    for (int i = 1; i <= n; i++)
    {
        scan_d(a[i].first);
        a[i].second = i;
    }
    sort(a + 1, a + n + 1);

    solve();

    for (int i = 1; i < n - 1; i++)
    {
        printf("%d ", ans[i]);
    }
    printf("%d\n", ans[n - 1]);

    return 0;
}