QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1302 | #827225 | #9774. Same Sum | ship2077 | TJUHuangTao | Success! | 2024-12-23 09:57:51 | 2024-12-23 09:57:52 |
詳細信息
Extra Test:
Wrong Answer
time: 1ms
memory: 5980kb
input:
516 1 19880 11583 24563 143974 13998 19560 4946 161496 788 17549 10796 170867 3127 22383 19641 154849 4949 5405 12570 177076 16164 14239 15785 153812 20820 10913 7778 160489 3432 15965 7345 173258 4949 5405 12570 177076 18576 10700 24075 146649 2135 16582 13069 168214 20482 19807 5117 154594 20596 2...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#827225 | #9774. Same Sum | TJUHuangTao | WA | 761ms | 57904kb | C++23 | 3.7kb | 2024-12-22 20:33:13 | 2024-12-23 10:07:07 |
answer
#include <bits/stdc++.h>
#define int __int128_t
#define ll __int128_t
#define db double
#define pii pair<int, int>
using namespace std;
const int maxn = 2e5 + 10;
const int mod = (long long)1e18 + 201, base = 2333;
long long arr[maxn];
int ksm(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * a % mod)
if (b & 1)
res = res * a % mod;
return res;
}
struct Node {
ll laz1 = 0, laz2 = 0, laz3 = 0, sum = 0, pos = 0, neg = 0;
};
struct SEG {
#define ls rt << 1
#define rs rt << 1 | 1
#define mid ((l + r) >> 1)
Node t[maxn << 2];
void push_up(int rt) {
t[rt].sum = t[ls].sum + t[rs].sum;
t[rt].pos = (t[ls].pos + t[rs].pos) % mod;
t[rt].neg = (t[ls].neg + t[rs].neg) % mod;
}
void fun(int rt, int l, int r, int k, int pos, int neg) {
t[rt].sum += (r - l + 1) * k;
t[rt].pos = (t[rt].pos * pos) % mod;
t[rt].neg = (t[rt].neg * neg) % mod;
t[rt].laz1 += k;
t[rt].laz2 = t[rt].laz2 * pos % mod;
t[rt].laz3 = t[rt].laz3 * neg % mod;
}
void push_down(int rt, int l, int r) {
if (t[rt].laz1) {
fun(ls, l, mid, t[rt].laz1, t[rt].laz2, t[rt].laz3);
fun(rs, mid + 1, r, t[rt].laz1, t[rt].laz2, t[rt].laz3);
t[rt].laz1 = 0;
t[rt].laz2 = t[rt].laz3 = 1;
}
}
void build(int rt, int l, int r) {
t[rt].laz2 = t[rt].laz3 = 1;
if (l == r) {
t[rt].sum = arr[l];
t[rt].pos = ksm(base, arr[l]);
t[rt].neg = ksm(ksm(base, arr[l]), mod - 2);
return;
}
build(ls, l, mid), build(rs, mid + 1, r);
push_up(rt);
}
void update(int rt, int l, int r, int p, int q, int k, int pos, int neg) {
if (p > r || q < l)
return;
if (p <= l && r <= q) {
fun(rt, l, r, k, pos, neg);
return;
}
push_down(rt, l, r);
update(ls, l, mid, p, q, k, pos, neg),
update(rs, mid + 1, r, p, q, k, pos, neg);
push_up(rt);
}
Node query(int rt, int l, int r, int p, int q) {
if (p <= l && r <= q)
return t[rt];
push_down(rt, l, r);
if (q <= mid)
return query(ls, l, mid, p, q);
if (p > mid)
return query(rs, mid + 1, r, p, q);
Node left = query(ls, l, mid, p, mid),
right = query(rs, mid + 1, r, mid + 1, q);
Node res;
res.pos = (left.pos + right.pos) % mod;
res.neg = (left.neg + right.neg) % mod;
res.sum = (left.sum + right.sum);
return res;
}
} seg;
void solve() {
long long n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> arr[i]; //, arr[i] *= 2;
seg.build(1, 1, n);
while (q--) {
long long op;
cin >> op;
if (op == 1) {
long long l, r, v;
cin >> l >> r >> v;
// v *= 2;
seg.update(1, 1, n, l, r, v, ksm(base, v),
ksm(ksm(base, v), mod - 2));
} else {
long long l, r;
cin >> l >> r;
Node tem = seg.query(1, 1, n, l, r);
if (tem.sum % ((r - l + 1) / 2)) {
cout << "NO\n";
continue;
}
int avg = 2 * tem.sum / (r - l + 1);
if (tem.neg * ksm(base, avg) % mod == tem.pos % mod)
cout << "YES\n";
else
cout << "NO\n";
}
}
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--)
solve();
}