【BZOJ1969】【AHOI2005】LANE航线规划【离线、hash、并查集、树链剖分、线段树】

Description

星际空间站的Samuel II巨型计算机经过长期探测&＃xff0c;已经锁定了Samuel星系中许多星球的空间坐标&＃xff0c;并对这些星球从1开始编号1、2、3……。 一些先遣飞船已经出发&＃xff0c;在星球之间开辟探险航线。 探险航线是双向的&＃xff0c;例如从1号星球到3号星球开辟探险航线&＃xff0c;那么从3号星球到1号星球也可以使用这条航线。 例如下图所示&＃xff1a; 在5个星球之间&＃xff0c;有5条探险航线。 A、B两星球之间&＃xff0c;如果某条航线不存在&＃xff0c;就无法从A星球抵达B星球&＃xff0c;我们则称这条航线为关键航线。

显然上图中&＃xff0c;1号与5号星球之间的关键航线有1条&＃xff1a;即为4-5航线。 然而&＃xff0c;在宇宙中一些未知的磁暴和行星的冲撞&＃xff0c;使得已有的某些航线被破坏&＃xff0c;随着越来越多的航线被破坏&＃xff0c;探险飞船又不能及时回复这些航线&＃xff0c;可见两个星球之间的关键航线会越来越多。 假设在上图中&＃xff0c;航线4-2&＃xff08;从4号星球到2号星球&＃xff09;被破坏。此时&＃xff0c;1号与5号星球之间的关键航线就有3条&＃xff1a;1-3&＃xff0c;3-4&＃xff0c;4-5。 小联的任务是&＃xff0c;不断关注航线被破坏的情况&＃xff0c;并随时给出两个星球之间的关键航线数目。现在请你帮助完成。

Input

第一行有两个整数N&＃xff0c;M。表示有N个星球&＃xff08;1

Output

对每个C为1的询问&＃xff0c;输出一行一个整数表示关键航线数目。 注意&＃xff1a;我们保证无论航线如何被破坏&＃xff0c;任意时刻任意两个星球都能够相互到达。在整个数据中&＃xff0c;任意两个星球之间最多只可能存在一条直接的航线。

题解

　　感觉这题非常好啊。

　　一开始非常zz地在不是很会写&＃xff0c;一直在思考并查集怎么做分离&＃xff0c;不过一看到题解&＃xff0c;就感受到了树链剖分的妙处啊。
　　
　　我们假设一开始只有一棵树&＃xff0c;那么显然每条边都是关键路线。然后我们考虑加上一条边时&＃xff0c;一定会形成一个环&＃xff0c;这样这个环上的每条边都不是关键路径了。因为是统计两个点之间的关键路径数量&＃xff0c;所以直接用0、1来表示是否为关键路径&＃xff0c;最后只需统计路径和即可。到这里&＃xff0c;可以显然地看出树链剖分了。用线段树在链上做区间覆盖和区间求和即可。
　　
　　不过我们怎么变成上述的模型呢&＃xff1f;只需离线处理&＃xff0c;先将所有的边都读入&＃xff0c;不过怎么记录被删除的边呢&＃xff1f;这里又可以使用hash法&＃xff0c;将边hash成数字&＃xff08;通过所连接的点随便搞搞出一个独特的值&＃xff09;&＃xff0c;在map的帮助下表示这条边有没有被摧毁。所以全部读入完后我们还剩一些边&＃xff0c;用并查集来建树。然后反向操作一开始记录的读入&＃xff0c;往树上加边就是一个区间覆盖。
　　
　　这样&＃xff0c;这题的思路就非常地显然了。

代码

#include
#include
#include
#include#define N 30010
#define M 100010
#define C 40010
using namespace std;map <int,bool> hash;
int f[N];
struct node1{int x,y;}edge[M],not_tree[M];
struct node2{int to,next;}e[M*2];
int head[N],tot,t,tim,n;
int dep[N],fa[N],top[N],son[N],size[N],tid[N];
int x[C],y[C],opt[C],ans[C];void init() {tot &＃61; 0;//the number of ok edget &＃61; 0; tim &＃61; 0;memset(son,-1,sizeof(son));memset(head,0,sizeof(head));
}int find(int x) { return x &＃61;&＃61; f[x] ? x : f[x] &＃61; find(f[x]); }void add_edge(int from,int to) {e[&＃43;&＃43;tot].next &＃61; head[from]; head[from] &＃61; tot; e[tot].to &＃61; to;
}void dfs1(int v,int pa,int d)
{dep[v] &＃61; d; fa[v] &＃61; pa; size[v] &＃61; 1;for(int i &＃61; head[v];i;i&＃61;e[i].next)if(e[i].to !&＃61; pa) {dfs1(e[i].to,v,d&＃43;1);size[v] &＃43;&＃61; size[e[i].to];if(son[v] &＃61;&＃61; -1 || size[e[i].to] > size[son[v]])son[v] &＃61; e[i].to;}
}void dfs2(int v,int tp)
{top[v] &＃61; tp; tid[v] &＃61; &＃43;&＃43;tim;if(son[v] &＃61;&＃61; -1) return;dfs2(son[v],tp);for(int i &＃61; head[v];i;i&＃61;e[i].next) {if(e[i].to !&＃61; son[v] && e[i].to !&＃61; fa[v])dfs2(e[i].to,e[i].to);}
}#define lson o <<1
#define rson o <<1 | 1
int sum[N <<2],setv[N <<2];void build(int o,int l,int r)
{setv[o] &＃61; -1;if(l &＃61;&＃61; r) {sum[o] &＃61; 1; if(l &＃61;&＃61; 1) sum[o] &＃61; 0; return;}int mid &＃61; (l&＃43;r)>>1;build(lson,l,mid); build(rson,mid&＃43;1,r);sum[o] &＃61; sum[lson] &＃43; sum[rson];
}void pushdown(int o)
{if(setv[o] !&＃61; -1) {setv[lson] &＃61; setv[rson] &＃61; 0;sum[lson] &＃61; sum[rson] &＃61; 0;setv[o] &＃61; -1;}
}void update(int o,int l,int r,int ll,int rr)
{if(ll <&＃61; l && rr >&＃61; r) {sum[o] &＃61; setv[o] &＃61; 0;return;}pushdown(o);int mid &＃61; (l&＃43;r)>>1;if(ll <&＃61; mid) update(lson,l,mid,ll,rr);if(rr > mid) update(rson,mid&＃43;1,r,ll,rr);sum[o] &＃61; sum[lson] &＃43; sum[rson];
}void change(int x,int y)
{while(top[x] !&＃61; top[y]) {if(dep[top[x]] 1,1,n,tid[top[x]],tid[x]);x &＃61; fa[top[x]];}if(dep[x] > dep[y]) swap(x,y);update(1,1,n,tid[x]&＃43;1,tid[y]);
}int query(int o,int l,int r,int ll,int rr)
{if(ll <&＃61; l && rr >&＃61; r) return sum[o];int mid &＃61; (l&＃43;r)>>1,ans &＃61; 0;pushdown(o);if(ll <&＃61; mid) ans &＃43;&＃61; query(lson,l,mid,ll,rr);if(rr > mid) ans &＃43;&＃61; query(rson,mid&＃43;1,r,ll,rr);return ans;
}int ask(int x,int y)
{int ans &＃61; 0;while(top[x] !&＃61; top[y]) {if(dep[top[x]] 1,1,n,tid[top[x]],tid[x]);x &＃61; fa[top[x]];}if(dep[x] > dep[y]) swap(x,y);ans &＃43;&＃61; query(1,1,n,tid[x]&＃43;1,tid[y]);return ans;
}int main()
{int m,q;scanf("%d%d",&n,&m);for(int i &＃61; 1;i <&＃61; m;i&＃43;&＃43;) {scanf("%d%d",&edge[i].x,&edge[i].y);if(edge[i].x > edge[i].y) swap(edge[i].x,edge[i].y);}q &＃61; 0;while(scanf("%d",&opt[&＃43;&＃43;q]) && opt[q] !&＃61; -1) {scanf("%d%d",&x[q],&y[q]);if(x[q] > y[q]) swap(x[q],y[q]);if(opt[q] &＃61;&＃61; 0) hash[ (x[q]-1)*n&＃43;y[q] ] &＃61; true;}for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;) f[i] &＃61; i;init();for(int i &＃61; 1;i <&＃61; m;i&＃43;&＃43;){int now &＃61; (edge[i].x-1)*n&＃43;edge[i].y;if(hash[now]) continue;int f1 &＃61; find(edge[i].x),f2 &＃61; find(edge[i].y);if(f1 !&＃61; f2) {add_edge(edge[i].x,edge[i].y); add_edge(edge[i].y,edge[i].x);f[f1] &＃61; f2;}else {not_tree[&＃43;&＃43;t].x &＃61; edge[i].x;not_tree[t].y &＃61; edge[i].y;}}dfs1(1,0,0); dfs2(1,1);build(1,1,n);for(int i &＃61; 1;i <&＃61; t;i&＃43;&＃43;) change(not_tree[i].x,not_tree[i].y);for(int i &＃61; q-1;i >&＃61; 1;i--)if(opt[i] &＃61;&＃61; 0) change(x[i],y[i]); else ans[i] &＃61; ask(x[i],y[i]);for(int i &＃61; 1;i if(opt[i]) printf("%d\n",ans[i]);return 0;
}