QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1296#824535#9774. Same Sumship2077ucup-team4474Success!2024-12-22 18:51:582024-12-22 18:51:59

詳細信息

Extra Test:

Wrong Answer
time: 42ms
memory: 22688kb

input:

200000 1
1989 4673 5022 68316 9289 5943 5568 59200 9038 4151 6342 60469 6573 8957 5225 59245 3468 5640 3177 67715 155 35 2418 77392 1419 5988 7830 64763 7888 5652 5497 60963 3737 3996 2460 69807 4814 9670 7016 58500 1523 4091 6597 67789 5239 8965 3674 62122 7283 5884 9109 57724 6178 3743 1650 68429 ...

output:

YES

result:

wrong answer expected NO, found YES [1st token]

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#824535#9774. Same Sumucup-team4474#WA 1383ms23536kbC++205.7kb2024-12-21 14:34:392024-12-22 18:57:25

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128_t;

bool Memory_begin;

template <int mod>
unsigned int down(unsigned int x)
{
    return x >= mod ? x - mod : x;
}
template <int mod>
struct Modint
{
    unsigned int x;
    Modint() = default;
    Modint(unsigned int x) : x(x) {}
    friend istream &operator>>(istream &in, Modint &a) { return in >> a.x; }
    friend ostream &operator<<(ostream &out, Modint a) { return out << a.x; }
    friend Modint operator+(Modint a, Modint b) { return down<mod>(a.x + b.x); }
    friend Modint operator-(Modint a, Modint b) { return down<mod>(a.x - b.x + mod); }
    friend Modint operator*(Modint a, Modint b) { return 1ULL * a.x * b.x % mod; }
    friend Modint operator/(Modint a, Modint b) { return a * ~b; }
    friend Modint operator^(Modint a, i64 b)
    {
        Modint ans = 1;
        for (; b; b >>= 1, a *= a)
            if (b & 1)
                ans *= a;
        return ans;
    }
    friend Modint operator~(Modint a) { return a ^ (mod - 2); }
    friend Modint operator-(Modint a) { return down<mod>(mod - a.x); }
    friend Modint &operator+=(Modint &a, Modint b) { return a = a + b; }
    friend Modint &operator-=(Modint &a, Modint b) { return a = a - b; }
    friend Modint &operator*=(Modint &a, Modint b) { return a = a * b; }
    friend Modint &operator/=(Modint &a, Modint b) { return a = a / b; }
    friend Modint &operator^=(Modint &a, i64 b) { return a = a ^ b; }
    friend Modint &operator++(Modint &a) { return a += 1; }
    friend Modint operator++(Modint &a, int)
    {
        Modint x = a;
        a += 1;
        return x;
    }
    friend Modint &operator--(Modint &a) { return a -= 1; }
    friend Modint operator--(Modint &a, int)
    {
        Modint x = a;
        a -= 1;
        return x;
    }
    friend bool operator==(Modint a, Modint b) { return a.x == b.x; }
    friend bool operator!=(Modint a, Modint b) { return !(a == b); }
};
const int mod = 998244353;
typedef Modint<mod> mint;

const mint base = 91, e = 1;
const int N = 2e5 + 5;
int n, q, a[N];
struct node
{
    mint tag;
    mint sum1, sum2;
    i64 tag0, sum0;
} st[N << 2];
void build(int cur, int l, int r)
{
    st[cur].tag = e;
    if (l == r)
    {
        st[cur].sum0 = a[l];
        st[cur].sum1 = base ^ a[l];
        st[cur].sum2 = e / st[cur].sum1;
        return;
    }
    int mid = l + r >> 1;
    build(cur << 1, l, mid);
    build(cur << 1 | 1, mid + 1, r);
    st[cur].sum1 = st[cur << 1].sum1 + st[cur << 1 | 1].sum1;
    st[cur].sum2 = st[cur << 1].sum2 + st[cur << 1 | 1].sum2;
    st[cur].sum0 = st[cur << 1].sum0 + st[cur << 1 | 1].sum0;
}
void pushdown(int cur, int l, int mid, int r)
{
    if (st[cur].tag == e)
        return;
    st[cur << 1].tag *= st[cur].tag;
    st[cur << 1].sum1 *= st[cur].tag;
    st[cur << 1].sum2 /= st[cur].tag;
    st[cur << 1].tag0 += st[cur].tag0;
    st[cur << 1].sum0 += 1ll * (mid - l + 1) * st[cur].tag0;
    st[cur << 1 | 1].tag *= st[cur].tag;
    st[cur << 1 | 1].sum1 *= st[cur].tag;
    st[cur << 1 | 1].sum2 /= st[cur].tag;
    st[cur << 1 | 1].tag0 += st[cur].tag0;
    st[cur << 1 | 1].sum0 += 1ll * (r - mid) * st[cur].tag0;
    st[cur].tag = e, st[cur].tag0 = 0;
}
void update(int cur, int l, int r, int a, int b, int x)
{
    if (a <= l and r <= b)
    {
        st[cur].tag0 += x;
        st[cur].sum0 += 1ll * x * (r - l + 1);
        mint tmp = base ^ x;
        st[cur].tag *= tmp;
        st[cur].sum1 *= tmp;
        st[cur].sum2 /= tmp;
        return;
    }
    int mid = l + r >> 1;
    pushdown(cur, l, mid, r);
    if (a <= mid)
        update(cur << 1, l, mid, a, b, x);
    if (b > mid)
        update(cur << 1 | 1, mid + 1, r, a, b, x);
    st[cur].sum1 = st[cur << 1].sum1 + st[cur << 1 | 1].sum1;
    st[cur].sum2 = st[cur << 1].sum2 + st[cur << 1 | 1].sum2;
    st[cur].sum0 = st[cur << 1].sum0 + st[cur << 1 | 1].sum0;
}
pair<mint, mint> query(int cur, int l, int r, int a, int b)
{
    if (a <= l and r <= b)
        return {st[cur].sum1, st[cur].sum2};
    if (a > r or b < l)
        return {mint(0), mint(0)};
    int mid = l + r >> 1;
    pushdown(cur, l, mid, r);
    auto lft = query(cur << 1, l, mid, a, b);
    auto rht = query(cur << 1 | 1, mid + 1, r, a, b);
    return {lft.first + rht.first, lft.second + rht.second};
}
i64 query1(int cur, int l, int r, int a, int b)
{
    if (a <= l and r <= b)
        return st[cur].sum0;
    if (a > r or b < l)
        return 0;
    int mid = l + r >> 1;
    pushdown(cur, l, mid, r);
    return query1(cur << 1, l, mid, a, b) + query1(cur << 1 | 1, mid + 1, r, a, b);
}

bool Memory_end;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cerr << (&Memory_end - &Memory_begin) / 1048576.0 << "MB" << '\n';

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    while (q--)
    {
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            int l, r, x;
            cin >> l >> r >> x;
            update(1, 1, n, l, r, x);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            i64 s = query1(1, 1, n, l, r) * 2;
            bool ans = false;
            if (s % (r - l + 1) == 0)
            {
                s /= r - l + 1;
                auto tmp = query(1, 1, n, l, r);
                tmp.second *= base ^ s;
                if (tmp.first == tmp.second)
                    ans = true;
            }
            if (ans)
                cout << "YES\n";
            else
                cout << "NO\n";
        }
    }
}
/*
 */