BZOJ

# Solution

• 根据给定的 $a_1,d,len$，可以在 $O(1)$或 $O(\log n)$的级别上出解
• 与顺序无关
• 满足区间加法

$S^2=\sum_{i=1}^n (a_i-\overline{a})^2=\sum_{i=1}^n (a_i^2-2\overline{a}a_i+\overline{a}^2)$

# Code

#include <algorithm>
#include <cstdio>
#define rg register
using namespace std;
typedef long long ll;
const int maxn=300010,INF=0x3f3f3f3f,mod=1000000007,inv=500000004,inv6=166666668;
template <typename Tp> inline void read(Tp &x)
{
x=0;char ch=getchar();int f=0;
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
if(f) x=-x;
}
inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x<y?x+mod-y:x-y;}
struct infor{
int a2,a,mn;
infor operator + (const infor &t)const{
return (infor){pls(a2,t.a2),pls(a,t.a),min(mn,t.mn)};
}
}fir;
int n,m,cnt,op,x,y,k,mn[maxn<<2],a[maxn<<2],a2[maxn<<2],sum[maxn];
void pushup(int rt)
{
a[rt]=pls(a[rt<<1],a[rt<<1|1]);
a2[rt]=pls(a2[rt<<1],a2[rt<<1|1]);
mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
int m=(l+r)>>1;
build(l,m,rt<<1);build(m+1,r,rt<<1|1);
pushup(rt);
}
void update(int l,int r,int pos,int val,int rt)
{
if(l==r){mn[rt]=a[rt]=val;a2[rt]=(ll)val*val%mod;return ;}
int m=(l+r)>>1;
if(pos<=m) update(l,m,pos,val,rt<<1);
else update(m+1,r,pos,val,rt<<1|1);
pushup(rt);
}
infor query(int l,int r,int L,int R,int rt)
{
if(L<=l&&r<=R) return (infor){a2[rt],a[rt],mn[rt]};
int m=(l+r)>>1;infor res;res.a2=0ll;res.a=0;res.mn=INF;
if(L<=m) res=res+query(l,m,L,R,rt<<1);
if(m<R) res=res+query(m+1,r,L,R,rt<<1|1);
return res;
}
int getfc(int len,int a1,int d)
{
if(len&1)
{
len>>=1;
return (ll)d*d%mod*2%mod*len%mod*(len+1)%mod*(len<<1|1)%mod*inv6%mod;
}
else return (ll)d*d%mod*sum[len>>1]%mod*inv%mod;
}
int power(int x,int y)
{
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1)
res=(ll)res*x%mod;
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
build(1,n,1);
for(rg int i=1;i<=n;i++) sum[i]=pls(sum[i-1],(ll)(i+i-1)*(i+i-1)%mod);
while(m--)
{
x^=cnt;y^=cnt;
if(op==1){y%=mod;update(1,n,x,y,1);}
else
{
if(x>y) swap(x,y);
fir=query(1,n,x,y,1);
int fc=getfc(y-x+1,fir.mn,k),mid,tmp=0;
mid=(ll)fir.a*power(y-x+1,mod-2)%mod;
tmp=pls(dec(fir.a2,(ll)mid*2%mod*fir.a%mod),(ll)(y-x+1)*mid%mod*mid%mod);
if(tmp==fc) puts("Yes"),cnt++;
else puts("No");
}
}
return 0;
}