正題

---

題目大意

$n$只叫龍，$m$個操作。每只叫龍有種類$(0/1)$和攻擊力。

修改某只叫龍的攻擊力

取出$l～r$只叫龍，然后將連續的種類為$01$的叫龍消滅只到沒有連續的$01$為止，求剩下的叫龍中攻擊力最高是多少

---

解題思路

初始時只有一個節點，按順序枚舉叫龍，如果是$0$就新建一個節點和邊向下，如果是$1$就新建一條邊回到父節點。這樣我們就構建好了一棵樹，然后我們可以發現我們每次詢問都是兩條邊，對答案有影響的一定是這兩條邊之間的路徑，所以我們可以用樹鏈剖分來進行修改和查詢。

整體的細節有億點多，這里放一下$XXY$大佬的$blog$。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> 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[top[y]]) swap(x,y),flag^=1;if(flag)ans=max(ans,Up.Ask(1,1,cnt,seg[top[x]],seg[x]));else ans=max(ans,Down.Ask(1,1,cnt,seg[top[x]],seg[x]));x=fa[top[x]];}if(dep[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; //250Mchar*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));}}} }

總結

以上是生活随笔為你收集整理的nssl1489-大冰隙2【树链剖分,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。