当前位置:网站首页>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;
}
边栏推荐
- Quartz misfire missed and compensated execution
- Exness foreign exchange: the governor of the Bank of Canada said that the interest rate hike would be more moderate, and the United States and Canada fell slightly to maintain range volatility
- MySQL 中的数据类型介绍
- Pointer for in-depth analysis (problem solution)
- 1.16 - check code
- 在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
- Pelosi: Congress will soon have legislation against members' stock speculation
- 2.2 fonctionnement stm32 GPIO
- 简易博客系统
- [Qt5] QT QWidget immediately appears and disappears
猜你喜欢
Cubemx 移植正点原子LCD显示例程
MySQL reads missing data from a table in a continuous period of time
1.16 - 校验码
SAP ALV单元格级别设置颜色
An article will give you a comprehensive understanding of the internal and external components of "computer"
Exness foreign exchange: the governor of the Bank of Canada said that the interest rate hike would be more moderate, and the United States and Canada fell slightly to maintain range volatility
BUAA计算器(表达式计算-表达式树实现)
深入刨析的指针(题解)
2.1 rtthread pin device details
Serial port-rs232-rs485-ttl
随机推荐
How to standardize the deployment of automated testing?
mysql从一个连续时间段的表中读取缺少数据
[meisai] meisai thesis reference template
1.16 - 校验码
2、GPIO相关操作
2.2 fonctionnement stm32 GPIO
Restful style
Cross origin cross domain request
SAP ALV color code corresponding color (finishing)
February 14, 2022 Daily: Google long article summarizes the experience of building four generations of TPU
2.13 weekly report
暑期刷题-Day3
Schnuka: what is visual positioning system and how to position it
Four logs of MySQL server layer
在 .NET 6 中使用 Startup.cs 更简洁的方法
自动化测试怎么规范部署?
js凡客banner轮播图js特效
The solution of permission denied (750 permissions should be used with caution)
Microkernel structure understanding
3.1 detailed explanation of rtthread serial port device (V1)