Soulist 的博客

—可惜当时年少

题解 P2542 【[AHOI2005]航线规划】

posted on 2019-03-21 19:34:56 | under LCT |

（那些大佬好像都写了什么缩点双还是什么的，蒟蒻瑟瑟发抖啊 $QAQ$ ）

（图中绿边）

#include<bits/stdc++.h>
using namespace std;
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') {  if( cc == '-' ) flus = -flus;  cc = getchar();  }
while(cc >= '0' && cc <= '9')  cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
#define ls(x) t[x].son[0]
#define rs(x) t[x].son[1]
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define drep( i, t, s ) for( register int i = t; i >= s; -- i )
const int N = 200000 + 5;
struct LCT {
int son[2], val, fa, cover;
bool mark;
}t[N];
struct E{
int from, to, c;
}e[N];
map< int, int > mc1;
int n, m, Opt[N], From[N], To[N], tot, w[N], Idnum, ans[N], Id[N];
void pushup( int x ) {
t[x].val = t[ls(x)].val + t[rs(x)].val + w[x];
}
void push( int x ) { //cover表示覆盖标记，如果有覆盖标记，则此点的w值应改为0，且整棵子树都要被改为0
// 所以还要修改t[x].val = 0
w[x] = 0, t[x].cover = 1, t[x].val = 0;
}
void pushmark( int x ) {
if( t[x].cover ) // 下传标记
t[x].cover = 0, push( ls(x) ), push( rs(x) ), t[x].val = 0;
if( t[x].mark )
t[x].mark = 0, t[ls(x)].mark ^= 1, t[rs(x)].mark ^= 1, swap( ls(x), rs(x) );
}
bool isroot( int x ) {
return ( rs(t[x].fa) != x ) && ( ls(t[x].fa) != x );
}
void rotate( int x ) {
int f = t[x].fa, ff = t[f].fa, qwq = ( rs(f) == x );
t[x].fa = ff;
if( !isroot(f) ) t[ff].son[rs(ff) == f] = x;
t[t[x].son[qwq ^ 1]].fa = f, t[f].son[qwq] = t[x].son[qwq ^ 1];
t[x].son[qwq ^ 1] = f, t[f].fa = x;
pushup(f), pushup(x);
}
int st[N];
void Splay( int x ) {
int top = 0, now = x; st[++top] = now;
while( !isroot(now) ) st[++top] = ( now = t[now].fa );
while( top ) pushmark( st[top--] );
while( !isroot(x) ) {
int f = t[x].fa, ff = t[f].fa;
if( !isroot(f) ) ( ( rs(ff) == f ) ^ ( rs(f) == x ) ) ? rotate(x) : rotate(f);
rotate(x);
}
}
void access( int x ) {
for( int y = 0; x; y = x, x = t[y].fa )
Splay(x), t[x].son[1] = y, pushup(x);
}
void makeroot( int x ) {
access( x ), Splay( x ), t[x].mark ^= 1, pushmark( x );
}
int findroot( int x ) {
access( x ), Splay( x ), pushmark( x );
while( ls(x) ) pushmark( x = ls(x) );
return x;
}
void split( int x, int y ) {
makeroot(x), access(y), Splay(y);
}
void link( int x, int y ) {
makeroot( x );
if( findroot(y) != x ) t[x].fa = y;
}
bool check( int x, int y ) {
makeroot( x );
return findroot(y) == x;
}
void input() {
rep( i, 1, m ) {
if( e[i].from > e[i].to ) swap( e[i].from, e[i].to ); //swap, 方便统计
mc1[e[i].from * ( n + 1 ) + e[i].to] = i, w[i + n] = 1; //拆边，每条边的编号都是i+n，
//同时在map内记录，方便查初始有那些边存在
}
while( 1 ) {
if( Opt[tot] == -1 ) break;
if( Opt[tot] == 0 ) {
if( From[tot] > To[tot] ) swap( From[tot], To[tot] );
Id[tot] = mc1[From[tot] * ( n + 1 ) + To[tot]];
e[Id[tot]].c = 1; //标记这条边被用过了
}
}
}
signed main()
{
input(); //读入函数
rep( i, 1, m ) {
if( !e[i].c ) { //若这条边没有被用过
int u = e[i].from, v = e[i].to;
if( check( u, v ) )  split( u, v ), push(v); //如果u，v 在一个联通块内，则拉出u到v的链，然后打上标记
else link( e[i].from, i + n ), link( i + n, e[i].to ); //否则直接连边
}
}
drep( i, tot - 1, 1 ) {
if( Opt[i] == 0 ) { //如果是0，就是连边操作，与前面类似
int u = From[i], v = To[i];
if( check( u, v ) )  split( From[i], To[i] ), push(To[i]);
else link( From[i], Id[i] + n ), link( Id[i] + n, To[i] );
}
if( Opt[i] == 1 ) //否则就是询问，直接split然后统计答案
split( From[i], To[i] ), ans[++Idnum] = t[To[i]].val;
}
drep( i, Idnum, 1 ) printf("%d\n", ans[i]);
return 0;
}