淘宝网站建设的详细策划,图书馆新生专栏网站建设,网站建设运营的灵魂是,做爰全过程的视频的网站正题 题目大意 nnn只叫龙#xff0c;mmm个操作。每只叫龙有种类(0/1)(0/1)(0/1)和攻击力。
修改某只叫龙的攻击力取出l∼rl\sim rl∼r只叫龙#xff0c;然后将连续的种类为010101的叫龙消灭只到没有连续的010101为止#xff0c;求剩下的叫龙中攻击力最高是多少 解题思路
初…正题 题目大意
nnn只叫龙mmm个操作。每只叫龙有种类(0/1)(0/1)(0/1)和攻击力。
修改某只叫龙的攻击力取出l∼rl\sim rl∼r只叫龙然后将连续的种类为010101的叫龙消灭只到没有连续的010101为止求剩下的叫龙中攻击力最高是多少 解题思路
初始时只有一个节点按顺序枚举叫龙如果是000就新建一个节点和边向下如果是111就新建一条边回到父节点。这样我们就构建好了一棵树然后我们可以发现我们每次询问都是两条边对答案有影响的一定是这两条边之间的路径所以我们可以用树链剖分来进行修改和查询。
整体的细节有亿点多这里放一下XXYXXYXXY大佬的blogblogblog。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
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(LR){w[x]val;return;} int mid(LR)1;if(posmid)Change(x*2,L,mid,pos,val);else Change(x*21,mid1,R,pos,val);w[x]max(w[x*2],w[x*21]);return;}int Ask(int x,int L,int R,int l,int r){if(lr)return 0;if(LlRr)return w[x];int mid(LR)1;if(rmid)return Ask(x*2,L,mid,l,r);if(lmid)return Ask(x*21,mid1,R,l,r);return max(Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r));}
}Up,Down;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;fa[y]x;return;
}
void dfs1(int x){siz[x]1;for(int ils[x];i;ia[i].next){int ya[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 ils[x];i;ia[i].next){int ya[i].to;if(yson[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)ansmax(ans,Up.Ask(1,1,cnt,seg[top[x]],seg[x]));else ansmax(ans,Down.Ask(1,1,cnt,seg[top[x]],seg[x]));xfa[top[x]];}if(dep[x]dep[y]) swap(x,y);else flag^1;if(flag)ansmax(ans,Up.Ask(1,1,cnt,seg[son[x]],seg[y]));else ansmax(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 i1;in;i)scanf(%d,b[i]);for(int i1;in;i)scanf(%d,c[i]);rootnowcnt;for(int i1;in;i){if(b[i]){pid[i]now;upw[now]c[i];if(!fa[now]){addl(cnt,now);fa[now]cnt;rootnowcnt;}else nowfa[now];}else{addl(now,cnt);nowpid[i]cnt;dow[now]c[i];}}top[root]root;dfs1(root);dfs2(root);for(int i1;im;i){int op,l,r;scanf(%d%d%d,op,l,r);if(op1)Updata(l,b[l],r);else{if(lrpid[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)lfa[pid[l]];else lpid[l];if(b[r]1)rfa[pid[r]];else rpid[r];printf(%d\n,Query(l,r,1));}}}
}
