12
28
2015
2

[bzoj]4373: 算术天才⑨与等差数列

-->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...

Category: bzoj | Tags: hash gcd 线段树 | Read Count: 4000
Avatar_small
NCERT Computer Scien 说:
2022年9月26日 14:05

NCERT have introdused computer education from the foundation of the education, and they have designed Secondary Level 9th Standard sample paper with study & learning material for Term1 & Term2 Exams such as SA1, NCERT Computer Science Question Paper 2023 Class 11 SA2, FA1, FA2, FA4, and Assignment exams. Everyone can download and study to get complete strucher of the question paper style for Paper-1 & Paper-2 exams.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com