QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#1297 | #824572 | #9774. Same Sum | ship2077 | ucup-team3510 | Success! | 2024-12-23 09:13:11 | 2024-12-23 09:13:11 |
详细
Extra Test:
Wrong Answer
time: 88ms
memory: 7752kb
input:
516 1 14175 16185 23242 146398 20603 18258 24518 136621 17000 18699 8657 155644 5800 2672 22589 168939 5966 1943 18016 174075 6990 24521 21424 147065 19192 23961 23404 133443 6912 14605 4481 174002 12504 24116 23330 140050 9847 16664 4552 168937 11443 11850 4039 172668 3625 19813 16794 159768 2200 2...
output:
YES
result:
wrong answer expected NO, found YES [1st token]
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#824572 | #9774. Same Sum | ucup-team3510# | WA | 861ms | 44680kb | C++20 | 3.6kb | 2024-12-21 14:44:44 | 2024-12-23 09:15:29 |
answer
#include<iostream>
using namespace std;
inline int qpow(int a,long long b,int mod)
{
int ret=1;
while(b)
{
if(b&1)
{
ret=(long long)
ret*a%mod;
}
a=(long long)
a*a%mod,b>>=1;
}
return ret;
}
struct Tree
{
int mod,B,P[200010],invp[200010];
inline int add(int x,int y)
{
x+=y;
return x<mod?x:x-mod;
}
inline void init(int Mod,int base)
{
mod=Mod,B=base;
for(int i=P[0]=invp[0]=1;i<=2e5;i++)
{
P[i]=(long long)P[i-1]*B%mod;
invp[i]=qpow(P[i],mod-2,mod);
}
}
struct tree
{
int mul1,mul2,sum1,sum2;
long long add,sum;
};
tree a[800000];
inline void update(int p)
{
a[p].sum=a[p<<1].sum+a[(p<<1)|1].sum;
a[p].sum1=add(a[p<<1].sum1,a[(p<<1)|1].sum1);
a[p].sum2=add(a[p<<1].sum2,a[(p<<1)|1].sum2);
}
inline void add(int p,int l,int r,long long v)
{
a[p].sum+=(r-l+1)*v,a[p].add+=v;
}
inline void Add1(int p,int v)
{
a[p].sum1=(long long)a[p].sum1*v%mod;
a[p].mul1=(long long)a[p].mul1*v%mod;
}
inline void Add2(int p,int v)
{
a[p].sum2=(long long)a[p].sum2*v%mod;
a[p].mul2=(long long)a[p].mul2*v%mod;
}
inline void pushdown(int l,int mid,int r,int p)
{
add(p<<1,l,mid,a[p].add);
add((p<<1)|1,mid+1,r,a[p].add);
Add1(p<<1,a[p].mul1);
Add1((p<<1)|1,a[p].mul1);
Add2(p<<1,a[p].mul2);
Add2((p<<1)|1,a[p].mul2);
a[p].add=0,a[p].mul1=a[p].mul2=1;
}
void change(int l,int r,int ll,int rr,int v,int p)
{
if(r<ll||l>rr)
{
return;
}
if(ll<=l&&r<=rr)
{
add(p,l,r,v);
Add1(p,P[v]);
Add2(p,invp[v]);
return;
}
int mid=l+r>>1;
pushdown(l,mid,r,p);
change(l,mid,ll,rr,v,p<<1);
change(mid+1,r,ll,rr,v,(p<<1)|1);
update(p);
}
long long query(int l,int r,int ll,int rr,int p)
{
if(r<ll||l>rr)
{
return 0;
}
if(ll<=l&&r<=rr)
{
return a[p].sum;
}
int mid=l+r>>1;
pushdown(l,mid,r,p);
return query(l,mid,ll,rr,p<<1)
+query(mid+1,r,ll,rr,(p<<1)|1);
}
int query1(int l,int r,int ll,int rr,int p)
{
if(r<ll||l>rr)
{
return 0;
}
if(ll<=l&&r<=rr)
{
return a[p].sum1;
}
int mid=l+r>>1;
pushdown(l,mid,r,p);
return add(query1(l,mid,ll,rr,p<<1)
,query1(mid+1,r,ll,rr,(p<<1)|1));
}
int query2(int l,int r,int ll,int rr,int p)
{
if(r<ll||l>rr)
{
return 0;
}
if(ll<=l&&r<=rr)
{
return a[p].sum2;
}
int mid=l+r>>1;
pushdown(l,mid,r,p);
return add(query2(l,mid,ll,rr,p<<1)
,query2(mid+1,r,ll,rr,(p<<1)|1));
}
void build(int l,int r,int p,int *v)
{
a[p].add=0,a[p].mul1=a[p].mul2=1;
if(l==r)
{
a[p].sum=v[l];
a[p].sum1=P[v[l]];
a[p].sum2=invp[v[l]];
return;
}
int mid=l+r>>1;
build(l,mid,p<<1,v);
build(mid+1,r,(p<<1)|1,v);
update(p);
}
};
const int mod1=1e9+7,mod2=1e9+9;
const int base1=131,base2=233;
Tree T1,T2;
int n,m,A[200010];
inline bool judge(Tree &T,int l,int r,long long k)
{
int sum1=T.query1(1,n,l,r,1);
int sum2=T.query2(1,n,l,r,1);
return sum1==(long long)
qpow(T.B,k,T.mod)*sum2%T.mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>A[i];
}
T1.init(mod1,base1);
T1.build(1,n,1,A);
T2.init(mod2,base2);
T2.build(1,n,1,A);
while(m--)
{
int op,l,r;
cin>>op>>l>>r;
if(op==1)
{
int v;
cin>>v;
T1.change(1,n,l,r,v,1);
T2.change(1,n,l,r,v,1);
}
else
{
long long sum=T1.query(1,n,l,r,1);
int len=r-l+1>>1;
if(sum%len)
{
cout<<"NO\n";
continue;
}
long long k=sum/len;
cout<<((judge(T1,l,r,k)&&
judge(T2,l,r,k))?"YES":"NO")<<'\n';
}
}
return 0;
}