参考论文: 郭华阳《RMQ与LCA问题》 的解法.
通过构建最小生成树,然后转换成 寻找最近公共祖先来求解, 逆序处理询问,将删除改成添加边.
代码在BZOJ上WA了.暂时未找到原因, 先放着... 不过有看到用splay, 动态树等做的..
#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<map> #include<vector> using namespace std; const int N = (int)1e5+10; const int M = (int)1e6+10; const int maxn = 5*N; int n, m, Q_num; struct node{ int a, b, t; bool operator < (const node &tmp) const{ return t < tmp.t; } }edge[M]; struct Query{ int k,a,b; }Q[N]; map< pair<int,int>, int > mp; vector<int> S[2*N+10]; int getint(){ char ch = getchar(); for(; ch > '9' || ch < '0'; ch = getchar() ); int tmp = 0; for(; ch > '0' && ch < '9'; ch = getchar() ) tmp = tmp*10 + ch - '0'; return tmp; } int st[maxn], top; bool vis[M]; int find(int x){ return st[x] == x ? x : find(st[x]); } void debug(){ printf("n = %d, m = %d, Q_num = %d\n", n, m, Q_num ); printf("Edge:\n"); for(int i = 0; i < m; i++) printf("(%d,%d,t=%d)\n", edge[i].a, edge[i].b, edge[i].t ); printf("Query:\n"); for(int i = 0; i < Q_num; i++) printf("k=%d,(%d,%d)\n", Q[i].k, Q[i].a, Q[i].b ); } void input(){ n = getint(); m = getint(); Q_num = getint(); for(int i = 0; i < m; i++){ // Edge infomation edge[i].a = getint(); edge[i].b = getint(); edge[i].t = getint(); } for(int i = 0; i < Q_num; i++){ // Query Q[i].k = getint(); Q[i].a = getint(); Q[i].b = getint(); } sort( edge, edge+m ); // sort by t desc for(int i = 0; i < m; i++) // index mp[ make_pair( edge[i].a, edge[i].b ) ] = mp[ make_pair( edge[i].b, edge[i].a ) ] = i; for(int i = 0; i < Q_num; i++){ if( Q[i].k == 2 ) vis[ mp[make_pair(Q[i].a, Q[i].b)] ] = true; } // for(int i = 0; i < m; i++) // printf("%d ", vis[i] ); puts(""); } int val[maxn]; int pos[maxn], dep[maxn], vec[maxn], idx; int dp[maxn][50]; void dfs(int u,int d){ dep[++idx] = d; vec[idx] = u; if( pos[u] == -1 ) pos[u] = idx; dep[idx] = d; for(int i = 0; i < (int)S[u].size(); i++){ dfs( S[u][i], d+1 ); dep[++idx] = d; vec[idx] = u; } } void print(){ printf("Top = %d\n", top); for(int i = 1; i <= top; i++) printf("pos[%d] = %d, val[%d] = %d\n", i, pos[i], i, val[i]); printf("idx = %d\n", idx); for(int i = 1; i <= idx; i++) printf("i = %d, vec[%d] = %d, dep[%d] = %d\n", i, i, vec[i], i, dep[i] ); } void predeal(){ for(int i = 0; i < 2*n+10; i++) st[i] = i, S[i].clear(); top = n; for(int i = 0; i < m; i++){ if( vis[ mp[ make_pair( edge[i].a, edge[i].b ) ] ] == false ){ int a = edge[i].a, b = edge[i].b, t = edge[i].t; int x = find(a), y = find(b); // printf("(%d,%d): x = %d, y = %d\n",a,b, x, y ); if( x != y ){ st[x] = st[y] = ++top; val[top] = t; S[top].push_back(x), S[top].push_back(y); } } } for(int i = 1; i <= top; i++) pos[i] = -1; idx = 0; dfs( top, 0 ); //print(); // init RMQ for(int i = 1; i <= idx; i++) dp[i][0] = i; for(int j = 1; (1<<j) <= idx; j++){ for(int i = 1; i+(1<<j)-1 <= idx; i++){ // dp[i][j] = min( dp[i][j-1], dp[i+(1<<(j-1))][j-1] ); if( dep[ dp[i][j-1] ] < dep[ dp[i+(1<<(j-1))][j-1] ] ) dp[i][j] = dp[i][j-1]; else dp[i][j] = dp[i+(1<<(j-1))][j-1]; } } } int RMQ_find(int l,int r){ int d = r-l+1, k = 0; while( (1<<(k+1)) < d ) k++; // printf("RMQ: k = %d\n", k ); // printf("RMQ: L = %d, R = %d\n", dp[l][k] , dp[r-(1<<k)+1][k] ); if( dep[ dp[l][k] ] < dep[ dp[r-(1<<k)+1][k] ] ) return dp[l][k]; return dp[ r-(1<<k)+1 ][k]; } int ans[M], ans_cnt; void solve(){ int ans_cnt = 0; predeal(); for(int i = Q_num-1; i >= 0; i-- ){ if( Q[i].k == 1 ){ int l = pos[ Q[i].a ], r = pos[ Q[i].b ]; // printf("(a=%d,b=%d),(l=%d,r=%d)\n", Q[i].a, Q[i].b, l, r); if( l > r ) swap( l, r ); int pt = RMQ_find(l,r); //printf("pt = %d\n", pt ); ans[ ans_cnt++ ] = val[ vec[pt] ]; } else{ // Q[i].k == 2 vis[ mp[ make_pair( Q[i].a,Q[i].b ) ] ] = false; predeal(); // restructrue the min genaration tree } // puts("******************************************************"); } for(int i = ans_cnt-1; i >= 0; i-- ){ printf("%d\n", ans[i] ); } } int main(){ freopen("1.in","r",stdin); input(); solve(); return 0; }