QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314646 | #7782. Ursa Minor | Delay_for_five_minutes | WA | 0ms | 24264kb | C++20 | 5.9kb | 2024-01-26 01:55:09 | 2024-01-26 01:55:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n , m , q;
const int bs = 7797;
const int mod = (1<<31)-1;
int a[200005] ;
int st[20][200005];
int qry(int l,int r) {
int k = __lg(r - l + 1) ;
return __gcd(st[k][l] , st[k][r - (1<<k) + 1]) ;
}
int pw[200005] , prep[200005];
struct ST1 {
int pr[505] ; //前缀和
int block[200005]; // 所属块
int pre[505][505] ;///每块前缀和
int L[505] , R[505];
int a[200005];
int B;
void init() {
for(int i = 1;i <= n;i++) {
block[i] = block[i - 1];
if(B == 1 || i % B == 1) {
block[i]++ ;
R[block[i - 1]] = i - 1;
L[block[i]] = i;
}
}
R[block[n]] = n ;
for(int i = 1;i <= block[n];i++) {
for(int j = L[i] ; j <= R[i] ;j++) {
pre[i][j - L[i] + 1] = (pre[i][j - L[i]] + a[j]) % mod;
}
pr[i] = (pr[i - 1] + pre[i][R[i] - L[i] + 1]) % mod;
}
}
void upd(int pos,int v) {
a[pos] = v;
int i = block[pos] ;
for(int j = pos ; j <= R[i] ;j++) {
pre[i][j - L[i] + 1] = (pre[i][j - L[i]] + a[j]) % mod;
}
for(int j = i ; j <= block[n];j++) pr[j] = (pr[j - 1] + pre[j][R[j] - L[j] + 1]) % mod;
}
int qry(int l,int r) {
int bl = block[l] , br = block[r] ;
if(bl == br) {
return (pre[bl][r - L[bl] + 1] - pre[bl][l - L[bl]] + mod ) % mod;
}
return ((pre[br][r - L[br] + 1] - pre[bl][l - L[bl]]
+ pr[br - 1] - pr[bl - 1])%mod + mod ) % mod;
}
}s1;
struct ST2 {
int a[200005];
int pr[505];
int B;
void init() {
int cnt = 0;
for(int i = 1;i <= n;i++) {
if(i % B == 1 || B == 1) ++cnt;
pr[cnt] = (pr[cnt] + a[i]) % mod;
}
}
void upd(int pos,int v) {
int id = (pos - 1) / B + 1;
pr[id] = ((ll)pr[id] - a[pos] + v + mod) % mod;
a[pos] = v;
return ;
}
int qry(int l,int r) {
int idl = (l - 1) / B + 1 , idr = (r - 1) / B + 1;
if(idl == idr) {
int ans = 0;
for(int j = l;j <= r;j++) ans = (ans + a[j]) % mod;
return ans;
}
int ans = 0;
if(l > idl * B - B/2) {
for(int j = l;j <= idl*B;j++) ans = (ans + a[j]) % mod;
}
else {
ans = (ans + pr[idl]) % mod;
for(int j = (idl-1)*B + 1 ; j < l;j++) ans = (ans - a[j]) % mod;
ans = (ans + mod) % mod;
}
if(r > idr*B - B/2) {
ans = (ans + pr[idr]) % mod;
for(int j = r + 1;j <= idr*B;j++) ans = (ans - a[j]) % mod;
ans = (ans + mod) % mod;
}
else{
for(int j = (idr-1)*B + 1 ; j <= r;j++) ans = (ans + a[j]) % mod;
}
for(int j = idl + 1; j <= idr - 1;j++) ans = (ans + pr[j]) % mod;
return ans;
}
}S[450];
void solv()
{
cin >> n >> m >> q;
pw[0] = 1; prep[0] = 1;
for(int i = 1;i <= n;i++) {pw[i] = 1LL * pw[i - 1] * bs % mod; prep[i] = (prep[i - 1] + pw[i]) % mod;}
for(int i = 1;i <= n;i++) {cin >> a[i] ;}
for(int i = 1;i <= m;i++) {
cin >> st[0][i] ;
}
for(int i = 1;i <= 19;i++) {
for(int j = 1;j <= m;j++) {
if(j + (1 << i - 1) <= m) st[i][j] = __gcd(st[i - 1][j] , st[i - 1][j + (1 << i - 1)]) ;
else st[i][j] = st[i - 1][j] ;
}
}
s1.B = sqrt(n) ;
int B = sqrt(n) ;
for(int i = 1;i <= n;i++) s1.a[i] = 1LL * pw[n - i] * a[i] % mod;
s1.init() ;
for(int k = 1;k <= B;k++) {
S[k].B = sqrt(n);
for(int i = 1;i <= n;i++) {
S[k].a[i] = 1LL * a[i] * pw[i % k] % mod;
if(i % k == 0) S[k].a[i] = (S[k].a[i] - 1LL * a[i] * prep[k - 1]%mod + mod) % mod;
}
S[k].init() ;
}
// puts("ojbk") ;
int n0 = 0 , n1 = 0 , n2 = 0;
for(int x= 1;x <= q;x++){
char op ; cin >> op ;
if(op == 'Q') {
int l , r , s , t;
cin >> l >> r >> s >> t;
int k = __gcd(r - l + 1 , qry(s , t)) ;
if(k > B) {
n0++;
int sum = 0;
int s0 = 0 , ql = l, qr = l + k - 1;
for(int i = 0 ; i < (r - l + 1) / k ; i++) {
sum = (sum + 1LL * s1.qry(ql, qr) * pw[i * k]) % mod;
s0 = (s0 + a[ql]) % mod;
ql += k ; qr += k;
}
if(l + k <= n) s0 = 1LL * s0 * (prep[n - l] - prep[n - l - k] + mod) % mod;
else s0 = 1LL * s0 * prep[n - l] % mod;
if(s0 == sum) cout << "Yes\n" ;
else cout << "No\n" ;
}
else {
n1++;
int sum = S[k].qry(l , r);
if(sum == 0) cout << "Yes\n";
else cout << "No\n" ;
}
}
else {
n2++;
int u , v ; cin >> u >> v;
a[u] = v;
s1.upd(u , 1LL * a[u] * pw[n - u] % mod) ;
// puts("ojbk??") ;
for(int k = 1;k <= B;k++) {
int val = 1LL * a[u] * pw[u % k] % mod;
if(u % k == 0) val = (val - 1LL * a[u] * prep[k - 1]%mod + mod) % mod;
S[k].upd(u , val);
}
// puts("ojbk") ;
}
}
return;
}
int main()
{
// freopen("in.txt","r",stdin) ;
// freopen("out.txt","w",stdout) ;
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
int T = 1;
clock_t st = clock() ;
while(T--) solv();
// cerr << (double)(clock()- st) / CLOCKS_PER_SEC << '\n' ;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 24264kb
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 No
result:
wrong answer 4th words differ - expected: 'Yes', found: 'No'