此博客停更

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373

强制在线。。只能想到数据结构-。-

标算表示想不到-。-||| %Claris

我的做法是，用线段树维护区间最小值，区间哈希值，哈希采用平方和的方法(from 比利)，对于一个知道了首项和公差的等差数列，其数列

$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$

然后。。

笑而不语。。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 300300
#define ll long long
const ll mo=1000000007ll;
int i,j,k,m,n,x,y,a[N],last,L,R,X,V;ll ans;
struct tree{int mn;ll v;}T[N<<2];
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define min(a,b) ((a)<(b)?(a):(b))
inline void Mn(int&a,int b){if(b<a)a=b;}
#define up(k) (T[k].mn=min(T[k<<1].mn,T[k<<1|1].mn),T[k].v=(T[k<<1].v+T[k<<1|1].v)%mo)
void build(int k,int l,int r){
	if(l==r){T[k].mn=a[l],T[k].v=1ll*a[l]*a[l]%mo;return;}
	int m=l+r>>1;
	build(lson),build(rson),up(k);
}
void change(int k,int l,int r){
	if(l==r){T[k].mn=V,T[k].v=1ll*V*V%mo;return;}
	int m=l+r>>1;
	X<=m?change(lson):change(rson);up(k);
}
void ask(int k,int l,int r){
	if(l>=L&&r<=R){(ans+=T[k].v)%=mo;return;}
	int m=l+r>>1;
	if(L<=m)ask(lson);
	if(R>m)ask(rson);
}
int _ask(int k,int l,int r){
	if(l>=L&&r<=R)return T[k].mn;
	int m=l+r>>1,ans=0x7f7f7f7f;
	if(L<=m)Mn(ans,_ask(lson));
	if(R>m)Mn(ans,_ask(rson));
	return ans;
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)a[i]=read();
	for(build(1,1,n);m--;){
		int op=read();
		if(op==1)X=read()^last,V=read()^last,change(1,1,n);
		else{
			L=read()^last,R=read()^last,k=read()^last;
			ans=0,ask(1,1,n);int o=_ask(1,1,n),len=R-L+1;
			ll Ans=(1ll*len*o%mo*((len-1)*k+o)%mo+1ll*len*(len-1)*(2*len-1)/6%mo*k%mo*k%mo)%mo;
			if(ans==Ans)puts("Yes"),++last;
			else puts("No");
		}
	}
}

loading...