环保部网站官网建设项目审批,wordpress文章没办法显示略缩图,wordpress文章全屏,服装网站建设多少钱先不考虑数据结构部分#xff0c;尝试猜一下结论。
结论#xff1a;一个连通块有解当且仅当连通块的度数为偶数。
然后这题要你最大边权最小。最无脑的方法就是直接上 lct \text{lct} lct。真省事啊
我第一眼想到的还是整体二分。这玩意非常好写。
但是为什么也可以用线段…先不考虑数据结构部分尝试猜一下结论。
结论一个连通块有解当且仅当连通块的度数为偶数。
然后这题要你最大边权最小。最无脑的方法就是直接上 lct \text{lct} lct。真省事啊
我第一眼想到的还是整体二分。这玩意非常好写。
但是为什么也可以用线段树分治来做呢。这需要简单的分析一下性质。考虑求出每条边在哪些生成树上出现过分析可知这一定是一段区间。
然后是非常玄学的操作。考虑离线然后 倒着处理询问 真是违背常理啊这样的话一条边如果原来在生成树上那么删去一条边后显然还是在生成树上上面的分析告诉你的这意味着恰好有一条边被加了进去而这条边被加进去的条件就是连接的两个点不联通。
基于上述分析我们可以尝试分治。首先计算出影响区间的右端点在 [ m i d 1 , r ] [mid1,r] [mid1,r]之间的边那么我们就要先算出哪些边的影响区间 ≥ m i d 1 \ge mid1 ≥mid1哪些边的影响区间 ≤ m i d \le mid ≤mid这样就将边集分成了两部分。使用可撤销并查集然后往两边递归即可。怎么计算答案呢发现递归到叶子节点的时候可以把那颗生成树算出来然后就做完了。
事实上算边的影响区间部分我们可以不用真的将边分到两个集合中去。考虑更聪明的想法倒着往前处理询问的时候之前在生成树上的边还是在生成树上那么我们事实上只需要在此基础上加入边权更大的边当然这条边必须合法直到得到的图满足条件。那么我们就知道新加入的这些边的影响区间的右端点就是当前这个位置在线段树上对应部分打一个标记即可。这个半在线做法非常神奇。
这高级玩意估计考场上也想不到/kk
复杂度 O ( n log n log m ) O(n\log n\log m) O(nlognlogm)。
实现了后一种较为复杂的方法。
该死有一个地方打挂了。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
#define db double
#define cpx complexdb
using namespace std;
const int N3e55;
int n,m,cnt,res[N],now;
int fa[N],s[N],sa[N];
vectorintG[N2];
struct node{int x,y,z;
}e[N];
bool cmp(int x,int y){return e[x].ze[y].z;
}
int find(int x){return fa[x]x?x:find(fa[x]);
}
void modify(int p,int l,int r,int ql,int qr,int x){if(qlqr)return;if(qllrqr){G[p].pb(x);return;}int midlr1;if(qlmid)modify(p1,l,mid,ql,qr,x);if(midqr)modify(p1|1,mid1,r,ql,qr,x);
}
void solve(int p,int l,int r){vectorpairint,intbak;for(auto pos:G[p]){int xfind(e[pos].x),yfind(e[pos].y);if(x!y){cnt-(s[x]1)(s[y]1);if(s[x]s[y])swap(x,y);bak.pb(make_pair(x,y));fa[x]y,s[y]s[x],cnt(s[y]1);}}if(lr){while(cntnowm){int xfind(e[sa[now]].x),yfind(e[sa[now]].y);if(sa[now]l)modify(1,1,m,sa[now],l-1,sa[now]);//fixedif(sa[now]lx!y){cnt-(s[x]1)(s[y]1);if(s[x]s[y])swap(x,y);bak.pb(make_pair(x,y));fa[x]y,s[y]s[x],cnt(s[y]1);}now;}if(!cnt)res[l]e[sa[now-1]].z;else res[l]-1;}else{int midlr1;solve(p1|1,mid1,r);solve(p1,l,mid);}reverse(bak.begin(),bak.end());for(auto x:bak){cnt-s[x.se]1;fa[x.fi]x.fi,s[x.se]-s[x.fi];cnt(s[x.fi]1)(s[x.se]1);}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i)fa[i]i,s[i]1;for(int i1;im;i){cine[i].xe[i].ye[i].z,sa[i]i;}sort(sa1,sa1m,cmp);cntn,now1;solve(1,1,m);for(int i1;im;i)coutres[i]\n;
}
