[Codeforces Round #323(Div.1)] 582C-Superior Periodic Subarrays

来说说这个题吧~

首先在纸上画画可以知道：对于一个数 $a_i$，如果其在 Superior Periodic Subarrays 内（以下简称SPS），那么他要作比较的数与这个 SPS 的起始位置 $l$ 是没有关系的，只和 $n$ 与 $s$ 有关。

那么对于这个数，究竟要哪些数作比较呢？实际上，对于这个数而言，以 $\gcd(n,s)$ 为间隔 $gap$，那么实际上我们每次都往后跳 $gap$ 个数，就是它要比较的数。比如说 1 2 3 4 5 6（​$n=6$），那么设当前 $s=2$​，那么由于 ​$gap=\gcd(n,s)=\gcd(6,2)=2$，若数字 $3$ 在 SPS 内，那么其要作比较的数就是 $1,3,5$​。而显然，因为 $5>3$​，所以 $3$ 不可能在 SPS 内。

这就启发我们：我们可以根据一个 $gap$ 对这 $n$ 个数分组，对于每一组都是 $\frac{n}{gap}$ 个数。还是比如说 1 2 3 4 5 6，然后 $gap=2$​，那么我们就可以分成 1 3 5 和 2 4 6。因为奇数不可能和偶数作比较。然后对于每一组，显然只有组中最大的数才可能在 SPS 内。于是我们可以将每一组最大的数（可能有多个）设为 $1$​，其他的数设为 $0$，这样整个数组转化成了 $01$ 序列，然后就统计连续的 ​$1$ 对答案的贡献即可。

不过要注意一种情况：1 2 1 2，当 $gap=2$ 的时候，整个序列转化成了 1 1 1 1，但显然答案就不是直接统计。我们可以将数组开两倍，然后再分开来统计即可。

综上，由于 $gap$ 可以通过枚举 $n$ 的因子，然后后面每次处理都是 $\mathcal{O}(n)$ ​的，那么总的复杂度为 $\mathcal{O}(n\sigma (n))$

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
using namespace std;
const int N = 400050;
const int inf = 0x3f3f3f3f;
const ll mod = 998244353LL;
clock_t TIME_START, TIME_END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
int n;
int a[N], f[N], h[N];
ll ans;
vector<int> g[N];
inline ll work(int gap)
{
    mem(f, 0, (n << 1), int);
    mem(h, 0, (n << 1), int);
    for (int i = 0; i < gap; ++i)
    {
        int mx = 0;
        for (int j = i; j < n; j += gap)
        {
            mx = max(mx, a[j]);
        }
        for (int j = i; j < n; j += gap)
        {
            if (mx == a[j])
                f[j] = 1;
        }
    }
    for (auto i : g[gap])
        h[i]++;
    for (int i = 0; i < (n << 1); ++i)
        h[i + 1] += h[i];
    for (int i = 0; i < n; ++i)
        f[i + n] = f[i];
    for (int i = 1; i < (n << 1); ++i)
        if (f[i])
            f[i] += f[i - 1];
    ll ret = 0;
    for (int i = n; i < (n << 1); ++i)
    {
        ret += h[f[i]];
    }
    return ret;
}
void solve()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        scanf(
    for (int i = 1; i < n; ++i)
        g[__gcd(i, n)].pb(i);
    for (int i = 1; i < n; ++i)
    {
        if (n
            continue;
        ans += work(i);
    }
    cout << ans << endl;
}
int main()
{
    TIME_START = clock();
    int Test = 1;
    // cin >> Test;
    while (Test--)
        solve();
    TIME_END = clock();
    program_end();
    return 0;
}