2019-05-08 15:04:03

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

// 写得很长，常数很大
#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);
}

{
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()
{
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].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)
while (L > q[i].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{由乃可爱，欠雷赛高}$

• star
首页