题解 P5355 【[Ynoi2017]由乃的玉米田】

2019-05-08 15:04:03


$\large \texttt{Ynoi2017 由乃的}$赫鲁晓夫$\large \texttt{玉米田}$

我这个菜鸡终于会一道由乃OI题了。

本题弱化版:P3674 小清新人渣的本愿

本题的操作1~3可以直接从P3674贺过来。

注意,除法询问要求整除

对于除法的询问,若有 $ x \ge \sqrt{max\{a_i\}} $ 则暴力查找,单次复杂度 $O(\sqrt{n})$ 。

对于剩下的每个 $x$ 的值,我们可以在 $O(n·log_2·n+q)$ 的时间内处理出所有该值的答案:先将询问按左端点降序排列。然后取一个指针,一开始指向 $n$ 。若当前询问的左端点为 $l$ ,则将 $[l,j]$ 上所有元素的贡献插入树状数组中,并使 $j = l - 1$,完成后直接在树状数组上获取当前询问的答案。

这一部分的时间复杂度为 $O(n\sqrt{max\{a_i\}}·log_2n+q)$

注意询问中可能存在 $x=0$ 。

总时间复杂度 $O(n\sqrt{max\{a_i\}}·log_2n+q+\frac{n·q}{64})$

// 写得很长,常数很大
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cmath>
#define maxn 100005

using namespace std;

bitset<maxn << 1> vis[2], flg;
int pos[maxn], n, m, ans[maxn], a[maxn], nxt[maxn];
int cnt[maxn], blck, Maxi, len, lim, tot, c[maxn];
int sum[maxn];

class Query
{
  public:
    int l, r, opt, x, id;
    bool operator < (const Query b)const
    {
        if (pos[l] != pos[b.l])
            return pos[l] < pos[b.l];
        return (pos[l] & 1) ? r < b.r : r > b.r;
    }
} q[maxn], d[maxn];

bool cmp(const Query &a, const Query &b)
{
    return a.x < b.x || (a.x == b.x && a.l > b.l);
}

inline int read()
{
    char ch = getchar();
    int ret = 0, f = 1;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            f = -f;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

inline void add(int x)
{
    ++cnt[a[x]];
    if (cnt[a[x]] == 1)
    {
        vis[0][a[x] + maxn] = 1;
        vis[1][maxn - a[x]] = 1;
    }
}

inline void del(int x)
{
    --cnt[a[x]];
    if (!cnt[a[x]])
    {
        vis[0][a[x] + maxn] = 0;
        vis[1][maxn - a[x]] = 0;
    }
}

inline int Min(const int &x, const int &y)
{
    return x < y ? x : y;
}

inline void Add(int k, const int &x)
{
    while (k <= n)
    {
        c[k] = Min(c[k], x);
        k += k & -k;
    }
}

inline int Ask(int k)
{
    int res = n + 1;
    while (k)
    {
        res = Min(res, c[k]);
        k -= k & -k;
    }
    return res;
}

void Solve()
{ // 处理所有 x <= sqrt(max{a[i]}) 的询问
    sort(d + 1, d + 1 + tot, cmp);
    for (int l = 1, r; l <= tot; l = r + 1)
    {
        r = l + 1;
        while (d[r].x == d[l].x && r <= tot)
            ++r;
        --r;
        memset(c, 127, sizeof(c));
        memset(nxt, 127, sizeof(nxt));
        for (int i = l, j = n; i <= r; ++i)
        {
            while (j >= d[i].l)
            {
                nxt[a[j]] = j;
                if (1ll * a[j] * d[l].x <= 1ll * Maxi)
                    Add(j, nxt[a[j] * d[l].x]);
                if (a[j] % d[l].x == 0)
                    Add(j, nxt[a[j] / d[l].x]);
                --j;
            }
            if (d[i].l > d[i].r)
                ans[d[i].id] = 0;
            else
                ans[d[i].id] = (Ask(d[i].r) <= d[i].r);
        }
    }
}

int main()
{
    n = read(), m = read();
    blck = sqrt(n);
    for (int i = 1; i <= n; ++i)
    {
        a[i] = read(), pos[i] = (i - 1) / blck + 1;
        Maxi = max(Maxi, a[i]);
        sum[i] = sum[i - 1] + (a[i] == 0 ? 1 : 0);
    }
    lim = sqrt(Maxi);
    for (int i = 1; i <= m; ++i)
    {
        ++len;
        q[len].opt = read();
        q[len].l = read(), q[len].r = read();
        q[len].x = read();
        q[len].id = i;
        if (q[len].opt == 4 && q[len].x <= lim && q[len].x != 0)
        {
            d[++tot] = q[len];
            --len;
        }
    }
    Solve();
    sort(q + 1, q + 1 + len);
    register int L = 1, R = 0;
    for (int i = 1; i <= len; ++i)
    {
        while (R < q[i].r)
            add(++R);
        while (L > q[i].l)
            add(--L);
        while (L < q[i].l)
        {
            del(L);
            ++L;
        }
        while (R > q[i].r)
        {
            del(R);
            --R;
        }
        if (q[i].opt == 1)
        {
            ans[q[i].id] = ((vis[0] >> q[i].x) & vis[0]).any();
        }
        else if (q[i].opt == 2)
        {
            ans[q[i].id] = ((vis[0] >> q[i].x) & vis[1]).any();
        }
        else if (q[i].opt == 3)
        {
            ans[q[i].id] = 0;
            if (vis[0][maxn] && q[i].x == 0)
            {
                ans[q[i].id] = 1;
                continue;
            }
            for (int k = 1; k * k <= q[i].x; ++k)
            {
                if (q[i].x % k)
                    continue;
                if (vis[0][k + maxn] && vis[0][q[i].x / k + maxn])
                {
                    ans[q[i].id] = 1;
                    break;
                }
            }
        }
        else
        {
            ans[q[i].id] = 0;
            if (q[i].x == 0)
            {
                if (vis[0][maxn] && cnt[0] < R - L + 1)
                    ans[q[i].id] = 1;
            }
            else
            {
                for (int k = 1, j = q[i].x; j <= Maxi; ++k, j += q[i].x)
                {
                    if (vis[0][k + maxn] && vis[0][j + maxn])
                    {
                        ans[q[i].id] = 1;
                        break;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= m; ++i)
        printf("%s\n", ans[i] ? "yuno" : "yumi");
    return 0;
}

$\color{white} \text{由乃可爱,欠雷赛高}$