Reincarnation

正因为梦易碎，才格外美好。

P3792 由乃与大母神原型和偶像崇拜

发表于 更新于 分类于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

好巧妙！

题目介绍

题目来源：洛谷月赛
评测链接：https://www.luogu.com.cn/problem/P3792

形式化题意：给定一个长度为 的序列 ，两个操作：

  2. 查询区间 是否可以重排为值域上连续的一段。

数据范围：

虽然我不知道为什么 的范围不一样。

考虑到如果 为值域上连续的一段，设为 那么我们求出区间和为 ，这是显然的，但这样并不能保证为连续一段，因为会出现 的情况，题目背景里也有所提及，所以我们需要另外一个数值来帮我们判断——平方和。

考虑对于每一个区间记录： 表示该区间的极值，区间和，区间平方和。通过极值计算这个区间如果满足条件情况下的区间和与区间平方和，用等差数列公式和平方和公式即可。

注意会爆 long long ，而且使用平方和公式时的 /6 会导致未知错误，所以考虑选取一个恰当的模数修改为逆元。也可以试试靠 int128 。

AC Code
 
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
// ----- Eternally question-----
// Problem: P3792 由乃与大母神原型和偶像崇拜
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3792
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-30 11:23:53
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10,MAXS=2.5e7+10;
const int INF=0x3f3f3f3f;
const ll Mod=1e9+7;
int N,Q;
ll Val[MAXN];
#define ls (p<<1)
#define rs (p<<1|1)
struct ST
{
	int l,r,mx,mn;
	ll sum,squ;
}Tr[MAXN<<2];
struct Node
{
	int l,r;
	ll val,sum;
	Node(int l=0,int r=0,ll val=0,ll sum=0):l(l),r(r),val(val),sum(sum){}
	inline void upDate(int ql,int qr,ll qv,ll qs)
	{
		checkMin(l,ql),checkMax(r,qr);
		val+=qv,sum+=qs;
	}
	inline void upDate(Node arc)
	{
		checkMin(l,arc.l),checkMax(r,arc.r);
		val+=arc.val,sum=(sum+arc.sum)%Mod;
	}
};
inline void pushUp(int p)
{
	Tr[p].sum=Tr[ls].sum+Tr[rs].sum;
	Tr[p].squ=(Tr[ls].squ+Tr[rs].squ)%Mod;
	Tr[p].mx=std::max(Tr[ls].mx,Tr[rs].mx);
	Tr[p].mn=std::min(Tr[ls].mn,Tr[rs].mn);
}
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].sum=Tr[p].mx=Tr[p].mn=Val[l],Tr[p].squ=Val[l]*Val[l]%Mod,void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyX(int p,int x,int v)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].mx=Tr[p].mn=Tr[p].sum=v,Tr[p].squ=1ll*v*v%Mod,void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	if(x<=mid) modifyX(ls,x,v);
	else modifyX(rs,x,v);
	pushUp(p);
}
Node querySeg(int p,int l,int r)
{
	if(l<=Tr[p].l&&Tr[p].r<=r) return Node(Tr[p].mn,Tr[p].mx,Tr[p].sum,Tr[p].squ);
	int mid=(Tr[p].l+Tr[p].r)>>1;Node res(INF,-INF,0,0);
	if(l<=mid) res.upDate(querySeg(ls,l,r));
	if(mid<r) res.upDate(querySeg(rs,l,r));
	return res;
}
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%Mod;
		a=a*a%Mod;b>>=1;
	}
	return res;
}
ll Inv2,Inv6;
inline ll ansSqu(int v)
{
	return 1ll*v*(v+1)%Mod*(2*v+1)%Mod*Inv6%Mod;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,Q);
	Inv2=qPow(2,Mod-2),Inv6=qPow(6,Mod-2);
	for(int i=1;i<=N;++i) read(Val[i]);
	build(1,1,N);
	for(int opt,ql,qr;Q--;)
	{
		read(opt,ql,qr);
		if(opt==1) modifyX(1,ql,qr);
		else
		{
			bool flag=0;
			Node res=querySeg(1,ql,qr);
			if(1ll*(res.l+res.r)*(res.r-res.l+1)%Mod*Inv2%Mod!=res.val%Mod) flag=1;
			if((ansSqu(res.r)-ansSqu(res.l-1)+Mod)%Mod!=(res.sum+Mod)%Mod) flag=1;
			puts(flag?"yuanxing":"damushen");
		}
	}
	return 0;
}
/*

*/
相关文章