题解 P5355 【[Ynoi2017]由乃的玉米田】
吹雪吹雪吹
2019-05-08 15:04:03
[$\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{由乃可爱,欠雷赛高}$