CF1009F Dominant Indices

首先介绍一下我们亲爱的dsu on tree,也就是(一种?)树上启发式合并。
它本质上就是一种优化的暴力:对于树上的信息,我们先把树以某种方式剖分,然后对于关键链直接上传,非关键链暴力合并。
其中,长链剖分一般用来维护和深度相关的信息。
复杂度是O(n)的。证明我不太会。
在这一题中,我们考虑暴力维护每个点为根的子树中每一层的信息,并把非长儿子的信息合并到长儿子中。
为了保证线性,我们使用指针。
我们建一个指针数组f,其中f_{i,j}表示以i为根的根节点的子树中到i的距离为j的节点的个数。
同时建一个数组tmp,那么f就变成指向的是tmp里面的值。这样子就可以O(1)合并非长儿子的信息了。因为\sigma len<=n,所以空间是足够的。
那就昨晚了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n;
int sn[N],len[N],ans[N],tmp[N],*f[N],*id=tmp;
inline void dfs0(int X,int FA){
	sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		if(len[sn[X]]<len[e[i].v]){
			sn[X]=e[i].v;
		}
	}
	len[X]=len[sn[X]]+1;
}
inline void dfs1(int X,int FA){
	f[X][0]=1;
	if(sn[X]){
		f[sn[X]]=f[X]+1;
		dfs1(sn[X],X);
		ans[X]=ans[sn[X]]+1;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		f[e[i].v]=id;id+=len[e[i].v];
		dfs1(e[i].v,X);
		for(int j=1;j<=len[e[i].v];++j){
			f[X][j]+=f[e[i].v][j-1];
			if((j<ans[X]&&f[X][j]>=f[X][ans[X]])||(j>ans[X]&&f[X][j]>f[X][ans[X]])){
				ans[X]=j;
			}
		}
	}
	if(f[X][ans[X]]==1){
		ans[X]=0;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	dfs0(1,0);
	f[1]=id;id+=len[1];
	dfs1(1,0);
	for(int i=1;i<=n;++i){
		printf("%d\n",ans[i]);
	} 
}
int main(){
	init();
	return 0;
}

初赛复习:前缀表达式和后缀表达式

前缀表达式和后缀表达式——有时也被成为波兰表达式和逆波兰表达式——是对仅包含二元关系运算符和括号的表达式的变形。

事实上,前缀表达式和后缀表达式没有本质区别,因此只要会了前缀表达式,就会了后缀表达式——记住,前缀表达式是把运算符提到最前面的表达式,而后缀表达式反之。

对于一个这样的式子:
a+b/c
我们按照运算符优先级依次操作:
a+/bc
+a/bc
这样就将所有符号提到了整个式子的最前面。
对于包含括号的表达式,例如:
2+3(4-(5+6))/7 操作流程依然是按照运算符优先级的。 2+3(4-+5 6)/7
2+3(-4+5 6)/7 2+3(-4+5 6)/7
2+/3-4+5 6 7 +2/3-4+5 6 7

而如果要求后缀表达式,那操作就反之——从优先级最低的操作符开始,把操作符提到最右边。
还是一样的例子:
2 3(4-(5+6))/7+ 2 3(4-(5+6))7/+
2 3(4-(5+6))7/+ 2 3(4(5+6)-)7/+
2 3 4 5 6+-*7/+

初赛复习:OSI七层网络协议

ISO网络协议标准包括七层。

最底层的被称为物理层。这一层主要包括:
光纤、同轴电缆、双绞线、网卡、中继器、集线器
等硬件。它传输的是比特(bit)

物理层之上被称为数据链路层。数据链路层的主要硬件是网桥和交换机,这一层把数据封装成一种被称为帧(frame)的结构。

网络层是第三层。IP地址是这一层的内容。路由器也在这一层。

传输层是网络层之上的第四层。这一层主要管的是数据包的运输。TCP协议UDP协议都是传输层协议。

会话层是第五层,没看到什么考点。

表示层主要负责数据转换,没看到什么考点。

应用层是最顶层,应用层协议包括Telnet(Windows的远程桌面)、FTPSNMP(这两个都是远程文件管理系统)、HTTPDNS(IP地址解析服务)等协议。它是直接展现给用户的一层。

初赛复习:主定理

对于形如:
$$T(n)=aT(\frac{n}{b})+f(n)$$
那么,我们可以用下述三个公式来刻画\(T(n)\)的渐近上下界。
$$f(n)=\Theta(n^{log_ba-\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(n^{log_ba})$$
$$f(n)=\Theta(n^{log_ba+\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(f(n))$$
$$f(n)=\Theta(n^{log_ba})\Rightarrow T(n)=\Theta(n^{log_ba}logn)$$
换而言之,就是,比较\(f(n)\)和\(\Theta(n^{log_ba})\)的级别。如果两者同级,就乘上一个log,否则就取较大的。

lp1341 无序字母对

仔细观察这题:考虑到字母对可以反向,我们不妨把它们看作无序数对。这就把题意转化为了,给你n个无序数对,让你找到一个n+1个数的序列,使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性,我们可以尝试把无序数对看成一条边,然后建一张图。在这种情况下,这个序列就是这张图上的一个遍历顺序,使得经过每一条边至少一次。
深入考虑,这个序列也只能经过每条边至多一次。这是因为,一条n条边的路径,恰好包含了n+1个点。
问题就转化为了欧拉路径问题。

判断一张图是否是半欧拉图是很容易的。一张半欧拉图中,恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点,我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上,只需从奇数入度点开始,就是合法的?
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是,为什么搜索的时候不会直接走到链的另一端,而是先把环跑完,或者反过来?
我们注意到把点加入答案数组的方式:对于两个栈——答案栈和搜索栈来说,点被加入的顺序是不仅相同的。
模拟一下,一个点能从搜索栈出来,被加入答案栈,当且仅当从这个点出发无路可走了。
显然,有且仅有终点是无路可走的。那么,无论终点是在什么时候被访问到的,只要它被访问到,那么它就会被立刻退出搜索栈并被加入答案栈,剩下的点也是同理。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
	for(int i=0;i<52;++i){
		if(mp[X][i]){
			printf("%d %d\n",X,i);
			--mp[X][i],--mp[i][X];
			dfs(i);
		}
	}
	printf("%d\n",X); 
	st[++tp]=X;
}
void init(){
	for(int i=0;i<26;++i){
		hash['A'+i]=i;hash['a'+i]=i+26;
		hsah[i]='A'+i;hsah[i+26]='a'+i;
	}
	scanf("%d",&n);
	char ch[4];
	for(int i=1;i<=n;++i){
		std::cin>>ch+1;
		++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
		++in[hash[ch[1]]],++in[hash[ch[2]]];
	}
	int ans=0,nans=-1;
	for(int i=0;i<52;++i){
		if(in[i]&1){
			++ans;
			if(nans<0){nans=i;}
		}
	}
	if(ans&&ans!=2){
		puts("No Solution");
		return;
	}
	if(!ans){
		for(int i=0;i<52;++i){
			if(in[i]){
				nans=i;
				break;
			}
		}
	}
	dfs(nans);
	if(tp!=n+1){
		puts("No Solution");
		return;
	}
	while(tp){
		putchar(hsah[st[tp--]]);
	}
}
int main(){
	init();
	return 0;
}

lp4027 NOI2007 货币兑换

我们观察到,整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得:
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说,购买的A和B券的数量分别是:
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么,我们从j转移到i的方程是:
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设:
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$
那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。
通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意:要判一下分母不能等于极小数,否则可能会挂。

略微思考一下就可以证明这个定理。倘若先部分买再部分买,再全卖,显然不是优的。因为我们总可以找到更优的部分,使得全买再全卖更优;同理,部分卖再部分卖也一定不会更优。这是因为,券是必须按比例卖出的。 于是,我们就把整个决策拆分为很多个全买和全卖交替出现的点,然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A,那么购买的数量是x/A,那么购买了B的数量是x/(A*Rate),花费的钱是xB/(A*Rate)。可以解得: $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说,购买的A和B券的数量分别是: $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么,我们从j转移到i的方程是: $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是,斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中,这使得我们设\(f_j=y\)的计划破产了。 我们不妨设: $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到: $$f_i=A_ix_j+B_iy_j$$ 那么,当前点之前的所有点构成的就是平面上的一些点,然后我们要用这条直线去切这些点,找到截距最大的那个。 通过这个斜率优化,我们把问题如下转换:我们有一个仅包含第一象限的平面,有\(10^5\)个操作,每个操作可能是加入一个点,或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此,我们对时间分治,然后左半部分对x坐标排序——这是为了维护凸包;对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线,都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的,因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意:要判一下分母不能等于极小数,否则可能会挂。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;

const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
	double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。 
inline double cmp(const data &A,const data &B){
	return A.a*B.b>B.a*A.b; 
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
//	printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
	return a[P].x*A+a[P].y*B; 
}
inline double slp(int A,int B){
	if(fabs(a[A].x-a[B].x)<eps){
		return INF;
	}
	return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
	int mid=(l+r)>>1;
	int I=l,J=mid+1,tp=l;
	while(I<=mid&&J<=r){
		if(a[I].x<a[J].x){
			b[tp++]=a[I++];
		}else{
			b[tp++]=a[J++];
		}
	}
	while(I<=mid){
		b[tp++]=a[I++];
	}
	while(J<=r){
		b[tp++]=a[J++];
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
}
inline void cdq(int l,int r){
	if(l==r){
		f[l]=max(f[l],f[l-1]);
		a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
		a[l].x=(double)a[l].r*a[l].y;
		return;
	}
	int mid=(l+r)>>1;
	int I=l,J=mid+1;
	for(int i=l;i<=r;++i){
		if(a[i].id<=mid){
			b[I++]=a[i];
		}else{
			b[J++]=a[i];
		}
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i];
	}
	cdq(l,mid);
	tp=0;
	for(int i=l;i<=mid;++i){
		while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
			--tp;
		}
		st[++tp]=i;
	}
//	printf("[%d,%d]\n",l,r);
//	for(int i=1;i<=tp;++i){
//		printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
//	}
	for(int i=mid+1;i<=r;++i){
		while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
			--tp;
		}
		f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
//		printf("%d %lf\n",i,a[i].ans); 
	}
	cdq(mid+1,r);
	mg(l,r);
}
void init(){
	scanf("%d%lf",&n,&f[0]);
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	cdq(1,n);
//	for(int i=1;i<=n;++i){
//		printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
//	}
	printf("%.3lf\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp2564 SCOI2009 生日礼物

尺取法即可。
开一个桶维护珍珠的颜色,然后扫一遍。每一次将最前端的点弹出,然后移动至下一个合法点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
	scanf("%d%d",&n,&K);
	int T;
	for(int i=1;i<=K;++i){
		scanf("%d",&T);
		for(int j=1;j<=T;++j){
			++tp;
			scanf("%d",&a[tp].val);
			a[tp].id=i;
		}
	}
	std::sort(a+1,a+1+n,cmp);
	int ans=2147483647;
	int l=1,r=0;
	while(r<n){
		while(r<n){
			++r;
			if(!bckt[a[r].id]){
				++cnt;
			}
			++bckt[a[r].id];
			if(cnt==K){
				break;
			}
		}
		if(cnt==K){
			ans=min(ans,a[r].val-a[l].val);
		}
		while(l<=r){
			--bckt[a[l].id];
			if(!bckt[a[l].id]){
				--cnt;
				++l;
				break;
			}
			++l;
			if(cnt==K){
//				printf("%d %d %d\n",ans,l,r);
				ans=min(ans,a[r].val-a[l].val);
			}
			
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp2219 HAOI2007 修筑绿化带

我们知道,如果我们确定了每个大矩形包含的权值最小的小矩形,那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。

那么我们考虑用单调队列来预处理出每一个小矩形的权值,然后用二维线段树来维护这个权值,那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然,我们可以维护2n个单调队列来计算这个最大值。
那么,对于这题的强化板,我们该怎么做呢?
如果确定了右下角,那么整个矩形的权值是已经固定了的。那么,我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题,我们发现,每个花坛的最小值是可以预处理的。这样,我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂,且不要混淆单调队列里的数的意义。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1005;

int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
	scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&val[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
		}
	}
	for(int i=B;i<=n;++i){
		for(int j=A;j<=m;++j){
			b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
//			printf("%d ",b[i][j]);
		}
//		puts("");
	}
	for(int i=D;i<=n;++i){
		for(int j=C;j<=m;++j){
			a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
//			printf("%d ",a[i][j]);
		}
//		puts("");
	}
	int ans=0;
	for(int i=D+1;i<n;++i){
		for(int j=C+1;j<m;++j){
//			printf("%d %d\n",i,j);
			while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
			q[j].push_back(i);
			while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
		}
		while(!qq.empty()){qq.pop_back();}
		for(int j=C+1;j<m;++j){
			while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
			qq.push_back(j);
			while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
			if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

P1083 NOIP2012 借教室

本质上是区间减区间最小值。
考虑到先操作再询问,差分加前缀和即可。
对于题目要求的那个答案,我们找到第一个不合法的点,然后枚举每一个询问和它比较即可
复杂度O(n+m)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
 
typedef long long ll;
const int N=1000005;
ll a[N],val[N];
int qx[N],ql[N],qr[N];
int n,m;
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&qx[i],&ql[i],&qr[i]);
		val[ql[i]]+=qx[i],val[qr[i]+1]-=qx[i];
	}
	int loc=0;
	for(int i=1;i<=n;++i){
		val[i]+=val[i-1];
		if(val[i]>a[i]){
			loc=i;
			break;
		}
	}
	if(!loc){
		puts("0");
		return;
	}
	ll cnt=0;
	for(int i=1;i<=m;++i){
		if(ql[i]<=loc&&qr[i]>=loc){
			if(cnt+qx[i]>a[loc]){
				puts("-1");
				printf("%d\n",i);
				return;
			}else{
				cnt+=qx[i];
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp3285 SCOI2014 方伯伯的OJ

题目要求维护一个编号序列和一个排名序列,并支持四种操作:
1.按照编号修改编号,并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名,然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8,那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续:这一题是我在190103的时候写完的,然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用,这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误,进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后,经由此处,我发现有个节点的相邻节点是一个大小为空的节点,进而发现这个节点在被分配下标之前就被访问了。
最终,我注意到它第一次出现所相接的节点,并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错,并通过了此题。
注意点:
1.对于空节点的情况一定要认真考虑,因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」!!!!!!
4.如果一个点本来就是排名最后的点而要移到排名最后,有可能会出错。

#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);

bool bo=0;
class Splay{
	public:
		class Node{
			public:
				int l;
				int r;
				int sz;
				int sn[2];
				int fa;
				inline void set(int L,int R,int FA){
					l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
				}
		};
		//i表示mp[i]这个节点的右端点的标号。 
		std::map<int,int> mp;
		Node tr[400005];
		int cnt,rt;
		//寻找当前节点与父亲的关系。 
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		//更新当前节点。 
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
//			if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
		}
		//旋转套装。 
		inline void splayOne(int X){
			if(!X){return;}
			int D=fndD(X),D2=fndD(tr[X].fa);
//			if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
//				puts("FKFKFK");
//				printf("X");debug(X);
//				printf("FA");debug(tr[X].fa);
//				printf("BR");debug(tr[tr[X].fa].sn[D^1]);
//			}
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
//			if(bo&&X==38190){debug(X);}
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){splayTwo(X);}
			rt=X;
		}
//		inline void splayRnw(int X){
//			while(tr[X].fa){
//				int F=tr[X].fa,FF=tr[tr[X].fa].fa;
//				if(!FF)
//			}
//		}
		//找到排名为X的元素。 
		inline int fnd(int X){
			int P=rt;
			while(P){
				if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
					X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
					P=tr[P].sn[1];
				}else if(X>tr[tr[P].sn[0]].sz){
					X-=tr[tr[P].sn[0]].sz;
					splayRnw(P);
//					debug(P);
					return tr[P].l+X-1;
				}else{
					P=tr[P].sn[0];
				}
			}
			return -1; 
		}
		//开一个新节点,以X为它的父亲。 
		inline int nwlc(int X,int L,int R){
			int P=++cnt;
//			if(P==65505){
//				printf("START:");
//				debug(P);
//			}
			tr[P].set(L,R,X);
			return P;
		}
		//将编号为X的节点单独弄成一个新的节点,然后将它的两个子节点接到它的左右,并更改相应的编号的映射 
		inline int split(int P,int X){
			if(tr[P].l==tr[P].r){return P;}
			if(P==-1){return error(192600404),192600404;}
			if(X>tr[P].l){
				int L=tr[P].sn[0];
				L?(cut(L),0):(tr[0].fa=0);
				tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
				L?(cnnct(L,tr[P].sn[0],0),0):0;
				mp[X-1]=tr[P].sn[0];
//				updt(tr[P].sn[0]);
			}
			if(X<tr[P].r){
				int R=tr[P].sn[1];
				R?(cut(R),1):(tr[0].fa=0);
				tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
				R?(cnnct(R,tr[P].sn[1],1),1):1;
				mp[tr[P].r]=tr[P].sn[1];
//				updt(tr[P].sn[1]);
			}
			tr[P].l=tr[P].r=X;mp[X]=P;
			updt(P);
			return P;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0]; 
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline void cut(int X){
			int D=fndD(X);
			tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
		}
		inline void cnnct(int X,int Y,int D){
			tr[Y].sn[D]=X,tr[X].fa=Y;
			updt(Y);
		}
		inline void prnt(int X,int dep=0){
			if(!X){return;}
			for(int i=1;i<=dep;++i){
				printf(" ");
			}debug(X);
			prnt(tr[X].sn[0],dep+1);
			prnt(tr[X].sn[1],dep+1);
		}
	public:
		inline int CHANGE(int X,int Y){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			tr[P].l=tr[P].r=Y;
			mp[Y]=P;
			splayRnw(P);
			return tr[tr[P].sn[0]].sz+1;
		}
		inline int LST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!L){
				return RT;
			}
			R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。 
			return RT;
		}
		inline int RST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!R){
				return RT;
			}
			L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
			return RT;
		}
		inline int ARNK(int X){
			return fnd(X);
		} 
		//初始化。 
		inline void INIT(int N){
			cnt=1;
			rt=1;
			tr[1].set(1,N,0);
			mp[N]=1;
		}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。 
*/

int n,m;
Splay T;
void init(){
	int code=0;
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int op,x,y;
	for(int i=1;i<=m;++i){
		scanf("%d",&op);
		switch(op){
			case 1:{
				scanf("%d%d",&x,&y);
				x-=code,y-=code;
				printf("%d\n",code=T.CHANGE(x,y));
//				if(code==95204&&i>=80000){
//					puts("fk1");
//					printf("%d\n",x);
//					return;
//				}
				break;
			}
			case 2:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.LST(x));
				break;
			}
			case 3:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.RST(x));
				break;
			}
			case 4:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.ARNK(x));
				break;
			}
		}
//		printf("CORESIZE:%d\n",T.tr[54567].sz);
	}
}

int main(){
//	freopen("input1.in","r",stdin);
//	freopen("output1.out","w",stdout);
	init();
	return 0;
} 

lp4768 NOI2018 归程

克鲁斯卡尔重构树模板题。
我们发现,这一题可以拆成两个步骤。第一个步骤,是找到所有u可以通过共享单车达到的点;第二个步骤,是找到这些点中到原点最小的点的距离。
我们容易发现,第一个步骤和长度无关,第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构:当你使用克鲁斯卡尔算法建最小/最大生成树的时候,每一次合并,你新建一个节点p,这个点的点权是这一次合并通过的边的边权,然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树,其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例,我们构造一棵最大生成树,那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说,从u在d的降水下可以到的节点,就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树,每个点的父亲节点的点权不会大于这个节点。这也就意味着,我们需要找到u的最高的祖先,使得这个祖先的点权大于等于d。不妨称这个祖先为w,那么w的子树的所有叶子节点,就是u在d的降水下能抵达的节点。
于是,我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图,我们先求出1号节点到所有节点的距离,然后把这些值赋到叶子节点上,不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」,那么就可以进行树形dp,把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=800005,M=800005;
const int INF=0x3f3f3f3f;

inline int Min(int A,int B){
	return A<B?A:B;
}

struct ee{
	int v;
	int w;
	int a;
	int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
	e[++et]=(ee){V,W,A,h[U]};
	h[U]=et;
}
inline void add(int U,int V,int W,int A){
	Eadd(U,V,W,A);
	Eadd(V,U,W,A);
}
struct tee{
	int v;
	int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
	te[++et]=(tee){V,g[U]};
	g[U]=et;
}
inline void tadd(int U,int V){
	tEadd(U,V);
	tEadd(V,U);
}
struct data{
	int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
	return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
	return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
	X=fa(X),Y=fa(Y);
	tadd(ff[X],cnt);tadd(ff[Y],cnt);
	ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
	cnt=n;
	for(int i=1;i<=m;++i){
		if(fa(lst[i].u)==fa(lst[i].v)){
			continue;
		}
		val[++cnt]=lst[i].a;
		uni(lst[i].u,lst[i].v);
		if(cnt==n*2-1){
			break;
		}
	}
	rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
	inline bool operator()(int A,int B){
		return dis[A]>dis[B];
	}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
	for(int i=2;i<=n*2;++i){
		dis[i]=INF;vis[i]=0;
	}
	vis[1]=1,dis[1]=0;
	q.push(1);
	int p;
	while(!q.empty()){
		p=q.top();q.pop();vis[p]=0; 
		for(int i=h[p];i;i=e[i].nxt){
			if(dis[e[i].v]>dis[p]+e[i].w){
				dis[e[i].v]=dis[p]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
				}
			}
		}
	}
}
inline void dfs0(int X){
	for(int i=g[X];i;i=te[i].nxt){
		if(te[i].v==f[X][0]){
			continue;
		}
//		printf("%d %d\n",X,te[i].v);
		f[te[i].v][0]=X;
		for(int j=1;j<=18;++j){
			f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
		}
		dfs0(te[i].v);
		dis[X]=Min(dis[X],dis[te[i].v]);
	}
}
inline int qry(int X,int D){
	for(int i=18;i>=0;--i){
		if(val[f[X][i]]>D){
			X=f[X][i];
		}
	}
	return dis[X];
}
void init(){
	scanf("%d%d",&n,&m);
	et=tet=0;
	for(int i=1;i<=n*2;++i){
		g[i]=h[i]=0;
	}
	int u,v,w,a;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d%d",&u,&v,&w,&a);
		add(u,v,w,a);
		lst[i]=(data){u,v,a};
	}
	std::sort(lst+1,lst+1+m,cmp);
	for(int i=1;i<=n*2;++i){
		ff[i]=i;val[i]=INF;
	}
	kruskal();
	dij();
	dfs0(rt);
//	for(int i=1;i<=rt;++i){
//		printf("%d ",dis[i]);
//	}
//	puts("");
	int Q,K,S,lans=0,x,d;
	scanf("%d%d%d",&Q,&K,&S);
	for(int i=1;i<=Q;++i){
		scanf("%d%d",&x,&d);
		x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
		printf("%d\n",lans=qry(x,d));
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}

lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树,我们可能可以想到用LCT来维护。但是代码难度太高,而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作,也就是说,每一次,我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树,我们暴力更新其中的每一个节点。于是可以证明,每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意:主席树的L,R本身就是节点位置;合并的时候要记得更新小树的根节点;返回的值是第k大的值而非第k大的排名因而要逆离散化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}