Ynoi做题记录

我回来了，纵使日薄西山，此时此刻的余晖，盼君勿忘。

「望月悲叹最初分块」

题目简介

题目名称：未来日记
题目来源：

评测链接：https://www.luogu.com.cn/problem/P4119

形式化题意：给定一个长度为 的序列 以及 次操作：

• 将 中所有 变为 。
• 求 区间第 小值。

数据范围：

时空限制：

考虑分块。

首先不考虑修改，静态区间第 小的做法就是可持久化线段树上二分，但显然主席树不适合带修，所以这个做法可以直接略过。

首先考虑怎么用分块维护区间 小值，我们让每一块有序，首先二分答案，然后查 std::lower_bound 的个数，然后枚举散块，判断答案是否为 ，这样的时间复杂度为 。优化的话可以把散块归并为一个整块使用 std::lower_bound，可以优化到 。但还是得考虑怎么把那个 给优化掉，所以考虑用值域分块代替二分。

令 表示第 个数列块，第 个值域块中值的个数， 表示第 个数列块中 的个数。可以 预处理。同理处理 分别表示散块中值域块 值的个数以及 的个数，用在处理左右散块。

对于查询，我们首先通过 确定第 小所在值域块，然后用类似的方法枚举 求出第 小，时间复杂度 ，散块可以直接使用 std::nth_element，时间复杂度也是 。

然后考虑修改，维护 ，用于存储修改后的真实值，考虑维护权值并查集，每次将 的根合并到 上，而 表示序列块 中并查集根 对应的值， 表示序列中 对应的根。有 ，其中 表示块编号。那 就是 的真实值了。

考虑查询时需要 的前缀形式，我们在修改的时候先差分回去，对块内独立维护，再合并回去，时间复杂度 ，并不在计算瓶颈上。然后考虑散块，我们利用并查集的维护，直接根据 对 进行重构并计算 即可。

整块的修改可以分为下面三种情况：

• 没有 ，无需修改。
• 有 无 ，那么我们把所有有关 的信息移植给 即可。
• 有 有 ，合并 的并查集，将 指向 并合并有关信息。序列中出现的不同值只有 ，所以势能分析下暴力均摊 ，所以可以直接做。

时间复杂度 ，空间也差不多。

AC Code

// ----- Eternally question-----
// Problem: P4119 [Ynoi2018] 未来日记
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4119
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-08-21 15:20:58
// ----- 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){ putchar(x?'1':'0'); }
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=1e5+10,MAXB=350;
const int S=1e5;
int N,Q,val[MAXN];
int Uni,Tot,Bel[MAXN];
int Lst[MAXB],Rst[MAXB];
int Cnt1[MAXB],Sum1[MAXB][MAXB];
int Cnt2[MAXN],Sum2[MAXB][MAXN];
int Rt[MAXB][MAXN],Vl[MAXB][MAXN],Pos[MAXN];
inline void recover(int x)
{ for(int i=Lst[x];i<=Rst[x];++i) val[i]=Vl[x][Pos[i]]; }
inline void build(int x)
{
	int cur=0;
	for(int i=1;i<=Uni;++i) Rt[x][Vl[x][i]]=0;
	for(int i=Lst[x];i<=Rst[x];++i)
	{
		if(!Rt[x][val[i]])
		{
			++cur;
			Rt[x][val[i]]=cur;
			Vl[x][cur]=val[i];
		}
		Pos[i]=Rt[x][val[i]];
	}
}
inline void upDate(int l,int r,int x,int y)
{
	for(int i=l;i<=r;++i)
		if(val[i]==x)
		{
			--Sum1[Bel[i]][Bel[x]];
			++Sum1[Bel[i]][Bel[y]];
			--Sum2[Bel[i]][x],++Sum2[Bel[i]][y];
			val[i]=y;
		}
}
inline void merge(int x,int p,int q)
{
	Rt[x][q]=Rt[x][p];
	Vl[x][Rt[x][p]]=q;
	Rt[x][p]=0;
}
inline void modifyRep(int l,int r,int x,int y)
{
	if((x==y)||(Sum2[Bel[r]][x]-Sum2[Bel[l]-1][x]==0)) return ;
	for(int i=Bel[N];i>=Bel[l];--i)
	{
		Sum1[i][Bel[x]]-=Sum1[i-1][Bel[x]];
		Sum1[i][Bel[y]]-=Sum1[i-1][Bel[y]];
		Sum2[i][x]-=Sum2[i-1][x],Sum2[i][y]-=Sum2[i-1][y];
	}
	if(Bel[l]==Bel[r])
	{
		recover(Bel[l]);
		upDate(l,r,x,y);
		build(Bel[l]);
	}
	else
	{
		recover(Bel[l]),upDate(l,Rst[Bel[l]],x,y),build(Bel[l]);
		recover(Bel[r]),upDate(Lst[Bel[r]],r,x,y),build(Bel[r]);
		for(int i=Bel[l]+1;i<=Bel[r]-1;++i)
		{
			if(!Sum2[i][x]) continue;
			else if(Sum2[i][y])
			{
				recover(i);
				upDate(Lst[i],Rst[i],x,y);
				build(i);
			}
			else
			{
				Sum1[i][Bel[y]]+=Sum2[i][x],
				Sum1[i][Bel[x]]-=Sum2[i][x];
				Sum2[i][y]+=Sum2[i][x];Sum2[i][x]=0;
				merge(i,x,y);
			}
		}
	}
	for(int i=Bel[l];i<=Bel[N];++i)
	{
		Sum1[i][Bel[x]]+=Sum1[i-1][Bel[x]],
		Sum1[i][Bel[y]]+=Sum1[i-1][Bel[y]];
		Sum2[i][x]+=Sum2[i-1][x],Sum2[i][y]+=Sum2[i-1][y];
	}
}
inline int queryKth(int l,int r,int k)
{
	int ans=0,sum=0;
	if(Bel[l]==Bel[r])
	{
		recover(Bel[l]);
		for(int i=l;i<=r;++i) Cnt2[i]=val[i];
		std::nth_element(Cnt2+l,Cnt2+l+k-1,Cnt2+r+1);
		ans=Cnt2[l+k-1];
		for(int i=l;i<=r;++i) Cnt2[i]=0;
		return ans;
	}
	recover(Bel[l]),recover(Bel[r]);
	for(int i=l;i<=Rst[Bel[l]];++i) ++Cnt1[Bel[val[i]]],++Cnt2[val[i]];
	for(int i=Lst[Bel[r]];i<=r;++i) ++Cnt1[Bel[val[i]]],++Cnt2[val[i]];
	for(int i=1;i<=Bel[S];++i)
	{
		if((sum+Cnt1[i]+Sum1[Bel[r]-1][i]-Sum1[Bel[l]][i])>=k)
		{
			for(int j=(i-1)*Uni+1;j<=i*Uni;++j)
			{
				if((sum+Cnt2[j]+Sum2[Bel[r]-1][j]-Sum2[Bel[l]][j])>=k)
				{
					for(int k=l;k<=Rst[Bel[l]];++k) --Cnt1[Bel[val[k]]],--Cnt2[val[k]];
					for(int k=Lst[Bel[r]];k<=r;++k) --Cnt1[Bel[val[k]]],--Cnt2[val[k]];
					return j;
				}
				else sum+=(Cnt2[j]+Sum2[Bel[r]-1][j]-Sum2[Bel[l]][j]);
			}
		}
		else sum+=(Cnt1[i]+Sum1[Bel[r]-1][i]-Sum1[Bel[l]][i]);
	}
	return ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	Uni=std::sqrt(N);
	Tot=std::ceil(1.0*N/Uni);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=1;i<=MAXN-10;++i) Bel[i]=(i-1)/Uni+1;
	for(int i=1;i<=Tot;++i) Lst[i]=Rst[i-1]+1,Rst[i]=i*Uni;
	Rst[Tot]=N;
	for(int i=1;i<=Tot;++i) build(i);
	for(int i=1;i<=Tot;++i)
	{
		for(int j=1;j<=MAXB-10;++j) Sum1[i][j]=Sum1[i-1][j];
		for(int j=1;j<=MAXN-10;++j) Sum2[i][j]=Sum2[i-1][j];
		for(int l=Lst[i];l<=Rst[i];++l) ++Sum1[i][Bel[val[l]]],++Sum2[i][val[l]];
	}
	for(int opt,l,r,x,y,k;Q--;)
	{
		read(opt,l,r);
		if(opt==1) read(x,y),modifyRep(l,r,x,y);
		else read(k),write(queryKth(l,r,k),'\n');
	}
	return 0;
}
/*

*/

---

「突刺贯穿第二分块」

题目简介

题目名称：五彩斑斓的世界
题目来源：

评测链接:https://www.luogu.com.cn/problem/P4117

形式化题意：给定一个长度为 的序列 以及 次操作：

• 将 内满足 的 减去 ；
• 求 中 出现的次数。

数据范围：

时空限制：

能够看出这不一般的时空限制。

首先势能分析一波，记 为全局最大值，显然 只减不增，所以极差一直减小，这或许是均摊复杂度的一个关键。

1. 如果 ，那么我们可以直接对 暴力减。
2. 如果 ，那么我们对 暴力加，然后对区间打上减 的标记。

于是，我们保证每次修改至多会修改 个元素（这里是值域范围内的）。所以每次操作的时间复杂度为 ，而操作一个块的复杂度就是 ，所以总时间复杂度 。如果常数小，这个方法已经可以通过了。

然后考虑实操，我们在最初分块中用到过一个技巧，那就是通过并查集反映值域的变化，显然在第二分块中我们也可以使用这个技巧来维护上述操作：

1. 当 时，我们将 向 合并；
2. 当 时，我们将 向 合并，并对区间打上减 的标记。

似乎这个操作也是可以用链表维护的，但显然没有并查集方便好写，况且 也写的并查集，万一会被卡常呢。合并操作 ，可以近似看作常数。

但这样实现会被空间限制，所以我们需要将空间优化到线性，考虑块间修改查询独立，所以我们离线操作后分块单独做，每次只需要处理当前块的操作，均摊时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P4117 [Ynoi2018] 五彩斑斓的世界
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4117
// Memory Limit: 64 MB
// Time Limit: 7500 ms
// Written by: Eternity
// Time: 2023-08-21 20:15:12
// ----- 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){ putchar(x?'1':'0'); }
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 MAXB=1e3+10,MAXN=1e6+10;
const int S=5e5;
int N,Q,val[MAXN];
struct Query
{ int opt,ql,qr,qx; }Qry[MAXN];
int Bel[MAXN],Lst[MAXB],Rst[MAXB],Uni,Tot;
int Fa[MAXN],Rt[MAXN],Pos[MAXN],Siz[MAXN];
int mxval,tag,ans[MAXN];
inline int getFa(int x){ return Fa[x]==x?x:Fa[x]=getFa(Fa[x]); }
inline void merge(int u,int v)
{
	if(Rt[v]) Fa[Rt[u]]=Rt[v];
	else Rt[v]=Rt[u],Pos[Rt[v]]=v;
	Siz[v]+=Siz[u];Rt[u]=Siz[u]=0;
}
inline void init()
{
	Uni=std::sqrt(N);
	Tot=(N-1)/Uni+1;
	for(int i=1;i<=Tot;++i) Lst[i]=Rst[i-1]+1,Rst[i]=i*Uni;
	Rst[Tot]=N;
}
inline void build(int x)
{
	mxval=tag=0;
	for(int i=Lst[x];i<=Rst[x];++i)
	{
		checkMax(mxval,val[i]);
		if(Rt[val[i]]) Fa[i]=Rt[val[i]];
		else Rt[val[i]]=Fa[i]=i,Pos[i]=val[i];
		++Siz[val[i]];
	}
}
inline void rebuild(int x,int l,int r,int qx)
{
	for(int i=Lst[x];i<=Rst[x];++i) val[i]=Pos[getFa(i)],Rt[val[i]]=Siz[val[i]]=0,val[i]-=tag;
	for(int i=Lst[x];i<=Rst[x];++i) Pos[i]=0;
	checkMax(l,Lst[x]),checkMin(r,Rst[x]);
	for(int i=l;i<=r;++i) val[i]=val[i]-(val[i]>qx)*qx;
	build(x);
}
inline void modifyRed(int qx)
{
	if((qx<<1)<=mxval-tag)
	{
		for(int i=tag+1;i<=tag+qx;++i) if(Rt[i]) merge(i,i+qx);
		tag+=qx;
	}
	else
	{
		for(int i=tag+qx+1;i<=mxval;++i) if(Rt[i]) merge(i,i-qx);
		if(tag+qx<mxval) mxval=tag+qx;
	}
}
inline void queryCnt(int x,int id)
{
	int l=Qry[id].ql,r=Qry[id].qr,qx=Qry[id].qx;
	if(qx+tag>S) return ;
	if(l<=Lst[x]&&Rst[x]<=r) ans[id]+=Siz[qx+tag];
	else
	{
		checkMax(l,Lst[x]),checkMin(r,Rst[x]);
		for(int i=l;i<=r;++i) if(Pos[getFa(i)]-tag==qx) ++ans[id];
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);init();
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=1;i<=Q;++i) read(Qry[i].opt,Qry[i].ql,Qry[i].qr,Qry[i].qx);
	for(int i=1;i<=Tot;++i)
	{
		for(int l=0;l<=mxval;++l) Rt[l]=Siz[l]=0;
		build(i);
		for(int j=1;j<=Q;++j)
		{
			if(Lst[i]>Qry[j].qr||Rst[i]<Qry[j].ql) continue;
			else if(Qry[j].opt==1)
			{
				if(Qry[j].ql<=Lst[i]&&Rst[i]<=Qry[j].qr) modifyRed(Qry[j].qx);
				else rebuild(i,Qry[j].ql,Qry[j].qr,Qry[j].qx);
			}
			else queryCnt(i,j);
		}
	}
	for(int i=1;i<=Q;++i) if(Qry[i].opt==2) write(ans[i],'\n');
	return 0;
}
/*

*/

---

「弑尽破净第四分块」

题目简介

题目名称：天降之物
题目来源：

评测链接：https://www.luogu.com.cn/problem/P5397

形式化题意：给定一个长度为 的序列 以及 次操作：

• 将序列中所有 换成 。
• 给出 ，求出 ，即 的最近距离。可能无解。

强制在线，保证 。

数据范围：

时空限制：

很熟悉的操作啊，但是不能用并查集维护了。所以这道题既不弑尽也不破净更不分块。是一个根号分治的想法，但是好像是有序列分块的做法的，有兴趣的读者可以研究研究。

我们首先考虑暴力的形式，对每一个权值记录一个集合 ，修改和查询时暴力合并两个链表，虽然在修改时可以势能分析均摊时间复杂度，但显然查询的时候是没有办法的，因为有可能有些元素的出现次数过多。

这个思路就很显然了，我们设定一个阈值 ，如果一个元素出现的次数超过了 ，我们可以通过预处理 得到贡献，因为这样的元素不会超过 个，称为超越数，记 表示第 个超越数对元素 的答案，总时间复杂度 。

需要注意的是， 与 独立，也就是 不会计算 的答案，但 ，所以暴力合并是没有问题的。

考虑对修改分类讨论：

• 如果 为非超越点，那么暴力合并 ，如果此时 ，则将 重构为超越点，这个过程不会超过 。
• 若 为非超越点， 为超越点，同样直接将 并入 ，然后依照上面的判断重构 ，时间复杂度同样是 。
• 若 皆为超越点，那直接重构 的次数不会超过 ，均摊是 。

所以修改的时间复杂度可以控制在 。

然后考虑用同样的方式分讨查询：

• 如果 皆为非超越点，那么暴力归并的时间复杂度为 ，总时间为 。
• 如果 为超越点，暴力归并后与 取 。
• 如果 为超越点，那暴力合并后对 取 。

所以查询的时间复杂度瓶颈在于暴力重构的 。所以总时间复杂度 。

平衡规划一下取 ，又有 同阶，所以我们可以在 的时间内解决所有问题。

需要注意的是，上述所有操作的前提都是 ，所以我们用 表示元素 实际对应的值，然后就可以直接 std::swap() 操作中的 和 了。

还有一些细节，重构是需要枚举两遍，一遍计算前驱一遍计算后继，然后卡常可以特判 ，以及处理无解的情况。但这样会被卡空间，因为 std::vector<int> 的 clear() 不释放空间，所以需要特殊操作，比如用一个局部变量与全局交换后在函数末尾将局部变量释放。

AC Code

// ----- Eternally question-----
// Problem: P5397 [Ynoi2018] 天降之物
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5397
// Memory Limit: 256 MB
// Time Limit: 500000 ms
// Written by: Eternity
// Time: 2023-08-22 14:54:25
// ----- 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){ putchar(x?'1':'0'); }
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=1e5+10,MAXB=1e3+10;
const int Inf=0x3f3f3f3f;
int N,Q,val[MAXN],lastans;
int Lim,Siz[MAXN],ans[MAXB][MAXN],Id[MAXN],Hash[MAXN],Tot;
std::vector<int>vec[MAXN];
inline void build(int x,int id=0)
{
	Id[x]=id?id:++Tot;
	id=Id[x];
	std::memset(ans[id],0x3f,sizeof(ans[id]));
	for(int i=1,cur=Inf;i<=N;++i)
		if(val[i]==x) cur=0;
		else checkMin(ans[id][val[i]],++cur);
	for(int i=N,cur=Inf;i;--i)
		if(val[i]==x) cur=0;
		else checkMin(ans[id][val[i]],++cur);
	std::vector<int>tmp;
	ans[id][x]=0;vec[x].swap(tmp);
}
inline void merge(int x,int y)
{
	int i=0,j=0,Sx=vec[x].size(),Sy=vec[y].size();
	std::vector<int>fre;
	while(i<Sx&&j<Sy) fre.emplace_back(vec[x][i]<vec[y][j]?vec[x][i++]:vec[y][j++]);
	while(i<Sx) fre.emplace_back(vec[x][i++]);
	while(j<Sy) fre.emplace_back(vec[y][j++]);
	vec[y]=fre;
}
inline int getMerge(int x,int y)
{
	int i=0,j=0,Sx=vec[x].size(),Sy=vec[y].size(),res=Inf;
	if(!Sx||!Sy) return Inf;
	while(i<Sx&&j<Sy) checkMin(res,vec[x][i]<vec[y][j]?vec[y][j]-vec[x][i++]:vec[x][i]-vec[y][j++]);
	if(i<Sx) checkMin(res,std::abs(vec[x][i]-vec[y][Sy-1]));
	if(j<Sy) checkMin(res,std::abs(vec[x][Sx-1]-vec[y][j]));
	return res;
}
inline int query(int x,int y)
{
	x=Hash[x],y=Hash[y];
	if(!Siz[x]||!Siz[y]) return -1;
	if(x==y) return 0;
	if(Siz[x]>Siz[y]) std::swap(x,y);
	if(Siz[y]<=Lim) return getMerge(x,y);
	else if(Siz[x]<=Lim) return std::min(ans[Id[y]][x],getMerge(x,y));
	else return std::min(getMerge(x,y),std::min(ans[Id[x]][y],ans[Id[y]][x]));
}
inline void modify(int x,int y)
{
	int _x=Hash[x],_y=Hash[y];
	if(!Siz[_x]||_x==_y) return ;
	if(Siz[_x]>Siz[_y]) Hash[y]=_x,Hash[x]=N+1,std::swap(_x,_y);
	else Hash[x]=N+1;
	if(_x>N||_y>N) return ;
	x=_x,y=_y;
	if(Siz[y]<=Lim)
	{
		if(Siz[x]+Siz[y]<=Lim)
		{
			for(int i:vec[x]) val[i]=y;
			for(int i=1;i<=Tot;++i) checkMin(ans[i][y],ans[i][x]);
			merge(x,y);
		}
		else
		{
			for(int i=1;i<=N;++i) if(val[i]==x) val[i]=y;
			build(y);
		}
	}
	else if(Siz[x]<=Lim)
	{
		if(Siz[x]+(int)vec[y].size()<=Lim)
		{
			for(int i:vec[x]) val[i]=y;
			for(int i=1;i<=Tot;++i) checkMin(ans[i][y],ans[i][x]);
			merge(x,y);
		}
		else
		{
			for(int i=1;i<=N;++i) if(val[i]==x) val[i]=y;
			build(y,Id[y]);
		}
	}
	else
	{
		for(int i=1;i<=N;++i) if(val[i]==x) val[i]=y;
		build(y,Id[y]);
	}
	std::vector<int>tmp;
	Siz[y]+=Siz[x],Siz[x]=0,vec[x].swap(tmp);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Lim=320;
	for(int i=1;i<=N;++i) read(val[i]),++Siz[val[i]],vec[val[i]].emplace_back(i),Hash[i]=i;
	for(int i=0;i<=N;++i) if(Siz[i]>Lim) build(i);
	for(int opt,qx,qy;Q--;)
	{
		read(opt,qx,qy),qx^=lastans,qy^=lastans;
		if(opt==1) modify(qx,qy);
		else
		{
			lastans=query(qx,qy);
			if(!~lastans) puts("Ikaros"),lastans=0;
			else write(lastans,'\n');
		}
	}
	return 0;
}
/*

*/

---

「深潜遁藏第六分块」

题目简介

题目名称：末日时在做什么？有没有空？可以来拯救吗？
题目来源：

评测链接：https://www.luogu.com.cn/problem/P4118

形式化题意：给定一个长度为 的序列以及 次操作：

• 对 执行 ；
• 求 的最大子段和。

数据范围：，保证任何时刻权值

我的天哪， 居然出线段树板子题了，直接把小白逛公园改改交了。然后你发现就寄完了。

这个简单想想就会发现，很可能会出现类似于 的正负交替序列，而当我们执行 后就会得到：，而之前的最大子段和为 ，之后为 ，显然 ，所以你怎么维护区间长度这肯定都不对。所以我们断言，线段树无法做区间修改最大子段和。

真的不能做吗？

可以做，时间复杂度三支还是四支 ，但在修改时仅支持区间加正数，详见洛谷某道题，这不是现在我们提及的重点，所以感兴趣的读者可自行了解。

考虑正常的最大子段和的维护方式，记录以左端点为起点的最长前缀，以右端点为终点的最大后缀，以及当前区间最大子段和，这些信息具有合并性，所以可以通过线段树做，我们分别记为 。

那么我们以几何方式表示 （ 同理），那么这是由若干个一次函数构成的一条折线，此时我们暂不考虑最值问题，仅用 表示长度为 的前缀和， 表示长度为 的后缀和。

类似于 ，你发现 的几何形式是类凸包，严谨来说 是凸函数。而对于修改操作，我们需要最大化 ，这同样是一个凸包形式，所以可以通过 二分进行实现。

然后考虑 的维护形式，与线段树维护方式相同，记录 表示长度为 的最大子段和，那么就有：

$$h(x+y)=\max\Big(\max\big(h_L(x+y),h_R(x+y)\big),f_L(x)+g_R(y)\Big)$$

从几何方式考虑，显然 也是凸函数，所以 的求法相当于是对 求闵可夫斯基和后取最大值。每次操作复杂度线性，也就是 。

于是，我们考虑维护一棵线段树，但是每个结点都以凸包形式呈现，可以用 的复杂度实现建树，而提取 的区间后，每个区间我们都需要合并凸包维护信息，所以时间复杂度 。

我们考虑分块，然后对每一块建凸包线段树进行维护，整体修改时按照上述方法维护凸包，而区间修改则需要重构线段树，整体修改 ，零散修改 ，整体查询 ，区间查询 。优化一下可以做到 。

但显然无法满足当前题目的需求，所以我们考虑优化两个较大的复杂度瓶颈，即零散修改和整体查询。

考虑零散修改的重构过于朴素，所以我们每次重构仅重构线段树涉及的子树，并打上重构标记，并对其它结点进行线性重构。对于整体修改，我们让加法标记实现标记永久化，也就是在二维平面中将凸包整体上移一些单位，在凸包内考虑标记和叠加的正比例函数。

在每一层中，会被线性重构的结点数理论 ，配合标记永久化的的等比数列求和可以做到 ，所以最终实现依然是线性。值得注意的是，这里的标记支持整数域。

我们考虑优化查询，将查询离线后逐块处理，也就是类似于线段树将所有操作分割成 个后对每一个块执行所有操作结束后扫描线下一个块。

考虑整体查询一定提取到的是线段树的根结点，而根结点的标记一定为 。所以我们考虑一个相对的关系，将所有查询按照标记升序排序，转化为只存在加正数的操作，因为逐块处理中，我们可以在任意两次等价操作中交换任意操作的顺序。所以我们可以用 处理所有询问。至于查询排序，有可以直接 的快排，如果替换成基数排序当然可以做到线性，但在数据过小时基排常数过大不如快排。

最终， 同阶，取 可以得到理论最优复杂度 。

关于卡常，可以将基数稍微取大一点，但注意时空分配均匀；至于 std::vector 可能常数略大于指针数组。需要合理分配内存，以及适当调整块长。

大概调了一段时间，发现我的代码在 取到 时速度最快。代码稍微有点长，注意分段写，分段调。

AC Code

// ----- Eternally question-----
// Problem: P4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4118
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-09-01 15:06:43
// ----- 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){ putchar(x?'1':'0'); }
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=2e5+10,MAXB=5e2+15;
const int Inf=0x3f3f3f3f,uni=510;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,Q,a[MAXN];
struct Point
{
	ll x,y;
	Point(ll _x=0,ll _y=0):x(_x),y(_y){}
	inline friend const Point operator+(const Point &a,const Point &b)
	{ return Point(a.x+b.x,a.y+b.y); }
	inline friend const Point operator-(const Point &a,const Point &b)
	{ return Point(a.x-b.x,a.y-b.y); }
	inline friend const ll operator*(const Point &a,const Point &b)
	{ return a.x*b.y-a.y*b.x; }
	inline friend const bool operator<=(const Point &a,const Point &b)
	{ return a*b>=0; }
}Pt[MAXN];
typedef Point Vector;
int pTop;
struct Convex
{
	Vector* vec;
	int mxcnt,siz;
	ll tag;
	Convex(){ mxcnt=0; }
	inline Point operator[](const int &x) const { return Point(vec[x].x,vec[x].y+tag*vec[x].x); }
	inline void insert(Point p){ checkMax(vec[p.x].y,p.y); }
	inline void push_back(Point p){ vec[siz++]=p; }
	inline void clear(int len)
	{
		vec[0]=Vector(0,0);
		for(re int i=1;i<=len;++i) vec[i]=Vector(i,-INF);
		siz=len+1;tag=0;
	}
	inline void convex()
	{
		if(siz<=2) return ;
		int top=1;
		for(re int i=2;i<siz;++i)
		{
			if(vec[i].y==-INF) continue;
			while(top>=1&&vec[top]-vec[top-1]<=vec[i]-vec[top-1]) --top;
			vec[++top]=vec[i];
		}
		siz=top+1;tag=0;
	}
	inline ll maxv(ll adv)
	{
		while(mxcnt<siz-1&&(vec[mxcnt+1].x-vec[mxcnt].x)*(tag+adv)+vec[mxcnt+1].y-vec[mxcnt].y>0) ++mxcnt;
		return vec[mxcnt].x*(tag+adv)+vec[mxcnt].y;
	}
	inline ll maxv_bs(ll adv)
	{
		int l=-1,r=siz-1;
		while(l+1<r)
		{
			int mid=(l+r)>>1;
			if((vec[mid+1].x-vec[mid].x)*(tag+adv)+vec[mid+1].y-vec[mid].y>0) l=mid;
			else r=mid;
		}
		mxcnt=r;
		return vec[r].x*(tag+adv)+vec[r].y;
	}
};
struct Node
{
	ll lx,rx,val,sum;
	Node(ll _l=0,ll _r=0,ll _v=0,ll _s=0):lx(_l),rx(_r),val(_v),sum(_s){}
	inline friend const Node operator+(const Node &a,const Node &b)
	{ return Node(	std::max(a.lx,a.sum+b.lx),
					std::max(b.rx,b.sum+a.rx),
					std::max(std::max(a.val,b.val),a.rx+b.lx),
					a.sum+b.sum); }
};
struct Segment_tree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct Segment
	{
		Convex lx,rx,ans;
		ll tag,sum;
	}Tr[MAXB<<2];
	inline void merge(Convex& c,Convex& a,Convex& b,Vector adv)
	{
		int siza=a.siz,sizb=b.siz;
		for(re int i=0;i<siza;++i) c.push_back(a[i]);
		for(re int i=0;i<sizb;++i) c.push_back(adv+b[i]);
		c.convex();
	}
	inline void mincowsky(Convex& c,Convex& a,Convex& b)
	{
		int cur1=0,cur2=0,siza=a.siz,sizb=b.siz;
		c.insert(a[0]+b[0]);
		while(cur1+1<siza&&cur2+1<sizb)
		{	
			if(a[cur1+1]-a[cur1]<=b[cur2+1]-b[cur2]) c.insert(a[cur1]+b[++cur2]);
			else c.insert(a[++cur1]+b[cur2]);
		}
		while(cur1+1<siza) c.insert(a[++cur1]+b[cur2]);
		while(cur2+1<sizb) c.insert(a[cur1]+b[++cur2]);
	}
	inline void update(int p,int l,int r)
	{
		int mid=(l+r)>>1;
		merge(Tr[p].lx,Tr[ls].lx,Tr[rs].lx,Point(mid-l+1,Tr[ls].sum));
		merge(Tr[p].rx,Tr[rs].rx,Tr[ls].rx,Point(r-mid,Tr[rs].sum));
		Tr[p].ans.clear(r-l+1);
		int siz=Tr[ls].ans.siz;
		for(re int i=0;i<siz;++i) Tr[p].ans.insert(Tr[ls].ans[i]);
		siz=Tr[rs].ans.siz;
		for(re int i=0;i<siz;++i) Tr[p].ans.insert(Tr[rs].ans[i]);
		mincowsky(Tr[p].ans,Tr[ls].rx,Tr[rs].lx);
		Tr[p].ans.convex();
		Tr[p].lx.mxcnt=Tr[p].rx.mxcnt=Tr[p].ans.mxcnt=0;
		Tr[p].sum=Tr[ls].sum+Tr[rs].sum;
	}
	inline void locate(int p,int l,int r)
	{
		Tr[p].lx.vec=Pt+pTop;pTop+=r-l+3;
		Tr[p].rx.vec=Pt+pTop;pTop+=r-l+3;
		Tr[p].ans.vec=Pt+pTop;pTop+=r-l+3;
		if(l==r) return ;
		int mid=(l+r)>>1;
		locate(ls,l,mid),locate(rs,mid+1,r);
	}
	void build(int p,int l,int r,int bel)
	{
		if(l==r)
		{
			Tr[p].lx.push_back(Point(0,0)),Tr[p].lx.push_back(Point(1,a[l+(bel-1)*uni]));
			Tr[p].rx.push_back(Point(0,0)),Tr[p].rx.push_back(Point(1,a[l+(bel-1)*uni]));
			Tr[p].ans.push_back(Point(0,0)),Tr[p].ans.push_back(Point(1,a[l+(bel-1)*uni]));
			Tr[p].sum=a[l+(bel-1)*uni];
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid,bel),build(rs,mid+1,r,bel);
		update(p,l,r);
	}
	inline void pushdown(int p,int l,int r)
	{
		if(l==r||!Tr[p].tag) return ;
		int mid=(l+r)>>1;
		Tr[ls].tag+=Tr[p].tag,Tr[rs].tag+=Tr[p].tag;
		Tr[ls].lx.tag+=Tr[p].tag,Tr[ls].rx.tag+=Tr[p].tag,Tr[ls].ans.tag+=Tr[p].tag;
		Tr[ls].sum+=(mid-l+1)*Tr[p].tag,Tr[rs].sum+=(r-mid)*Tr[p].tag;
		Tr[rs].lx.tag+=Tr[p].tag,Tr[rs].rx.tag+=Tr[p].tag,Tr[rs].ans.tag+=Tr[p].tag;
		Tr[p].tag=0;
	}
	inline void add_part(int p,int l,int r,int ql,int qr,ll v)
	{
		if(l==ql&&qr==r)
		{
			Tr[p].tag+=v,Tr[p].sum+=(r-l+1)*v;
			Tr[p].lx.tag+=v,Tr[p].rx.tag+=v,Tr[p].ans.tag+=v;
			return ;
		}
		pushdown(p,l,r);
		int mid=(l+r)>>1;
		if(mid>=qr) add_part(ls,l,mid,ql,qr,v);
		else if(mid+1<=ql) add_part(rs,mid+1,r,ql,qr,v);
		else
		{
			add_part(ls,l,mid,ql,mid,v);
			add_part(rs,mid+1,r,mid+1,qr,v);
		}
		Tr[p].lx.siz=Tr[p].rx.siz=Tr[p].ans.siz=0;
		update(p,l,r);
	}
	inline Node query_all(int l,int r,ll adv)
	{ return Node(Tr[1].lx.maxv(adv),Tr[1].rx.maxv(adv),Tr[1].ans.maxv(adv),Tr[1].sum+(r-l+1)*adv); }
	inline Node query_seg(int p,int l,int r,int ql,int qr,ll adv)
	{
		if(l==ql&&qr==r&&p==1) return query_all(ql,qr,adv);
		if(l==ql&&qr==r) return Node(	Tr[p].lx.maxv_bs(adv),Tr[p].rx.maxv_bs(adv),
										Tr[p].ans.maxv_bs(adv),Tr[p].sum+(r-l+1)*adv);
		pushdown(p,l,r);
		int mid=(l+r)>>1;
		if(mid>=qr) return query_seg(ls,l,mid,ql,qr,adv);
		else if(mid+1<=ql) return query_seg(rs,mid+1,r,ql,qr,adv);
		else return query_seg(ls,l,mid,ql,mid,adv)+query_seg(rs,mid+1,r,mid+1,qr,adv);
	}
	inline void clear(int p,int l,int r)
	{
		Tr[p].lx.siz=Tr[p].rx.siz=Tr[p].ans.siz=0;
		Tr[p].lx.mxcnt=Tr[p].rx.mxcnt=Tr[p].ans.mxcnt=0;
		Tr[p].lx.tag=Tr[p].rx.tag=Tr[p].ans.tag=0;
		Tr[p].tag=0;
		if(l==r) return ;
		int mid=(l+r)>>1;
		clear(ls,l,mid),clear(rs,mid+1,r);
	}
	#undef ls
	#undef rs
};
struct Operation
{
	int opt,l,r,id;
	ll v;
	Operation(int _o=0,int _l=0,int _r=0,int _i=0,ll _v=0):opt(_o),l(_l),r(_r),id(_i),v(_v){}
	inline bool operator<(const Operation &x) const { return v<x.v; }
};
int Lst[MAXB],Rst[MAXB],Bel[MAXN],Tot;
Node ans[MAXN];
struct Sqrt_Block
{
	Segment_tree Tr;
	int bel,n,m,cnt[256];
	Operation seq[MAXN],tmp[MAXN];
	ll mrk,val[MAXN],val_tmp[MAXN];
	inline void add_all(ll v){ mrk+=v; }
	inline void add_part(int l,int r,ll v)
	{
		if(!v) return ;
		if(l==1&&r==n) return add_all(v);
		seq[m++]=Operation(v,l,r,0,mrk);
	}
	inline void query(int l,int r,int id){ seq[m++]=Operation(0,l,r,id,mrk); }
	inline void carsort(int l,int r)
	{
		if(r-l<=1500) return std::sort(seq+l,seq+r),void();
		for(re int i=l;i<r;++i) val[i-l]=val_tmp[i-l]=seq[i].v|((1ll*i)<<35);
		for(re int i=0;i<32;i+=8)
		{
			std::memset(cnt,0,sizeof(cnt));
			for(re int j=0;j<r-l;++j) ++cnt[(val[j]>>i)&255];
			for(re int j=1;j<256;++j) cnt[j]+=cnt[j-1];
			for(re int j=r-l-1;j>=0;--j)
			{
				val_tmp[cnt[(val[j]>>i)&255]-1]=val[j];
				--cnt[(val[j]>>i)&255];
			}
			std::memcpy(val,val_tmp,(r-l+5)*sizeof(ll));
		}
		for(re int i=l;i<r;++i) tmp[i-l]=seq[i];
		for(re int i=l;i<r;++i) seq[i]=tmp[(val[i-l]>>35)-l];
	}
	inline void prefix()
	{
		ll minmrk=0;
		for(re int i=0;i<m;++i) checkMin(minmrk,seq[i].v);
		for(re int i=0;i<m;++i) seq[i].v-=minmrk;
		for(re int i=Lst[bel];i<=Rst[bel];++i) a[i]+=minmrk;
		Tr.build(1,1,n,bel);
		int lst=0;
		for(re int i=0;i<m;++i)
			if(seq[i].opt!=0)
			{
				if(i!=lst) carsort(lst,i);
				lst=i+1;
			}
		if(lst!=m) carsort(lst,m);
	}
	inline void solve()
	{
		for(re int i=0;i<m;++i)
			if(seq[i].opt==0)
			{
				if(i&&seq[i-1].opt)
				{
					Tr.Tr[1].lx.maxv_bs(seq[i].v),
					Tr.Tr[1].rx.maxv_bs(seq[i].v),
					Tr.Tr[1].ans.maxv_bs(seq[i].v);
				}
				Node tmp=Tr.query_seg(1,1,n,seq[i].l,seq[i].r,seq[i].v);
				ans[seq[i].id]=ans[seq[i].id]+tmp;
			}
			else Tr.add_part(1,1,n,seq[i].l,seq[i].r,seq[i].opt);	
	}
	inline void clear(){ m=0;Tr.clear(1,1,n);mrk=0; }
};
struct query_seg
{
	int opt,l,r;
	ll v;
	query_seg(int _o=0,int _l=0,int _r=0,ll _v=0):opt(_o),l(_l),r(_r),v(_v){}
};
Sqrt_Block Blc;
query_seg Qr[MAXN];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(re int i=1;i<=N;++i) read(a[i]),Bel[i]=(i-1)/uni+1;
	for(re int i=1;i<=Q;++i)
	{
		read(Qr[i].opt,Qr[i].l,Qr[i].r);
		if(Qr[i].opt==1) read(Qr[i].v);
	}
	for(re int i=1;i<=Bel[N];++i)
	{
		Tot=0;
		Lst[i]=(i-1)*uni+1,Rst[i]=std::min(i*uni,N);
		for(re int j=1;j<=Q;++j)
		{
			auto q=Qr[j];
			if(q.opt==2) ++Tot;
			if(q.l>Rst[i]||q.r<Lst[i]) continue;
			int _l=std::max(q.l,Lst[i])-Lst[i]+1,_r=std::min(q.r,Rst[i])-Lst[i]+1;
			if(q.opt==1)
			{
				if(q.l<=Lst[i]&&Rst[i]<=q.r) Blc.add_all(q.v);
				else Blc.add_part(_l,_r,q.v);
			}
			else Blc.query(_l,_r,Tot);
		}
		Blc.bel=i;Blc.n=Rst[i]-Lst[i]+1;
		if(i==1||i==Bel[N]) pTop=0,Blc.Tr.locate(1,1,Blc.n);
		Blc.prefix();Blc.solve();Blc.clear();
	}
	for(re int i=1;i<=Tot;++i) write(ans[i].val,'\n');
	return 0;
}
/*	

*/

---

Ynoi2013

无力回天 NOI2017

题目简介

题目名称：无力回天

题目来源：

评测链接：https://www.luogu.com.cn/problem/P5607

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

• 对区间 执行 ；
• 选取区间 内的一个子序列求与 的最大异或和。

数据范围：

考虑线性基，但是需要用数据结构维护。根据学习的经验，线段树维护线性基可以做到 的复杂度，但仅支持单点修改。所以我们考虑怎么把这个区间修改转化成单点修改。

考虑差分，设 ，那么现在我们需要执行区间异或，你会发现对于 ，有 ，那不相当于没改吗。所以实际上只会修改 的值。

但现在好修改了，我们得考虑怎么查询。考虑线性基的本质，因为 是通过 异或而出的，所以 中 也只包含了 ，所以 与 的线性基集合应当是相同的。

所以我们单点修改 ，单点查 与 的线性基，然后将 插入后贪心求异或最大值。 可以用 或者其它较快数据结构维护。

时间复杂度 ，好像不怎么卡常。

AC Code

// ----- Eternally question-----
// Problem: P5607 [Ynoi2013] 无力回天 NOI2017
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5607
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-08-28 14:46:50
// ----- 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){ putchar(x?'1':'0'); }
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=5e4+10,MAXS=34;
int N,Q,val[MAXN];
struct Basis
{
	int Set[MAXS];
	Basis(){ std::memset(Set,0,sizeof(Set)); }
	int operator[](const int &x){ return Set[x]; }
	inline void init(){ std::memset(Set,0,sizeof(Set)); }
	inline void insert(int x)
	{
		if(!x) return ;
		for(int i=31;~i;--i)
			if(x>>i&1)
			{
				if(Set[i]) x^=Set[i];
				else return Set[i]=x,void();
			}
	}
};
inline Basis merge(Basis a,Basis b)
{
	Basis c;
	for(int i=0;i<=31;++i) c.insert(a[i]),c.insert(b[i]);
	return c;
}
struct Segment
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct St
	{
		int l,r;
		Basis val;
	}Tr[MAXN<<2];
	inline void pushUp(int p){ Tr[p].val=merge(Tr[ls].val,Tr[rs].val); }
	void build(int p,int l,int r)
	{
		Tr[p].l=l,Tr[p].r=r;
		for(int i=l;i<=r;++i) Tr[p].val.insert(val[i]);
		if(l==r) return ;
		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)
		{
			Tr[p].val.init();
			Tr[p].val.insert((val[x]^=v));
			return ;
		}
		int mid=(Tr[p].l+Tr[p].r)>>1;
		x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
		pushUp(p);
	}
	Basis querySet(int p,int l,int r)
	{
		if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
		int mid=(Tr[p].l+Tr[p].r)>>1;
		Basis res;
		if(l<=mid) res=querySet(ls,l,r);
		if(mid<r) res=merge(res,querySet(rs,l,r));
		return res;
	}
}Tr;
struct BIT
{
	int Tre[MAXN],Siz;
	inline int lowbit(int x){ return x&(-x); }
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]^=v; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res^=Tre[x];
		return res;
	}
}Tre;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Tre.build(N);
	for(int i=1;i<=N;++i) read(val[i]);
	for(int i=N;i>=2;--i) val[i]^=val[i-1];
	for(int i=1;i<=N;++i) Tre.add(i,val[i]);
	Tr.build(1,1,N);
	for(int opt,ql,qr,qv;Q--;)
	{
		read(opt,ql,qr,qv);
		if(opt==1)
		{
			Tre.add(ql,qv);Tr.modifyX(1,ql,qv);
			if(qr<N) Tre.add(qr+1,qv),Tr.modifyX(1,qr+1,qv);
		}
		else
		{
			int al=Tre.query(ql);
			if(ql==qr) write(std::max(qv,al^qv),'\n');
			else
			{
				Basis cur=Tr.querySet(1,ql+1,qr);
				cur.insert(al);
				for(int i=31;~i;--i) checkMax(qv,qv^cur[i]);
				write(qv,'\n');
			}
		}
	}
	return 0;
}
/*

*/

---

Ynoi2016

炸脖龙 I

题目简介

题目名称：炸脖龙

题目来源：

评测链接：https://www.luogu.com.cn/problem/P3934

给定一个长度为 的序列 以及 次操作：

• 对区间 加 ；
• 求 的幂塔对 取模。

幂塔的形式如 。

数据范围：

感觉在 乱做题的时候遇到过类似的，经证明发现是 的卡常版，发现 lxl 真的喜欢抓一些题来卡常过后整个多么大的范围。

首先了解欧拉降幂，也就是扩展欧拉定理：

$$a^x\equiv \begin{cases} a^x&,x<\varphi(p)\\ a^{x\bmod\varphi(p)+\varphi(p)}&,x\geq\varphi(p) \end{cases} \pmod{p}$$

这让幂级运算降到了 级，且这个定理不要求 ，所以可以在这道题中使用。

然后考虑递归求解幂塔，每上升一层模数就会 ，根据结论当 时 ，所以至多处理 层。相当于询问可以直接暴力做。

然后考虑修改，是区间修改单点查询，所以用 维护差分求前缀和即可。求 可以线性筛，脑抽了暴力求还跑了最优解。

时间复杂度是小常数的 ，常数大了过不了，需要注意 是 级别的，所以快速幂之类的中途转换要写 __int128_t。

AC Code

// ----- Eternally question-----
// Problem: P3934 [Ynoi2016] 炸脖龙 I
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3934
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// Written by: Eternity
// Time: 2023-08-23 20:53:27
// ----- 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){ putchar(x?'1':'0'); }
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; }
using Int=__int128_t;
const int MAXN=5e5+10;
int N,Q,ql,qr,a[MAXN],P;
std::unordered_map<ll,ll>Phi;
struct BIT
{
	ll Tre[MAXN];
	int Siz;
	inline int lowbit(int x){ return x&(-x); }
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline void add(int x,int v){ for(;x<=Siz;x+=lowbit(x)) Tre[x]+=v; }
	inline ll query(int x)
	{
		ll res=0;
		for(;x;x-=lowbit(x)) res+=Tre[x];
		return res;
	}
}Tre;
inline int getPhi(int p)
{
	int res=p;
	for(int i=2;i*i<=p;++i)
	{
		if(p%i==0)
		{
			res=res/i*(i-1);
			while(p%i==0) p/=i;
		}
	}
	if(p>1) res=res/p*(p-1);
	return res;
}
inline int Mod(Int x,int p)
{ return x%p+(x>=p)*p; }
inline int qPow(ll a,int b,int p)
{
	int res=1;
	while(b)
	{
		if(b&1) res=Mod((Int)res*a,p);
		a=Mod((Int)a*a,p);b>>=1;
	}
	return res;
}
int dfs(int x,int p)
{
	if(x>qr||p==1) return 1;
	if(Phi.find(p)==Phi.end()) Phi[p]=getPhi(p);
	int res=dfs(x+1,Phi[p]);
	return qPow(Tre.query(x),res,p);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Tre.build(N);
	for(int i=1;i<=N;++i) read(a[i]),Tre.add(i,a[i]-a[i-1]);
	for(int opt;Q--;)
	{
		read(opt,ql,qr,P);
		if(opt==1) Tre.add(ql,P),Tre.add(qr+1,-P);
		else write(dfs(ql,P)%P,'\n');
	}
	return 0;
}
/*

*/

---

Ynoi2017

由乃打扑克

题目简介

题目名称：由乃打扑克
题目来源：

评测链接：https://www.luogu.com.cn/problem/P5356

形式化题意：给定一个长度为 的序列以及 次操作：

• 对区间 执行 ；
• 求区间 第 小值。

数据范围：

考虑一个朴素的做法，求某数的区间排名和求区间中排名的数可以在 时间内互相转化。

所以我们考虑求区间中 的数的个数，然后通过二分 得到答案。

然后考虑一种很新的分块技巧，对于散块，我们当然可以直接暴力统计，那对于整块，我们可以复制一份块内元素记作 ，而 在每一个块中应当是有序的。这样的话，我们可以通过在每一个整块中二分得到当前块 的个数。

所以修改时相当于维护 ，对于整块，同时加减一个数不会影响相对大小，所以直接修改标记。而对于散块，我们可以直接暴力重构。这样的时间复杂度为 。

所以，我们现在可以得到一个时间复杂度为 ，算同阶的话就可以得到 的做法。

然后考虑优化，第一个瓶颈在于散块的暴力重构，我们发现一个块中某一区间会统一 ，而这个区间内元素的相对顺序不会改变，同理除开该区间的其他部分也是一样的，所以我们可以视作两个区间归并，可以直接线性做到 的重构复杂度。

第二个瓶颈在于查询的散块暴力，显然这并不优美，所以我们也将左右散块归并为一个大块，然后在这个大块上二分。可以少一个 的常数。

第三个瓶颈在于值域二分，左右极限应是 ，但显然前几个查询远远不会到达这个极限，所以可以维护区间极值，但这样多个线段树；或者记录一个修改次数，用 乘上修改次数得到极限，注意可能会存在 爆 int 的情况，详见 。

这样最后的时间复杂度为 ，可以发现取 最优，得到 。不过有意思的是，按理来说， 应该在 左右，但我的代码居然在 左右的时候最快，可以通过本题。这样的话，大概是散块常数远大于整块。

AC Code

// ----- Eternally question-----
// Problem: P5356 [Ynoi2017] 由乃打扑克
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5356
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-08-26 19:45:24
// ----- 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){ putchar(x?'1':'0'); }
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=1e5+10,MAXB=1e3+10;
int L=-2e4,R=2e4,Total=1;
int N,Q,val[MAXN];
int Uni,Tot,Bel[MAXN],Lst[MAXB],Rst[MAXB];
struct Node
{
	int v,id;
	bool operator<(const Node &x) const
	{ return v==x.v?id<x.id:v<x.v; }
}Ele[MAXB][MAXB],tmp1[MAXB],tmp2[MAXB];
int Tag[MAXB],tmp3[MAXB];
inline void build()
{
	Uni=200;
	Tot=(N-1)/Uni+1;
	for(re int i=1;i<=Tot;++i) Lst[i]=Rst[i-1]+1,Rst[i]=i*Uni;
	Rst[Tot]=N;
	for(re int i=1;i<=Tot;++i)
	{
		for(re int j=Lst[i];j<=Rst[i];++j) Bel[j]=i,Ele[i][j-Lst[i]+1]=(Node){val[j],j};
		std::sort(Ele[i]+1,Ele[i]+Rst[i]-Lst[i]+2);
	}
}
inline void modifyAdd(int l,int r,int v)
{
	int bl=Bel[l],br=Bel[r];
	if(bl==br)
	{
		int cnt1=0,cnt2=0,cur1=1,cur2=1,tot=0;
		for(re int i=1;i<=Rst[bl]-Lst[bl]+1;++i)
		{
			auto e=Ele[bl][i];
			if(l<=e.id&&e.id<=r) tmp2[++cnt2]=(Node){e.v+v,e.id};
			else tmp1[++cnt1]=e;
		}
		while(cur1<=cnt1&&cur2<=cnt2)
		{
			if(tmp1[cur1].v>tmp2[cur2].v) Ele[bl][++tot]=tmp2[cur2++];
			else Ele[bl][++tot]=tmp1[cur1++];
		}
		while(cur1<=cnt1) Ele[bl][++tot]=tmp1[cur1++];
		while(cur2<=cnt2) Ele[bl][++tot]=tmp2[cur2++];
		return ;
	}
	int cnt1=0,cnt2=0,cur1=1,cur2=1,tot=0;
	for(int i=1;i<=Rst[bl]-Lst[bl]+1;++i)
	{
		auto e=Ele[bl][i];
		if(l<=e.id) tmp2[++cnt2]=(Node){e.v+v,e.id};
		else tmp1[++cnt1]=e;
	}
	while(cur1<=cnt1&&cur2<=cnt2)
	{
		if(tmp1[cur1].v>tmp2[cur2].v) Ele[bl][++tot]=tmp2[cur2++];
		else Ele[bl][++tot]=tmp1[cur1++];
	}
	while(cur1<=cnt1) Ele[bl][++tot]=tmp1[cur1++];
	while(cur2<=cnt2) Ele[bl][++tot]=tmp2[cur2++];
	cnt1=cnt2=0,cur1=cur2=1,tot=0;
	for(re int i=1;i<=Rst[br]-Lst[br]+1;++i)
	{
		auto e=Ele[br][i];
		if(e.id<=r) tmp2[++cnt2]=(Node){e.v+v,e.id};
		else tmp1[++cnt1]=e;
	}
	while(cur1<=cnt1&&cur2<=cnt2)
	{
		if(tmp1[cur1].v>tmp2[cur2].v) Ele[br][++tot]=tmp2[cur2++];
		else Ele[br][++tot]=tmp1[cur1++];
	}
	while(cur1<=cnt1) Ele[br][++tot]=tmp1[cur1++];
	while(cur2<=cnt2) Ele[br][++tot]=tmp2[cur2++];
	for(re int i=bl+1;i<=br-1;++i) Tag[i]+=v;
}
inline int getCnt(int x,int v)
{
	int l=1,r=Rst[x]-Lst[x]+1,res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(Ele[x][mid].v<=v) res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
int queryCnt(int l,int r,int v)
{
	int bl=Bel[l],br=Bel[r];
	if(bl==br)
	{
		int ans=0;
		for(re int i=1;i<=Rst[bl]-Lst[bl]+1;++i)
		{
			auto e=Ele[bl][i];
			if(l<=e.id&&e.id<=r) ans+=((e.v+Tag[bl])<=v);
		}
		return ans;
	}
	int ans=0,cur1=1,cur2=1,tot=0,cnt1=0,cnt2=0;
	for(re int i=1;i<=Rst[bl]-Lst[bl]+1;++i) if(Ele[bl][i].id>=l) tmp1[++cnt1]=Ele[bl][i];
	for(re int i=1;i<=Rst[br]-Lst[br]+1;++i) if(Ele[br][i].id<=r) tmp2[++cnt2]=Ele[br][i];
	while(cur1<=cnt1&&cur2<=cnt2)
	{
		if(tmp1[cur1].v+Tag[bl]>tmp2[cur2].v+Tag[br]) tmp3[++tot]=tmp2[cur2++].v+Tag[br];
		else tmp3[++tot]=tmp1[cur1++].v+Tag[bl];
	}
	while(cur1<=cnt1) tmp3[++tot]=tmp1[cur1++].v+Tag[bl];
	while(cur2<=cnt2) tmp3[++tot]=tmp2[cur2++].v+Tag[br];
	int _l=1,_r=tot,_res=0;
	while(_l<=_r)
	{
		int _mid=(_l+_r)>>1;
		if(tmp3[_mid]<=v) _res=_mid,_l=_mid+1;
		else _r=_mid-1;
	}
	ans+=_res;
	for(re int i=bl+1;i<=br-1;++i)
	{
		if(Ele[i][1].v+Tag[i]>v) continue;
		else if(Ele[i][Rst[i]-Lst[i]+1].v+Tag[i]<=v){ ans+=Rst[i]-Lst[i]+1;continue; }
		ans+=getCnt(i,v-Tag[i]);
	}
	return ans;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(re int i=1;i<=N;++i) read(val[i]);
	build();
	for(int opt,ql,qr,qx;Q--;)
	{
		read(opt,ql,qr,qx);
		if(opt==2) modifyAdd(ql,qr,qx),++Total;
		else
		{
			if(qx>qr-ql+1){ puts("-1");continue; }
			int l=L*Total,r=R*Total,ans=R;
			while(l<=r)
			{
				int mid=((ll)l+r)>>1;
				int res=queryCnt(ql,qr,mid);
				// write(mid,' ',res,'\n');
				if(res>=qx) ans=mid,r=mid-1;
				else l=mid+1; 
			}
			write(ans,'\n');
		}
	}
	return 0;
}
/*

*/

---