本文共 2914 字，大约阅读时间需要 9 分钟。

正题

题目大意

$n$只叫龙，$m$个操作。每只叫龙有种类$(0/1)$和攻击力。

1. 修改某只叫龙的攻击力
2. 取出$l\sim r$只叫龙，然后将连续的种类为$01$的叫龙消灭只到没有连续的$01$为止，求剩下的叫龙中攻击力最高是多少

解题思路

初始时只有一个节点，按顺序枚举叫龙，如果是$0$就新建一个节点和边向下，如果是$1$就新建一条边回到父节点。这样我们就构建好了一棵树，然后我们可以发现我们每次询问都是两条边，对答案有影响的一定是这两条边之间的路径，所以我们可以用树链剖分来进行修改和查询。

整体的细节有亿点多，这里放一下$XXY$大佬的。

$code$

#include
   
    #include
    
     #include
     
      using namespace std;const int N=1e5+10;struct node{
   	int to,next;}a[N*2];int n,m,cnt,tot,root,num,ls[N],fa[N];int b[N],c[N],upw[N],dow[N],pid[N];int seg[N],id[N],dep[N],siz[N],son[N],top[N];struct Seq_Tree{
   	int w[N*4];	void Change(int x,int L,int R,int pos,int val){
   		if(L==R){
   			w[x]=val;			return;		} 		int mid=(L+R)>>1;		if(pos<=mid)Change(x*2,L,mid,pos,val);		else Change(x*2+1,mid+1,R,pos,val);		w[x]=max(w[x*2],w[x*2+1]);		return;	}	int Ask(int x,int L,int R,int l,int r){
   		if(l>r)return 0;		if(L==l&&R==r)			return w[x];		int mid=(L+R)>>1;		if(r<=mid)return Ask(x*2,L,mid,l,r);		if(l>mid)return Ask(x*2+1,mid+1,R,l,r);		return max(Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r));	} }Up,Down;void addl(int x,int y){
   	a[++tot].to=y;	a[tot].next=ls[x];	ls[x]=tot;fa[y]=x;	return;}void dfs1(int x){
   	siz[x]=1;	for(int i=ls[x];i;i=a[i].next){
   		int y=a[i].to;		dep[y]=dep[x]+1;		dfs1(y);siz[x]+=siz[y];		if(siz[y]>siz[son[x]])			son[x]=y;	}	return;} void dfs2(int x){
   	seg[x]=++num;id[num]=x;	Up.Change(1,1,cnt,num,upw[x]);	Down.Change(1,1,cnt,num,dow[x]); 	if(son[x]){
   		top[son[x]]=top[x];		dfs2(son[x]);	}	for(int i=ls[x];i;i=a[i].next){
   		int y=a[i].to;		if(y==son[x])continue;		top[y]=y;dfs2(y); 	}}void Updata(int x,int z,int val){
   	if(z)Up.Change(1,1,cnt,seg[pid[x]],val);	else Down.Change(1,1,cnt,seg[pid[x]],val);}int Query(int x,int y,int flag){
   	int ans=-2147483647;	while(top[x]!=top[y])	{
   		if(dep[top[x]]
      
       dep[y]) swap(x,y);else flag^=1;	if(flag)ans=max(ans,Up.Ask(1,1,cnt,seg[son[x]],seg[y]));	else ans=max(ans,Down.Ask(1,1,cnt,seg[son[x]],seg[y]));	return ans;}int main(){
   	int size = 256 << 20; //250M	char*p=(char*)malloc(size) + size;	__asm__("movl %0, %%esp\n" :: "r"(p) );	scanf("%d%d",&n,&m);	int now;	for(int i=1;i<=n;i++)		scanf("%d",&b[i]);	for(int i=1;i<=n;i++)		scanf("%d",&c[i]);	root=now=++cnt;	for(int i=1;i<=n;i++){
   		if(b[i]){
   			pid[i]=now;			upw[now]=c[i];			if(!fa[now]){
   				addl(++cnt,now);				fa[now]=cnt;				root=now=cnt;			}			else now=fa[now];		}		else{
   			addl(now,++cnt);			now=pid[i]=cnt;			dow[now]=c[i];		}	}	top[root]=root;	dfs1(root);	dfs2(root);	for(int i=1;i<=m;i++){
   		int op,l,r;		scanf("%d%d%d",&op,&l,&r);		if(op==1)Updata(l,b[l],r);		else{
   			if(l==r&&pid[l]==pid[r])printf("%d\n",c[l]);			else if(pid[l]==pid[r]&&b[l]!=b[r])printf("0\n");			else{
   				if(b[l]==0)l=fa[pid[l]];else l=pid[l];				if(b[r]==1)r=fa[pid[r]];else r=pid[r];				printf("%d\n",Query(l,r,1));			}		}	}}
      
     
    
   

转载地址：http://rdwaf.baihongyu.com/