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

吹雪吹雪吹

2019-05-08 15:04:03

Solution

[$\large \texttt{Ynoi2017 由乃的}$~~赫鲁晓夫~~$\large \texttt{玉米田}$](http://xc.fubuki.cn/ynoi2017Nikita_Sergeyevich_Khrushchev/) 我这个菜鸡终于会一道由乃OI题了。 本题弱化版:[P3674 小清新人渣的本愿 ](https://www.luogu.org/problemnew/show/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})$ ```cpp // 写得很长,常数很大 #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{由乃可爱,欠雷赛高}$