526互联

The 2020 ICPC Asia Shenyang Regional Programming Contest J. Descent of Dragons

发布时间 2023-11-16 18:02:16作者: 空気力学の詩

来道喜闻乐见的DS题，这题虽然比较套路但还是挺有趣的

一个朴素的想法就是用类似于珂朵莉树那样的方式维护所有内部等级相同的区间，但当操作数量上去后，显然分出的区间数量就变得不可控了，无法处理

另一个朴素的想法就是对于不同等级的龙维护它们的所有信息，直接暴力记录的话肯定不行，但考虑到操作的方式是从\(x\)升级到\(x+1\)，其实就提示我们是否能利用上这个“继承”关系

用可持久化线段树，对于版本号为\(x\)的线段树，定义某个区间\([l,r]\)的权值为“区间内是否有等级\(\ge x\)的龙”

为什么这里要定义成大于等于呢，其实有两种好处，一来是为了方便处理询问

当我们这样定义权值后，我们就可以直接二分答案，然后直接在对应版本的线段树上查询即可，如果改成\(=\)的话这里显然就会失去二分性

二来，这样也方便我们修改，这样我们每次继承信息的时候，直接把旧版本对应子树直接复制到新版本上即可，不然还要分值是否等于\(x\)来搞，就非常麻烦

最后要注意一个细节，这题和一般的主席树不同的地方在于每个版本可能会用到不止一次，因此在修改的时候要时刻更新每个版本，这个具体看代码就很好理解

总复杂度\(O(q\log^2 n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int n,q,rt[N],opt,l,r,x;
class Segment_Tree
{
	private:
		struct segment
		{
			int ch[2],val;
		}node[N*40]; int tot;
	public:
		#define TN CI l=1,CI r=n
		#define LS l,mid
		#define RS mid+1,r
		#define ls(x) node[x].ch[0]
		#define rs(x) node[x].ch[1]
		#define v(x) node[x].val
		inline void pushup(CI now)
		{
			v(now)=v(ls(now))|v(rs(now));
		}
		inline void build(int& now,TN)
		{
			now=++tot; v(now)=1; if (l==r) return;
			int mid=l+r>>1; build(ls(now),LS); build(rs(now),RS);
		}
		inline void copy(int& now,CI lst,CI beg,CI end,TN)
		{
			if (beg<=l&&r<=end) return (void)(now=lst);
			int cur=++tot; node[cur]=node[now]; now=cur; int mid=l+r>>1;
			if (beg<=mid) copy(ls(now),ls(lst),beg,end,LS);	if (end>mid) copy(rs(now),rs(lst),beg,end,RS); pushup(now);
		}
		inline int query(CI now,CI beg,CI end,TN)
		{
			if (!now) return 0; if (beg<=l&&r<=end) return v(now); int mid=l+r>>1,ret=0;
			if (beg<=mid) ret|=query(ls(now),beg,end,LS); if (end>mid) ret|=query(rs(now),beg,end,RS); return ret;
		}
		#undef TN
		#undef LS
		#undef RS
		#undef ls
		#undef rs
		#undef v
}SEG;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&q),SEG.build(rt[0]),i=1;i<=q;++i)
	{
		scanf("%d%d%d",&opt,&l,&r);
		if (opt==1) scanf("%d",&x),SEG.copy(rt[x+1],rt[x],l,r); else
		{
			int L=0,R=i-1,mid,ret; while (L<=R)
			if (SEG.query(rt[mid=L+R>>1],l,r)) ret=mid,L=mid+1; else R=mid-1;
			printf("%d\n",ret);
		}
	}
	return 0;
}