题目
点这里看题目。
分析
面对这种题还没有什么经验……
Subtask 1
暴力删暴力判，复杂度为 \(O((n+m)q)\)。
Subtask 2
尝试优化一下暴力。
尝试将 \(O((n+m)q)\) 变成 \(O((n+m)m)\)。之所以会判 \(q\) 次，主要在于纯暴力会对已经确定为 0 的边重复判断。然而，如果一条边已经删不了了，在此之后又不会新增边，所以如果之后又遇到它，肯定还是删不了。所以每条边只需要检查 1 次即可判定状态。
Subtask 3
好奇怪，为什么我妹想到？
我们没有必要在线处理问题，因为这必然意味着在线处理连通性，是我们暂时无法完成的。
先把所有重复的 \(x\) 处理掉：对于同一 \(x\)，只有第一次出现的位置有判断价值，其后必然全为 0。之后我们可以二分找出没有被删的那条边。
Remark.
主要还是自己完全是在线的思路，根本没有意识到可以离线解决。
从离线的角度来看，这其实就是将时间排扁成一维信息的常规思路。
当然，用二分进行查找的方法也应该熟悉。
Subtask 4
类似于 Subtask 3，当我们找出第一条之后，我们也可以找出第二条、第三条……
正解
将上面的思路拓展，我们干的事情是就是反复使用二分找出所有的 0 边，不妨设这些边为 \(e_1,e_2,\dots,e_k\)。
但再深入思考一下：当我们找到 \(e_1\)，由于更早的边都已被删除，之后有效的路径必然满足每一条边的删除时间都不早于 \(e_1\) 的时间。类似地，找到 \(e_2\) 时，限制就变成了路径上最早被删除的边的删除时间不早于 \(e_1\) 的时间，次早被删除的边的删除时间不早于 \(e_2\) 的时间，依此类推。
根据 \(e_1,e_2,\dots,e_k\) 的性质，我们可以推知最终剩下来的路径，都必须最小化路径上边的删除时间从小到大排序后的字典序。字典序可以对应，所以可以赋权并尝试和最短路模型联系起来，如果一条边从未被删除，则其权为 \(0\)（可以认为是 \(2^{-\infty}\)）；否则，若在第 \(t\) 次操作中第一次被删除，则其权为 \(2^{q-t}\)。
Remark.
文字描述显得比较抽象。实际上想像动态删边的过程就可以很好地理解这个过程了。
另外值得提醒的——综合考虑已有条件。
暴力计算最短路复杂度为 \(O(m^2\log m)\)，瓶颈在于比较最短路的长度。既然无法直接用“权”比较，我们就只能考虑路径本身了。当我们把所有路径拉出来的时候，我们知道会有一棵最短路树，并且最短路树可以反映路径之间的公共部分和非公共部分。路径权值的差别必然出现在非公共部分，而最短路是到根的路径，所以比较 \(u,v\) 的最短路长度时，我们可以直接比较非公共树链。更进一步地，由于非 \(0\) 边权互不相同，所以我们比较最高位——也就是指数的 \(\max\)——即可判断大小关系。
Dijkstra 过程中树会动态扩增，所以需要用倍增维护，复杂度为 \(O(m\log n\log m)\)。
代码
#include <cmath>
#include <cstdio>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
const int INF = 1e9;
const int MAXN = 2e5 + 5, MAXLOG = 18;
template<typename _T>
inline void Read( _T &x ) {
x = 0; char s = getchar(); bool f = false;
while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
if( f ) x = -x;
}
template<typename _T>
inline void Write( _T x ) {
if( x < 0 ) putchar( '-' ), x = -x;
if( 9 < x ) Write( x / 10 );
putchar( x % 10 + '0' );
}
template<typename _T>
inline _T Min( const _T &a, const _T &b ) {
return a < b ? a : b;
}
template<typename _T>
inline _T Max( const _T &a, const _T &b ) {
return a > b ? a : b;
}
struct Edge {
int to, nxt, w;
} Graph[MAXN << 1];
int tre[MAXN << 2], bas;
int mx[MAXLOG][MAXN], fath[MAXLOG][MAXN];
int dep[MAXN], pre[MAXN];
bool vis[MAXN], imp[MAXN];
int head[MAXN], cnt = 0;
int fr[MAXN], to[MAXN], tim[MAXN];
int rmvId[MAXN];
int N, M, Q, lg2;
inline void AddEdge( const int &from, const int &to, const int &W ) {
Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
Graph[cnt].w = W, head[from] = cnt;
}
inline void Build( const int &n ) {
for( bas = 1 ; bas < n ; bas <<= 1 );
rep( i, 1, bas ) tre[i + bas - 1] = i == 1 ? 1 : N + 1;
per( i, bas - 1, 1 ) tre[i] = tre[i << 1];
}
inline void Balance( int &u, const int &stp, int &ret ) {
for( int i = 0 ; ( 1 << i ) <= stp ; i ++ )
if( stp >> i & 1 ) ret = Max( ret, mx[i][u] ), u = fath[i][u];
}
inline bool Cmp( int x, int y, const int &v1Init = - INF, const int &v2Init = - INF ) {
if( x > N ) return false;
if( y > N ) return true;
int v1 = v1Init, v2 = v2Init;
if( dep[x] > dep[y] ) Balance( x, dep[x] - dep[y], v1 );
if( dep[x] < dep[y] ) Balance( y, dep[y] - dep[x], v2 );
if( x == y ) return v1 <= v2;
per( i, lg2, 0 ) if( fath[i][x] ^ fath[i][y] ) {
v1 = Max( mx[i][x], v1 ), x = fath[i][x];
v2 = Max( mx[i][y], v2 ), y = fath[i][y];
}
return Max( v1, mx[0][x] ) <= Max( v2, mx[0][y] );
}
inline void Upt( const int &x ) {
static int y, z; y = tre[x << 1], z = tre[x << 1 | 1];
tre[x] = Cmp( fath[0][y], fath[0][z], mx[0][y], mx[0][z] ) ? y : z;
}
inline void Update( int x ) {
tre[x + bas - 1] = x;
for( x += bas - 1 ; x >>= 1 ; Upt( x ) );
}
inline void Erase( int x ) {
tre[x + bas - 1] = N + 1;
for( x += bas - 1 ; x >>= 1 ; Upt( x ) );
}
void Dijkstra() {
Build( N ), dep[1] = 0;
rep( i, 1, N + 1 ) mx[0][i] = - INF, fath[0][i] = N + 1;
while( tre[1] <= N ) {
int u = tre[1];
Erase( u ), vis[u] = true;
dep[u] = dep[fath[0][u]] + 1;
rep( j, 1, lg2 ) {
fath[j][u] = fath[j - 1][fath[j - 1][u]];
mx[j][u] = Max( mx[j - 1][fath[j - 1][u]], mx[j - 1][u] );
}
for( int i = head[u], v ; i ; i = Graph[i].nxt )
if( ! vis[v = Graph[i].to] && Cmp( u, fath[0][v], Graph[i].w, mx[0][v] ) )
mx[0][v] = Graph[i].w, fath[0][v] = u, pre[v] = i, Update( v );
}
}
int main () {
Read( N ), Read( M ), Read( Q ), lg2 = log2( N );
rep( i, 1, M ) Read( fr[i] ), Read( to[i] ), tim[i] = - INF;
rep( i, 1, Q ) Read( rmvId[i] ), tim[rmvId[i]] = Max( tim[rmvId[i]], Q - i );
rep( i, 1, M ) AddEdge( fr[i], to[i], tim[i] );
Dijkstra();
for( int u = N ; u ^ 1 ; u = fath[0][u] ) imp[pre[u]] = true;
rep( i, 1, Q ) puts( imp[rmvId[i]] || Q - tim[rmvId[i]] < i ? "0" : "1" );
return 0;
}
原文地址：http://www.cnblogs.com/crashed/p/16909979.html
