QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340704#7782. Ursa MinorgoodierTL 4ms18116kbC++176.0kb2024-02-29 11:28:052024-02-29 11:28:06

Judging History

你现在查看的是最新测评结果

  • [2024-02-29 11:28:06]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:18116kb
  • [2024-02-29 11:28:05]
  • 提交

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...

output:


result: