重新用树状数组写了一遍,但是WA的很惨,似乎都是应该输出YES的地方输出了NO,球球大佬们帮忙改错:
#include<stdio.h>
#define lowbit(x) x&-x
#define inf 1000000000
const int maxn=1000005;
const long long Base=65537,mod=100000000003;
int i,j,k,m,n;
long long pow[maxn],a[maxn],sum[maxn][3];
inline int read(){
int x=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())
x=x*10+c-48;
return x;
}
void update(int x,long long v,int t){
for(int i=x;i<=n;i+=lowbit(i)){
sum[i][t]+=v;
if(t==2)
sum[i][t]%=mod;
}
}
long long query(int x,int t){
if(x==0)
return 0;
long long res=0;
for(int i=x;i;i-=lowbit(i)){
res+=sum[i][t];
if(t==2)
res%=mod;
}
return res;
}
int main(){
pow[0]=1;
for(i=1;i<maxn;i++)
pow[i]=pow[i-1]*Base%mod;
n=read(),m=read();
for(i=1;i<=n;i++){
a[i]=read();
update(i,a[i],1);
update(i,pow[a[i]],2);
}
for(i=1;i<=m;i++){
int opt,x,y,l1,r1,l2,r2,flg,len;
long long sum1,sum2,pow1,pow2;
opt=read();
if(opt==0){
x=read(),y=read();
update(x,-a[x],1),update(x,-pow[a[x]],2);
a[x]=y;
update(x,a[x],1),update(x,pow[a[x]],2);
}
if(opt==1){
l1=read(),r1=read(),l2=read(),r2=read();
len=r1-l1+1;
sum1=query(r1,1)-query(l1-1,1),sum2=query(r2,1)-query(l2-1,1);
if((sum1-sum2)%len)
flg=0;
else{
pow1=(query(r1,2)-query(l1-1,2)+mod)%mod;
pow2=(query(r2,2)-query(l2-1,2)+mod)%mod;
if(sum1<sum2)
flg=(pow1*pow[(sum2-sum1)/len]%mod==pow2);
else flg=(pow2*pow[(sum1-sum2)/len]%mod==pow1);
}
if(flg==1)
puts("YES");
else puts("NO");
}
}
return 0;
}