当前位置:网站首页>Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]
Cf603e pastoral oddities [CDQ divide and conquer, revocable and search set]
2022-07-06 03:44:00 【QuantAsk】
On the subject
Topic link :https://www.luogu.com.cn/problem/CF603E
The main idea of the topic
There was... At the beginning n n n A little bit , There is no side .
Add in sequence m m m Edge of strip weight , After each addition, ask whether there is an edge set , The degree satisfying each point is odd , Seek to minimize the maximum weight of this edge set .
1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 3 × 1 0 5 1\leq n\leq 10^5,1\leq m\leq 3\times 10^5 1≤n≤105,1≤m≤3×105
Their thinking
First, consider the condition for the existence of this edge set , It can be proved that there is an edge set satisfying the condition if and only if the size of the connected blocks is even .
The need for : For a connection block , Because each edge contributes an even number of degrees , And if this connected block is an odd number of points , Then if the total legal degree is Odd number × Odd number = Odd number , Obviously, it can't be even , So there is no such situation .
adequacy : If there is a point whose degree is odd , Then the degree of at least one point in the Unicom fast is odd , We can adjust to the legal situation by deleting the edge on the path of these two points on the way .
And it is definitely the best if we can connect the edges , Because there is no edge connection, the number of odd connected blocks will increase .
Then consider using CDQ Divide and conquer to solve this problem , Notice that the answer must be monotonous , Our process is to record the current interval [ l , r ] [l,r] [l,r] Answer range of { L , R } \{L,R\} { L,R}.
First calculate a n s m i d ans_{mid} ansmid, Then at this time we can be divided into [ l , m i d − 1 ] { a n s m i d , R } [l,mid-1]\{ans_{mid},R\} [l,mid−1]{ ansmid,R} and [ m i d + 1 , r ] { L , a n s m i d } [mid+1,r]\{L,ans_{mid}\} [mid+1,r]{ L,ansmid}
At this time, the two intervals are separated , This suggests that the violent enumeration of these intervals is the complexity of normal partition .
Then it's obvious , We calculated a n s m i d ans_{mid} ansmid After the left and right sides of recursive processing , With revocable and search set processing .
Time complexity : O ( m log m log n ) O(m\log m\log n) O(mlogmlogn)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+10;
struct node{
int x,y,w,id;
}a[N],b[N];
struct clnode{
int x,y,siz,dep;
}cl[N];
int n,m,sum,clt,fa[N],siz[N],dep[N];
int ans[N],rk[N];
int find(int x)
{
return (fa[x]==x)?x:find(fa[x]);}
void unionn(int x,int y){
x=find(x);y=find(y);
if(x==y)return;
if(dep[x]>dep[y])swap(x,y);
cl[++clt]=(clnode){
x,y,siz[y],dep[y]};
sum-=(siz[x]&1)&(siz[y]&1);
fa[x]=y;siz[y]+=siz[x];
dep[y]=max(dep[y],dep[x]+1);
}
void clearto(int d){
while(clt>d){
int x=cl[clt].x,y=cl[clt].y;
siz[y]=cl[clt].siz;
dep[y]=cl[clt].dep;
sum+=(siz[x]&1)&(siz[y]&1);
fa[x]=x;clt--;
}
return;
}
void cdq(int l,int r,int L,int R){
if(l>r)return;
int mid=(l+r)>>1,now=clt;
for(int i=l;i<=mid;i++)
if(rk[i]<L)unionn(a[i].x,a[i].y);
int mow=clt;
for(int i=L;i<=R;i++){
if(b[i].id<=mid)unionn(b[i].x,b[i].y);
if(!sum){
ans[mid]=i;break;}
}
if(!ans[mid]){
clearto(mow);
cdq(mid+1,r,L,R);
return;
}
clearto(mow);
cdq(mid+1,r,L,ans[mid]);
clearto(now);
for(int i=L;i<ans[mid];i++)
if(b[i].id<l)unionn(b[i].x,b[i].y);
cdq(l,mid-1,ans[mid],R);
clearto(now);return;
}
bool cmp(node x,node y)
{
return x.w<y.w;}
int main()
{
scanf("%d%d",&n,&m);sum=n/2;
if(n&1){
for(int i=1;i<=m;i++)
puts("-1");
return 0;
}
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
a[i].id=i;b[i]=a[i];
}
sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++)rk[b[i].id]=i;
cdq(1,m,1,m);
for(int i=1;i<=m;i++)
if(!ans[i])puts("-1");
else printf("%d\n",b[ans[i]].w);
return 0;
}
边栏推荐
- Yyds dry inventory what is test driven development
- 在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
- How do we make money in agriculture, rural areas and farmers? 100% for reference
- Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
- The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
- Blue Bridge Cup - Castle formula
- [matlab] - draw a five-star red flag
- mysql关于自增长增长问题
- Pointer written test questions ~ approaching Dachang
- BUAA喜鹊筑巢
猜你喜欢
C language judgment, ternary operation and switch statement usage
BUAA magpie nesting
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
在 .NET 6 中使用 Startup.cs 更简洁的方法
Python implementation of maddpg - (1) openai maddpg environment configuration
How to standardize the deployment of automated testing?
简易博客系统
Canvas cut blocks game code
Svg drag point crop image JS effect
Edcircles: a real time circle detector with a false detection control translation
随机推荐
记录一下逆向任务管理器的过程
C language judgment, ternary operation and switch statement usage
C language circular statement
给新人工程师组员的建议
施努卡:3d视觉检测应用行业 机器视觉3d检测
2.13 weekly report
Differential GPS RTK thousand search
SAP ALV单元格级别设置颜色
[optimization model] Monte Carlo method of optimization calculation
three. JS page background animation liquid JS special effect
Restful style
JVM的手术刀式剖析——一文带你窥探JVM的秘密
1、工程新建
11. Container with the most water
施努卡:视觉定位系统 视觉定位系统的工作原理
3.2 detailed explanation of rtthread serial port device (V2)
Schnuka: what is visual positioning system and how to position it
Align items and align content in flex layout
User experience index system
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒