资源站 wordpress,番禺区网站建设哪家好,说明电子商务网站的建设流程,成都哪家公司做网站最好一道神题#xff0c;两种神做法。 Description 捉迷藏 Jiajia和Wind是一对恩爱的夫妻#xff0c;并且他们有很多孩子。某天#xff0c;Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特#xff0c;由N个屋子和N-1条双向走廊组成#xff0c;这N-1条走… 一道神题两种神做法。 Description 捉迷藏 Jiajia和Wind是一对恩爱的夫妻并且他们有很多孩子。某天Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特由N个屋子和N-1条双向走廊组成这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的孩子们负责躲藏Jiajia负责找而Wind负责操纵这N个屋子的灯。在起初的时候所有的灯都没有被打开。每一次孩子们只会躲藏在没有开灯的房间中但是为了增加刺激性孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性Jiajia希望知道可能的最远的两个孩子的距离即最远的两个关灯房间的距离。 我们将以如下形式定义每一种操作 C(hange) i 改变第i个房间的照明状态若原来打开则关闭若原来关闭则打开。 G(ame) 开始一次游戏查询最远的两个关灯房间的距离。 Input 第一行包含一个整数N表示房间的个数房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q表示操作次数。接着Q行每行一个操作如上文所示。 Output 对于每一个操作Game输出一个整数表示最远的两个关灯房间的距离。若只有一个房间是关着灯的输出0若所有房间的灯都开着输出-1。 Sample Input 8 1 2 2 3 3 4 3 5 3 6 6 7 6 8 7 G C 1 G C 2 G C 1 G Sample Output 4 3 3 4 HINT N ≤100000, M ≤500000。 Solution 一道很好的裸题可以让你初步了解括号序列和动态点分治的用法。 先说说比较好理解的动态点分治吧 动态点分治顾名思义就是将点分治加上修改操作权值修改等并支持在线询问。 这里说的动态不是完全动态至少树的整个形态是要提前知道的。 我们仔细想想最基本的点分治怎么做 在当前的分治结构里把所有的点到分治根结点的距离处理出来每两条不在同一棵子树内的距离构成一条链。 因此找经过分治根结点的最长的一条链就是到分治根结点的最长距离加上次长距离。当然这两个距离不能在同一棵子树内。你懂的。 然后怎么让这个点分治“动”起来当然是选择数据结构啊。 清点一下我们要维护的信息有 ①分治结构中分治根结点的某个子树内所有的点到分治根结点的距离目标是求最大值 ②由①得出的分治结构中分治根结点的每个子树内的距离最大值目标是求最大值和次大值 ③由②得出的每个分治结构中过分治根结点的链的长度目标是求最大值即答案。 都是维护单点修改求整体最值用什么线段树当然是堆啊 你可能会对①产生疑问一个分治根结点难道要维护它的所有子树的距离信息一个结点开多个堆 当然不是啊反过来想改成维护该分治结构中所有的点到分治父节点的距离就完美解决了上面的问题。 除了“维护什么”还有“怎么维护”。 这是一个典(sang)型(bing)的维护堆套堆套堆从最低一级的堆开始每次堆顶有变就要往上一级更新小C不再赘述。 手写堆可能会写得你欲仙欲死这时候需要想办法用上PQ。如果你是Pascal党当我没说 PQ是无法对堆内部的节点进行修改的所以我们需要一些经典Trick。 用两个堆来表示一个用来存节点一个用来打删除标记。每次取top的时候把打了删除标记的堆顶清理一下。 取次大的就把最大pop掉再push进来即可。这些具体可以看小C的代码。 说完“怎么维护”还有“为什么可以这样维护”。 动态点分治的时空复杂度是以点分治为基础的由于分治根结点都是重心。每个结点最多只会出现在log个分治结构中。 由于所有的信息都要维护空间和时间复杂度起步都是O(nlogn)。 如果要开线段树就要动态开点空间复杂度O(nlog2n)这时就需要注意空间上的限制了。 所以无需注意标号和空间占用小的灵活的堆成为了很好的选择。 空间复杂度O(nlogn)时间复杂度O(nlog2n)。 发张图轻松一下~~ 接着小C来讲讲神一般的括号序列做法 我们先引入一个大佬的博客http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-捉迷藏/ 括号序列是什么你只要写过树剖就会很熟悉。因为括号序列本身就是由dfs序的开头和结尾组成的。 dfs的开头作为左括号结尾作为右括号节点编号紧挨着左括号。 如下图可以表示为[1[2[3][5[4]]]]。 然后这样表示有什么用呢括号序列的作用之一就是可以配合线段树查询两点之间即一条链上的信息。 询问点对(1,4)的距离1、4之间的括号串为“[2[3][5[” 去掉数字“[[][[”再去掉匹配的括号“[[[”右括号代表向上左括号代表向下 这也就意味着节点1向下走3步就可以走到节点4。 所以树上任意两点间的距离可以用数对(a,b)表示其中a为失配的右括号数b为失配的左括号数则两点间距离为ab。 每一段括号序列都有它的(a,b)也就是说只要求出两点间的括号序列的ab即为距离。 现在进入正题了如何用线段树求ab呢 考虑左(a1,b1)右(a2,b2)两个区间合并若b1a2则为(a1a2-b1,b2)若b1a2则为(a1,b2b1-a2)。 由此我们从已知a1,b1,a2,b2可以得出以下关于新区间(a,b)的显而易见的等式 ① ② ③ 我们发现新的ab和a-b都是由旧的ab和a-b通过加减运算得来。 所以设一段括号序列的ab为plusa-b为minus1b-a为minus2。 进一步题目要我们求的是两个黑点之间的ab我们同样可以通过维护以下信息求得 ①sum表示区间中两个黑点之间的括号序列的ab的最大值 ②left_plus表示区间中一个黑点左侧的括号序列的ba的最大值 ③left_minus表示区间中一个黑点左侧的括号序列的b-a的最大值 ④right_plus表示区间中一个黑点右侧的括号序列的ab的最大值 ⑤right_minus表示区间中一个黑点右侧的括号序列的a-b的最大值 注意上面的变量如果不存在即黑点数不足时都要设为-INF。 剩下的就是各种区间的合并“两点之间”、“左侧”、“右侧”实际上都是区间根据上面的等式可以很容易求得 ① ② ③ ④ ⑤ 然后就开开心心地写一写线段树就可以了啊。 时间复杂度O(nlogn)比动态点分治快到不知道那里去。 动态点分治 #include cstdio
#include cstring
#include algorithm
#include queue
#include vector
#define INF 0x3FFFFFFF
#define MN 100005
using namespace std;
struct queue
{priority_queue int A,B;void push(int x) {if (x!-INF) A.push(x);}void delet(int x) {if (x!-INF) B.push(x);}int top(){while (!B.empty()A.top()B.top()) A.pop(),B.pop();if (!A.empty()) return A.top(); else return -INF;}int two(){if (A.size()-B.size()2) return -INF;register int x,y;xtop(); A.pop(); ytop(); A.push(x); return xy;}
}q[MN],q1[MN],q2;
struct edge{int nex,to;}e[MN1];
vector int td[MN];
int siz[MN],hr[MN],fa[MN];
int mnz,mni,n,m,pin,gs;
bool bj[MN],hu[MN];inline int read()
{int n0,f1; char cgetchar();while (c0 || c9) {if(c-)f-1; cgetchar();}while (c0 c9) {nn*10c-0; cgetchar();}return n*f;
}inline void ins(int x,int y) {e[pin](edge){hr[x],y}; hr[x]pin;}
void getsiz(int x,int fat)
{siz[x]1;for (register int ihr[x];i;ie[i].nex)if (e[i].to!fat!bj[e[i].to])getsiz(e[i].to,x),siz[x]siz[e[i].to];
}
void getdp(int x,int fat,int depth,int dest)
{q[dest].push(depth);td[x].push_back(depth);for (register int ihr[x];i;ie[i].nex)if (e[i].to!fat!bj[e[i].to])getdp(e[i].to,x,depth1,dest);
}
void getrt(int x,int fat,int tot)
{register int i,mxz0;for (ihr[x];i;ie[i].nex){if (e[i].tofat||bj[e[i].to]) continue;getrt(e[i].to,x,tot);mxzmax(mxz,siz[e[i].to]);}mxzmax(mxz,tot-siz[x]);if (mxzmnz) mnzmxz,mnix;
}void dfs(int x,int fat)
{bj[x]true; fa[x]fat;q1[x].push(0);for (register int ihr[x];i;ie[i].nex){if (bj[e[i].to]) continue;getsiz(e[i].to,x); mnzn; getrt(e[i].to,x,siz[e[i].to]);getdp(e[i].to,x,1,mni);q1[x].push(q[mni].top());dfs(mni,x);}q2.push(q1[x].two());
}void setrev(int x)
{register int ck,nck,cck,ncck,y,i;ckq1[x].two();if (hu[x]) q1[x].delet(0); else q1[x].push(0);nckq1[x].two();if (ck!nck) q2.delet(ck),q2.push(nck);for (yx,itd[x].size()-1;fa[y];yfa[y],--i){ckq[y].top();if (hu[x]) q[y].delet(td[x][i]); else q[y].push(td[x][i]);nckq[y].top();if (cknck) continue;cckq1[fa[y]].two();q1[fa[y]].delet(ck); q1[fa[y]].push(nck);ncckq1[fa[y]].two();if (cck!ncck) q2.delet(cck),q2.push(ncck);}
}int main()
{register int i,x,y;char c[5];nread();for (i1;in;i){xread(); yread();ins(x,y); ins(y,x);}for (i1;in;i) hu[i]true;getsiz(1,0); mnzn; getrt(1,0,n); dfs(mni,0);mread(); gsn;while (m--){scanf(%s,c);if (c[0]C){xread(); setrev(x);gshu[x]?-1:1; hu[x]^1;}else if (c[0]G)if (gs0) puts(-1);else if (gs1) puts(0);else printf(%d\n,q2.top());}
} 括号序列画风略清奇 #include cstdio
#include algorithm
#include cstring
#define l(a) (a1)
#define r(a) (a1|1)
#define O(a) (a!-INF)
#define INF 100000007
#define MM 800005
#define MN 200005
using namespace std;
struct node{int lpl,lmi,rpl,rmi,sum;}T[MM];
struct meg{int x,y;}t[MM];
struct edge{int nex,to;}e[MN];
bool u[MN];
int kh[MN][2],hr[MN];
int dfn,n,m,pin,gs;inline int read()
{int n0,f1; char cgetchar();while (c0 || c9) {if(c-)f-1; cgetchar();}while (c0 c9) {nn*10c-0; cgetchar();}return n*f;
}inline void ins(int x,int y) {e[pin](edge){hr[x],y}; hr[x]pin;}
void dfs(int x,int fat)
{u[kh[x][0]dfn]true;for (register int ihr[x];i;ie[i].nex)if (e[i].to!fat) dfs(e[i].to,x);kh[x][1]dfn;
}void update(node C,const node A,const node B,const meg a,const meg b)
{C.summax(A.sum,B.sum); if (O(A.lpl)O(B.lpl)) C.summax(C.sum,max(A.rplB.lmi,A.rmiB.lpl));C.lplA.lpl; if (O(B.lpl)) C.lplmax(C.lpl,max(B.lpl-a.ya.x,B.lmia.ya.x));C.rplB.rpl; if (O(A.lpl)) C.rplmax(C.rpl,max(A.rpl-b.xb.y,A.rmib.xb.y));C.lmiA.lmi; if (O(B.lpl)) C.lmimax(C.lmi,B.lmia.y-a.x);C.rmiB.rmi; if (O(A.lpl)) C.rmimax(C.rmi,A.rmib.x-b.y);
}
inline void setin(int x) {T[x].lplT[x].lmi1; T[x].rplT[x].rmi0;}
inline void setout(int x) {T[x].lplT[x].lmiT[x].rplT[x].rmi-INF;}
void getcg(int x,int L,int R,int q)
{ if (LR) {if (O(T[x].lpl)) setout(x); else setin(x); return;}int midLR1;if (qmid) getcg(l(x),L,mid,q); else getcg(r(x),mid1,R,q);update(T[x],T[l(x)],T[r(x)],t[l(x)],t[r(x)]);
}
void build(int x,int L,int R)
{if (LR){T[x].sum-INF;if (!u[L]) t[x].x1,setout(x); else t[x].y1,setin(x);return;}int midLR1;build(l(x),L,mid); build(r(x),mid1,R);t[x].xt[l(x)].x; t[x].yt[r(x)].y;if (t[l(x)].yt[r(x)].x) t[x].xt[r(x)].x-t[l(x)].y;else if (t[l(x)].yt[r(x)].x) t[x].yt[l(x)].y-t[r(x)].x;update(T[x],T[l(x)],T[r(x)],t[l(x)],t[r(x)]);
}int main()
{register int i,x,y;char c[5];nread();for (i1;in;i){xread(); yread();ins(x,y); ins(y,x);}dfs(1,0); build(1,1,n1); gsn; mread();while (m--){scanf(%s,c);if (c[0]C){xread(); gsu[kh[x][0]]?-1:1;u[kh[x][0]]^1; getcg(1,1,n1,kh[x][0]);}else if (c[0]G)if (gs1) puts(0);else if (gs0) puts(-1);else printf(%d\n,T[1].sum);}
} Last Word 动态点分治写起来就像吃了那啥一样难受还好最后把代码压缩到小C容易接受的地步。 括号序列是真的厉害不知道以后能不能看到它更多的妙用。转载于:https://www.cnblogs.com/ACMLCZH/p/7465161.html
