QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#427332 | #7782. Ursa Minor | marher | WA | 1365ms | 58520kb | C++14 | 3.5kb | 2024-06-01 12:46:13 | 2024-06-01 12:46:14 |
Judging History
answer
#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+50,mod=1e9+7,S=500;
mt19937 rad(time(0));
int n,m,q,st[N][20],a[N],b[N],lg[N],x=rad()%mod,fir[N],mi[N],bl[N],imi[N],ix,sum[N],t[S][S+50];
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;a=a*a%mod;
}
return ans;
}
int find(int l,int r)
{
int k=lg[r-l+1];
return __gcd(st[l][k],st[r-(1<<k)+1][k]);
}
void ad(int&x,int y)
{
x+=y;
x-=x>=mod?mod:0;
}
struct block
{
int sum[S+50],k,val[S+50];
void change(int x,int ad)
{
sum[bl[x]]=(sum[bl[x]]+ad*mi[x%k]%mod)%mod;
if(x%k==0)val[bl[x]]=(val[bl[x]]+ad)%mod;
}
void init()
{
for(int i=1;i<=n;i++)change(i,a[i]);
}
int w(int x)
{
return a[x]*mi[x%k]%mod;
}
int find(int l,int r)
{
int ans=0;
for(int i=l;i<=min(bl[l]*S,r);i++)ad(ans,w(i));
if(r<=bl[l]*S)return ans;
for(int i=bl[l]+1;i<bl[r];i++)ad(ans,sum[i]);
for(int i=r;i>(bl[r]-1)*S;i--)ad(ans,w(i));
return ans;
}
int finds(int l,int r)
{
int ans=0;
for(int i=l;i<=min(bl[l]*S,r);i++)if(i%k==0)ad(ans,w(i));
if(r<=bl[l]*S)return ans;
for(int i=bl[l]+1;i<bl[r];i++)ad(ans,val[i]);
for(int i=r;i>(bl[r]-1)*S;i--)if(i%k==0)ad(ans,w(i));
return ans;
}
}B[S+50];
void rebuild(int p)
{
int l=(p-1)*S+1,r=min(n,p*S);sum[p]=0;
for(int i=l;i<=r;i++)t[p][i-l+1]=(t[p][i-l]+a[i]*mi[i]%mod)%mod,ad(sum[p],a[i]*mi[i]%mod);
}
int findsum(int l,int r)
{
int p=bl[l],L=(p-1)*S+1,LL=(bl[r]-1)*S+1;
if(bl[l]==bl[r])return (t[p][r-L+1]-t[p][l-L]+mod)%mod;
int ans=0;
ad(ans,(t[p][S]-t[p][l-L]+mod)%mod);
ad(ans,t[bl[r]][r-LL+1]);
for(int i=bl[l]+1;i<bl[r];i++)ad(ans,sum[i]);
return ans;
}
signed main()
{
// freopen("root.in","r",stdin);
// freopen("out.txt","w",stdout);
cin>>n>>m>>q;lg[0]=-1;mi[0]=fir[0]=imi[0]=1;ix=ksm(x,mod-2);
for(int i=1;i<=n;i++)cin>>a[i],mi[i]=mi[i-1]*x%mod,fir[i]=(fir[i-1]+mi[i])%mod,imi[i]=imi[i-1]*ix%mod;
for(int i=1;i<=m;i++)cin>>b[i],st[i][0]=b[i],lg[i]=lg[i>>1]+1;
for(int i=1;(1<<i)<=m;i++)for(int j=1;j+(1<<i)-1<=m;j++)st[j][i]=__gcd(st[j][i-1],st[j+(1<<i-1)][i-1]);
for(int i=1;i<=n;i++)bl[i]=(i-1)/S+1;
for(int i=1;i<=S;i++)B[i].k=i,B[i].init(),rebuild(i);
int cc=0;
while(q--)
{
char z;cin>>z;
if(z=='U')
{
int pos,x;
cin>>pos>>x;
for(int i=1;i<=S;i++)B[i].change(pos,(mod+x-a[pos])%mod);
a[pos]=x;rebuild(bl[pos]);
continue;
}
int l1,l2,r1,r2;
cin>>l1>>r1>>l2>>r2;
cc++;
int k=__gcd(r1-l1+1,find(l2,r2));
// if(cc==1043&&n==2e5)
// {
// cout<<k<<'\n';
// }
if(k<=S)
{
if(B[k].find(l1,r1)==B[k].finds(l1,r1)*fir[k-1]%mod)puts("Yes");
else puts("No");
continue;
}
int sa=0,sb=0;
for(int t=1;(t-1)*k<=n;t++)
{
int l=max(l1,(t-1)*k),r=min(r1,t*k-1);
if(l<=r)
{
ad(sa,find(l,r)*imi[(t-1)*k]%mod);
if(l==(t-1)*k)ad(sb,a[l]);
}
}
if(sa==sb*fir[k-1]%mod)puts("Yes");
else puts("No");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 26376kb
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: 0ms
memory: 26316kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 590ms
memory: 26564kb
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:
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 No No No Yes Yes Yes Yes Yes Yes Yes Yes Yes No Yes Yes Yes No...
result:
ok 100554 tokens
Test #4:
score: 0
Accepted
time: 455ms
memory: 52344kb
input:
1 200000 200000 998244353 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes ...
result:
ok 100240 tokens
Test #5:
score: 0
Accepted
time: 420ms
memory: 42648kb
input:
6 131072 200000 0 0 0 0 1000000000 1000000000 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...
output:
Yes Yes Yes No No No Yes No No No No No Yes Yes No Yes No Yes Yes Yes No No No No No No No Yes No No No Yes Yes Yes Yes Yes Yes Yes Yes No No No No Yes Yes No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No Yes No No No No No No Yes Yes No Yes N...
result:
ok 100021 tokens
Test #6:
score: -100
Wrong Answer
time: 1365ms
memory: 58520kb
input:
200000 200000 200000 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...
output:
No No No No No No No No No No No No No No Yes No No No Yes No No No No No No No No No No No No No No Yes No No No No No Yes Yes Yes No No No No No No No No Yes No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No Yes No Yes Yes No No No No No No No No N...
result:
wrong answer 1043rd words differ - expected: 'Yes', found: 'No'