QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #290391 | #7782. Ursa Minor | ucup-team2307 | WA | 1042ms | 12872kb | C++20 | 6.7kb | 2023-12-24 22:30:57 | 2023-12-24 22:30:57 |
Judging History
answer
#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
const ll inf = 1ll<<30;
struct Seg {
int n;
vector<int> tr;
Seg(int N) : n(N), tr(2*N) {}
void upd(int pos, int val) {
for(tr[pos+=n]=val;pos/=2;)
tr[pos] = __gcd(tr[2*pos], tr[2*pos+1]);
}
int qry(int l, int r) {
int res = 0;
for(l += n, r += n; l < r; l>>=1,r>>=1) {
if(l & 1) res = __gcd(res, tr[l++]);
if(r & 1) res = __gcd(res, tr[--r]);
}
return res;
}
};
const int C = 128, mod = 998244853;
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a + mod - b : a - b; }
int mul(int a, int b) { return a*1ll*b%mod; }
struct RSQ1 {//cosnt update root query
int n;
vector<int> a, b;
RSQ1(int N = 0) : n(N), a(n), b(n / C + 1) {}
void update(int pos, int val) {
b[pos / C] = sub(b[pos / C], a[pos]);
b[pos / C] = add(b[pos / C], a[pos] = val);
}
int qry(int l, int r) {
++r;
int ans = 0;
while(l < r) {
if(l % C == 0 && l + C <= r) {
ans = add(ans, b[l / C]);
l += C;
} else {
ans = add(ans, a[l++]);
}
}
return ans;
}
};
struct RSQ2 {//root update const query
int n;
vector<int> a, b, c;
RSQ2(int N = 0) : n(N), a(n), b(n/C+1), c(n) {}
void update(int pos, int val) {
for(int i = pos / C + 1; i < b.size(); i++) {
b[i] = sub(b[i], a[pos]);
b[i] = add(b[i], val);
}
int lim = min((pos / C) * C + C, n);
for(int i = pos; i < lim; i++) {
c[i] = sub(c[i], a[pos]);
c[i] = add(c[i], val);
}
a[pos] = val;
}
int qry(int r) {
if(r < 0) return 0;
int bl = r / C;
return add(b[bl], c[r]);
}
int qry(int l, int r) { return sub(qry(r), qry(l - 1)); }
};
mt19937 rng(123);//!!
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
// {
// int n = 20;
// RSQ1 a(n);
// RSQ2 b(n);
// for(int i = 0; i < n; i++) {
// a.update(i, i); b.update(i, i);
// }
// // cout << b.c[1] << b.b[0] << " " << b.qry(0, 1) << endl;
// for(int i = 0; i < n; i++) {
// for(int j = i; j < n; j++) {
// int x = a.qry(i, j), y = b.qry(i, j);
// // cout << i << " " << j << " " << x << " " << y << endl;
// assert(x == y);
// assert(x == j*(j+1)/2 - i*(i-1) / 2);
// }
// }
// return 0;
// }
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n);
for(auto &i : a) cin >> i;
vector<int> b(m);
for(auto &i : b) cin >> i;
Seg gst(m);
for(int i = 0; i < m; i++) {
gst.upd(i, b[i]);
}
vector<array<int, 5>> queries;
vector<int> ans(q, 1);
for(int I = 0; I < q; I++) {
char type;
cin >> type;
if(type == 'Q') {
int l, r, s, t;
cin >> l >> r >> s >> t;
queries.push_back({0, l, r, s, t});
} else {
ans[I] = -1;
int p, v;
cin >> p >> v;
queries.push_back({1, p, v, 0, 0});
}
}
//hash stuff
auto solve = [=, &ans](int x) mutable -> void {
vector<int> pws(2*n + 1, 1);
for(int i = 1; i <= 2*n; i++) pws[i] = pws[i - 1] * 1ll * x % mod;
auto suf = pws;
suf.back() = 0;
for(int i = 2*n; i--;) suf[i] = add(suf[i], suf[i + 1]);
vector<RSQ1> small(C);
for(int i = 1; i < C; i++) {
small[i] = RSQ1(n);
for(int j = 0; j < n; j++) {
small[i].update(j, a[j] * 1ll * pws[j % i] % mod);
}
}
// cout << small[3].qry(0, 5) << " " << a[0] * pws[0] <<endl;
RSQ2 r2(n);
RSQ2 S(n);
for(int i = 0; i < n; i++) {
r2.update(i, a[i] * 1ll * pws[i] % mod);
S.update(i, a[i]);
}
int ID = -1;
int out = 0;
for(auto Q : queries) { ++ID;
if(Q[0] == 0) {
auto [_, l, r, s, t] = Q;
int G = gst.qry(--s, t);
G = __gcd(G, r-- - --l);
if(++out == 376) {
cout << l << "_" << r << "_" << s << "_" << t << "_" << G << endl;
for(int i = l; i <= r; i++) cout << a[i] << " "; cout << endl;
}
// vector<int> sm(G);
// for(int i = l; i < r; i++) {
// sm[i % G] += a[i];
// }
int sum = 0;
int real_sum = S.qry(l, r);
if(G < C) {
sum = small[G].qry(l, r);
sum = mul(sum, pws[2*n - G]);
} else {
while(l + G - 1 <= r) {
sum = add(sum, mul(r2.qry(l, l + G - 1), pws[(2*n - G) - l]));
l += G;
}
// cout << sum << endl;
int P = 2*n - G;
while(l <= r) {
sum = add(sum, mul(r2.a[l], pws[P - l]));
l++, P++;
}
}
int div = suf[2*n - G];
ans[ID] &= mul(sum, G) == mul(div, real_sum);
// cout << G << " " << x << " : " << l << " " << r << " " << sum << " " << div << " " << (real_sum) << " " << ID<< endl;
// for(auto i : sm) cout << i << " "; cout << endl;
// int ok = *min_element(all(sm)) == *max_element(all(sm));
// cout << (ok?"Yes\n":"No\n");
} else {
auto [_, p, v, __, ___] = Q;
// a[--p] = v;
--p;
for(int i = 1; i < C; i++) {
small[i].update(p, mul(v, pws[p % i]));
}
r2.update(p, mul(v, pws[p]));
S.update(p, v);
a[p] = v;
}
}
};
solve(10);
// return 0;
solve(rng() % (mod - 1) + 1);
solve(rng() % (mod - 1) + 1);
// solve(rng() % (mod - 1) + 1);
for(auto i : ans) if(i >= 0) cout << (i ? "Yes" : "No") << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
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: 1ms
memory: 3464kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: -100
Wrong Answer
time: 1042ms
memory: 12872kb
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:
76_79_3_4_4 2 2 2 2 76_79_3_4_4 2 2 2 1 76_79_3_4_4 2 2 2 1 Yes Yes No Yes Yes No No No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No Yes Yes No No No No No Yes No No No Yes Yes No Yes No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes No Yes Yes Yes No No Yes No Yes...
result:
wrong answer 1st words differ - expected: 'Yes', found: '76_79_3_4_4'