ICPC 2023 Xi'an

I

考虑对于每一个约数 $d$ ，寻找满足条件的区间。对于一个确定的 $j$ ，要使区间尽可能小，应该使 $i$ 尽可能大，在此基础上找到尽可能小的 $k$ 。从后向前枚举 $j$ ，那么 $i$ 也单调递减，如果 $k$ 反而增大，那么一定不优。因此令 $k$ 单减即可。那么这一部分复杂度为 $O(nd)$ ，其中 $d$ 为 $10 ^ 6$ 内约数最多的数的约数个数。

剩下的部分为二维偏序问题。注意到修改较多，可以采用 $O(1)$ 修改，$O(\sqrt n)$ 查询的分块做法更优。

查看代码

#include <cstdio>
#include <vector>
#define pb push_back
using namespace std;
const int N = 1.5e5 + 10, Q = 1e5 + 10, K = 1e6, M = K + 10;
int n, m, w[N], ans[Q];
vector <int> f[M], p[M];
struct Modify
{
    int l, k;
    Modify (int _l, int _k) : l(_l), k(_k) { }
};
vector <Modify> ms[N];
struct Query
{
    int l, id;
    Query (int _l, int _id) : l(_l), id(_id) { }
};
vector <Query> qs[N];
int tr[N];
void chkmax (int &x, int k) { if (k > x) x = k; }
void add (int x, int k)
{
    for (; x; x -= x & -x)
        chkmax(tr[x], k);
}
int query (int x)
{
    int res = 0;
    for (; x <= n ; x += x & -x)
        chkmax(res, tr[x]);
    return res;
}
int main ()
{
    for (int i = 1; i <= K; ++i)
        for (int j = 1; i * j <= K; ++j)
            f[i * j].pb(i);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &w[i]);
        for (int j : f[w[i]])
            p[j].pb(i);
    }
    for (int i = 1; i <= K; ++i)
    {
        if (p[i].size() < 3) continue;
        int c = p[i].size() - 1;
        for (int b = p[i].size() - 2; b; --b)
        {
            int a = b - 1, d = p[i][b] * 2 - p[i][a];
            while (c - 1 > b && p[i][c - 1] >= d) --c;
            if (p[i][c] < d) continue;
            ms[p[i][c]].pb(Modify(p[i][a], i));
        }
    }
    for (int i = 1, l, r; i <= m; ++i)
    {
        scanf("%d%d", &l, &r);
        qs[r].pb(Query(l, i));
    }
    for (int i = 1; i <= n; ++i)
    {
        for (Modify j : ms[i]) add(j.l, j.k);
        for (Query j : qs[i])
            ans[j.id] = query(j.l);
    }
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

查看代码