QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#858874 | #9774. Same Sum | baoyangawa | TL | 7ms | 99692kb | C++14 | 3.9kb | 2025-01-17 08:16:16 | 2025-01-17 08:16:28 |
Judging History
answer
#include <bits/stdc++.h>
#define frr(a) freopen(a, "r", stdin)
#define fww(a) freopen(a, "w", stdout)
#define MP make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
using ll = long long;
const int inf = 0x3f3f3f3f, MB = 1 << 20;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct fio {
char ib[MB + 100], *p, *q;
fio() {
p = q = ib;
}
char gc() {
return getchar();
if (p == q) {
q = (p = ib) + fread(ib, 1, MB, stdin);
if (p == q) return EOF;
}
return *p++;
}
template <typename T> void read(T& x) {
char c = gc(), l = 0;
x = 0;
while (!isdigit(c)) l = c, c = gc();
while ( isdigit(c)) x = (x << 1) + (x << 3) + c - 48, c = gc();
if (l == '-') x = -x;
}
bool bk(char c) {
return c == ' ' || c == '\r' || c == '\n' || c == '\t' || c == EOF;
}
void read(char& x) {
char c = gc();
while (bk(c)) c = gc();
x = c;
}
void read(string& x) {
char c = gc();
x.clear();
while ( bk(c)) c = gc();
while (!bk(c)) x += c, c = gc();
}
template <typename T1, typename T2> void read(pair <T1, T2> &x) {
read(x.fi), read(x.se);
}
template <typename T, typename ...Argc> void read(T& x, Argc&... argc) {
read(x), read(argc...);
}
template <typename T> void readt(T bg, T ed) {
for (T it = bg; it != ed; it++) {
read(*it);
}
}
} IO;
const int N = 2e5 + 10;
int n, q;
ll a[N];
ll qpow(ll a, ll n, ll mod) {
ll res = 1; n = (n % (mod - 1) + mod - 1) % (mod - 1);
while (n) {
if (n & 1) res = res * a % mod;
a = a * a % mod, n >>= 1;
} return res;
}
struct seg {
ll mod, B;
struct node {
ll V, I, mx, mn, ad;
node (ll a = 0, ll b = 0, ll c = -INF, ll d = INF, ll e = 0) {
V = a, I = b, mx = c, mn = d, ad = e;
}
} tr[4 * N];
node merge(node a, node b) {
return node((a.V + b.V) % mod, (a.I + b.I) % mod, max(a.mx, b.mx), min(a.mn, b.mn), 0);
}
void pushup(int x) {
tr[x] = merge(tr[x << 1], tr[x << 1 | 1]);
}
void pushadd(int x, ll v) {
tr[x].ad += v, tr[x].mx += v, tr[x].mn += v;
tr[x].V = tr[x].V * qpow(B, v, mod) % mod, tr[x].I = tr[x].I * qpow(B, -v, mod) % mod;
}
void pushdown(int x) {
ll &ad = tr[x].ad;
if (ad) pushadd(x << 1, ad), pushadd(x << 1 | 1, ad), ad = 0;
}
void build(int x = 1, int L = 1, int R = n) {
if (L == R) {
tr[x] = node(qpow(B, a[L], mod), qpow(B, -a[L], mod), a[L], a[L], 0);
return;
} int mid = (L + R) >> 1;
build(x << 1, L, mid), build(x << 1 | 1, mid + 1, R);
pushup(x);
}
void add(int l, int r, int v, int x = 1, int L = 1, int R = n) {
if (l <= L && R <= r) return pushadd(x, v);
pushdown(x); int mid = (L + R) >> 1;
if (l <= mid) add(l, r, v, x << 1, L, mid);
if (mid < r) add(l, r, v, x << 1 | 1, mid + 1, R);
pushup(x);
}
node query(int l, int r, int x = 1, int L = 1, int R = n) {
if (l <= L && R <= r) return tr[x];
pushdown(x); int mid = (L + R) >> 1; node res;
if (l <= mid) res = merge(res, query(l, r, x << 1, L, mid));
if (mid < r) res = merge(res, query(l, r, x << 1 | 1, mid + 1, R));
return res;
}
bool check(int l, int r) {
node res = query(l, r);
ll val = res.I * qpow(B, res.mx + res.mn, mod) % mod;
return val == res.V;
}
void init(ll x, ll y) {
mod = x, B = y;
build();
}
} T1, T2, T3;
void build() {
T1.init(1e9 + 7, 131), T2.init(1e9 + 9, 13331);
// T3.init(998244353, 47);
}
void change(int l, int r, int v) {
T1.add(l, r, v), T2.add(l, r, v);
// T3.add(l, r, v);
}
bool check(int l, int r) {
return T1.check(l, r) && T2.check(l, r)/* && T3.check(l, r)*/;
}
int main() {
IO.read(n, q), IO.readt(a + 1, a + n + 1);
build();
while (q--) {
int op, l, r; IO.read(op, l, r);
if (op == 1) {
int v; IO.read(v);
change(l, r, v);
} else {
check(l, r) ? puts("YES") : puts("NO");
}
}
return 0;
}
/*
8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8
*/
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 99692kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Time Limit Exceeded
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...