QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#340704 | #7782. Ursa Minor | goodier | TL | 4ms | 18116kb | C++17 | 6.0kb | 2024-02-29 11:28:05 | 2024-02-29 11:28:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10, B = N, T = N;
const ll MOD = 998244353, base = 34261314;
int f[N][19], len[N], a[N], b[N], ba[N], n, m, q, ans[N], L[N], R[N], pos[N], t;
ll pw[N], spw[N], inv[N], s[N][2][2];
ll power(ll a, ll b)
{
ll c = 1;
while(b)
{
if(b & 1) c = c * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return c;
}
struct Op{
int op, l, r, x, y, k;
}qr[N];
int read()
{
int x = 0, t = 1; char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') t = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * t;
}
void write1()
{
putchar('Y'), putchar('e'), putchar('s'), putchar('\n');
}
void write0()
{
putchar('N'), putchar('o'), putchar('\n');
}
int gcd(int a, int b)
{
while(b)
{
int c = a;
a = b, b = c % b;
}
return a;
}
int query(int l, int r)
{
int t = len[r - l + 1];
return gcd(f[l][t], f[r - (1 << t) + 1][t]);
}
void init()
{
for(int i = 2; i <= m; i++) len[i] = len[i >> 1] + 1;
for(int i = 1; i <= m; i++) f[i][0] = b[i];
for(int j = 1; j <= len[m]; j++)
{
for(int i = 1; i + (1 << j) - 1 <= m; i++)
{
f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * (ll)base % MOD; spw[0] = 1; for(int i = 1; i <= n; i++) spw[i] = (spw[i - 1] + pw[i]) % MOD;
for(int i = 0; i <= n; i++) inv[i] = power(pw[i], MOD - 2);
t = n / B;
for(int i = 1; i <= t; i++)
{
L[i] = R[i - 1] + 1, R[i] = i * B;
for(int j = L[i]; j <= R[i]; j++) pos[j] = i;
}
if(R[t] < n)
{
t++;
L[t] = R[t - 1] + 1, R[t] = n;
for(int j = L[t]; j <= R[t]; j++) pos[j] = t;
}
}
void add1(int x, ll y, int c)
{
if(y < 0) y += MOD;
s[x][0][c] += y, s[pos[x]][1][c] += y;
if(s[x][0][c] >= MOD) s[x][0][c] -= MOD;
if(s[x][1][c] >= MOD) s[x][1][c] -= MOD;
}
void add2(int x, ll y, int c)
{
for(int i = x; i <= R[pos[x]]; i++)
{
s[i][0][c] += y;
if(s[i][0][c] >= MOD) s[i][1][c] -= MOD;
}
for(int i = pos[x]; i <= t; i++)
{
s[i][1][c] += y;
if(s[i][1][c] >= MOD) s[i][1][c] -= MOD;
}
}
ll ask2(int x, int c)
{
if(x == 0) return 0;
ll res = s[x][0][c] + s[pos[x] - 1][1][c];
if(res >= MOD) res -= MOD;
return res;
}
ll ask1(int x, int c)
{
if(x == 0) return 0;
ll res = 0;
for(int i = 1; i < pos[x]; i++)
{
res += s[i][1][c];
if(res >= MOD) res -= MOD;
}
for(int i = L[pos[x]]; i <= x; i++)
{
res += s[i][0][c];
if(res >= MOD) res -= MOD;
}
return res;
}
ll query1(int l, int r, int c)
{
return (ask1(r, c) - ask1(l - 1, c) + MOD) % MOD;
}
ll query2(int l, int r, int c)
{
ll res = ask2(r, c) - ask2(l - 1, c) + MOD;
if(res >= MOD) res -= MOD;
return res;
}
void solve1()
{
for(int k = 1; k <= T; k++)
{
for(int i = 1; i <= n; i++)
{
a[i] = ba[i]; s[i][0][0] = s[i][0][1] = s[i][1][0] = s[i][1][1] = 0;
}
for(int i = 1; i <= n; i++)
{
if(i % k == 0) add1(i, a[i], 0);
add1(i, (ll)a[i] * pw[i % k] % MOD, 1);
}
for(int i = 1; i <= q; i++)
{
if(qr[i].op == 1)
{
int x = qr[i].x, dt = qr[i].y - a[x];
if(x % k == 0) add1(x, dt, 0);
add1(x, (ll)dt * pw[x % k] % MOD, 1);
a[x] += dt;
}
else if(qr[i].k == k)
{
int l = qr[i].l, r = qr[i].r;
ans[i] = (query1(l, r, 0) * spw[k - 1] % MOD) == query1(l, r, 1);
}
}
}
}
void solve2()
{
for(int i = 1; i <= n; i++)
{
a[i] = ba[i]; s[i][0][0] = s[i][0][1] = s[i][1][0] = s[i][1][1] = 0;
}
for(int i = 1; i <= n; i++)
{
add2(i, (ll)a[i] * pw[i] % MOD, 0);
}
for(int i = 1; i <= q; i++)
{
if(qr[i].op == 1)
{
int x = qr[i].x, dt = qr[i].y - a[x];
add2(x, (ll)dt * pw[x], 0);
a[x] += dt;
}
else if(qr[i].k > T)
{
int k = qr[i].k, l = qr[i].l, r = qr[i].r;
ll res = 0;
for(int j = 1; j <= n; j += k)
{
int ll = j, rr = min(j + k - 1, n);
int LL = max(l, ll), RR = min(r, rr);
if(LL <= RR)
{
res += query2(LL, RR, 0) * inv[j] % MOD;
if(res >= MOD) res -= MOD;
}
}
ll s0 = 0;
for(int j = k; j <= n; j += k)
{
if(l <= j && j <= r)
{
s0 += a[j];
if(s0 >= MOD) s0 -= MOD;
}
}
ans[i] = (s0 * spw[k - 1] % MOD) == res;
}
}
}
int main()
{
//freopen("data.in", "r", stdin);
n = read(), m = read(), q = read();
for(int i = 1; i <= n; i++) ba[i] = a[i] = read();
for(int i = 1; i <= m; i++) b[i] = read();
init();
for(int i = 1; i <= q; i++)
{
char str[2]; scanf("%s", str);
if(str[0] == 'Q')
{
int l = read(), r = read(), x = read(), y = read();
qr[i] = Op({0, l, r, x, y, gcd(r - l + 1, query(x, y))});
}
else
{
int x = read(), y = read();
qr[i] = Op({1, 0, 0, x, y});
}
}
solve1();
solve2();
for(int i = 1; i <= q; i++)
{
if(qr[i].op == 0)
{
if(ans[i]) write1();
else write0();
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 15908kb
input:
6 4 5 1 1 4 5 1 4 3 3 2 4 Q 1 5 1 2 Q 2 5 3 4 U 5 2 Q 1 6 1 2 Q 2 5 3 4
output:
Yes No No Yes
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 4ms
memory: 18116kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: -100
Time Limit Exceeded
input:
2000 2000 200000 1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...