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

Posted on | Views:

线段树 + $hash$ 乱搞.

可以考虑用线段树维护区间的最小值,最大值.

若是等差数列,根据最小/大值,公差可以算出长度,区间元素和,区间元素平方和,区间元素立方和,后两个自然溢出.

在线段树中把这些信息也维护进去,然后查询区间的这些要素,看一下是否符合预期结果即可.

立方和不判似乎也可以过.这东西应该挺难卡的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read()
{
	int out=0,sgn=1;
	char jp=getchar();
	while(jp!='-' && (jp<'0' || jp>'9'))
		jp=getchar();
	if(jp=='-')
		sgn=-1,jp=getchar();
	while(jp>='0' && jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*sgn;
}
const int MAXN=3e5+10;
const int P=1e9+7;
ull cube(ull x)
{
	return x*x*x;
}
ull S1(ull x)
{
	return x*(x+1)/2;
}
ull S2(ull x)
{
	return x*(x+1)*(2*x+1)/6;
}
ull S3(ull x)
{
	return S1(x)*S1(x);
}
const ull U=1;
int n,m,tot=0,a[MAXN];
struct SegTree
{
	struct node
	{
		int minv,maxv;
		ll sum1;
		ull sum2,sum3;
		friend node operator + (node lson,node rson)
		{
			node root;
			root.minv=min(lson.minv,rson.minv);
			root.maxv=max(lson.maxv,rson.maxv);
			root.sum1=lson.sum1+rson.sum1;
			root.sum2=lson.sum2+rson.sum2;
			root.sum3=lson.sum3+rson.sum3;
			return root;
		}
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root=lson+rson;
	}
	void BuildTree(int o,int l,int r)
	{
		if(l==r)
		{
			root=(node){a[l],a[l],a[l],U*a[l]*a[l],cube(a[l])};
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		pushup(o);
	}
	void upd(int o,int l,int r,int pos,int c)
	{
		if(l==r)
		{
			root=(node){c,c,c,U*c*c,cube(c)};
			return;
		}
		int mid=(l+r)>>1;
		if(pos<=mid)
			upd(o<<1,l,mid,pos,c);
		else
			upd(o<<1|1,mid+1,r,pos,c);
		pushup(o);
	}
	node query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root;
		int mid=(l+r)>>1;
		if(R<=mid)
			return query(o<<1,l,mid,L,R);
		if(L>mid)
			return query(o<<1|1,mid+1,r,L,R);
		return query(o<<1,l,mid,L,R)+query(o<<1|1,mid+1,r,L,R);
	}
	bool check(int L,int R,int k)
	{
		node tmp=query(1,1,n,L,R);
		ull len=R-L+1;
		if((tmp.maxv-tmp.minv)!=(len-1)*k)
			return false;
		ll expsum1=len*(tmp.minv+tmp.maxv)/2;
		if(expsum1!=tmp.sum1)
			return false;
		ull b=tmp.minv-k;
		ull expsum2=len*b*b;
		expsum2+=k*b*(len+1)*len;
		expsum2+=k*k*S2(len);
		if(expsum2!=tmp.sum2)
			return false;
		ull expsum3=cube(k)*S3(len);
		expsum3+=U*3*k*k*b*S2(len);
		expsum3+=U*3*k*b*b*S1(len);
		expsum3+=len*cube(b);
		if(expsum3!=tmp.sum3)
			return false;
		return true;
	}
}T;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	T.BuildTree(1,1,n);
	while(m--)
	{
		int op=read();
		if(op==1)
		{
			int x=read()^tot,y=read()^tot;
			T.upd(1,1,n,x,y);
		}
		else
		{
			int L=read()^tot,R=read()^tot,k=read()^tot;
			if(T.check(L,R,k))
			{
				puts("Yes");
				++tot;
			}
			else
				puts("No");
		}
	}
	return 0;
}