首页 > 其他分享 >C135 线段树分治 P5631 最小mex生成树

C135 线段树分治 P5631 最小mex生成树

时间:2024-06-09 17:55:09浏览次数:18  
标签:C135 int siz top include P5631 mex

视频链接:

 

P5631 最小mex生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 线段树分治 O(nlognlogw)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
#define N 2000005
int n,m,mx,top;
int a[N],b[N],w[N];
int p[N],siz[N];
vector<int>tr[400005]; //节点
struct node{
  int x,y;
}st[N<<1]; //栈

void insert(int u,int l,int r,int L,int R,int i){
  if(l>R||r<L) return;
  if(L<=l&&r<=R) return tr[u].push_back(i);
  insert(ls,l,mid,L,R,i);
  insert(rs,mid+1,r,L,R,i);
}
int find(int x){ //查找根
  return p[x]==x?x:find(p[x]);
}
void merge(int x,int y){ //合并集合
  x=find(x),y=find(y);
  if(x==y) return;
  if(siz[x]>siz[y]) swap(x,y);
  st[++top]={x,y};
  p[x]=y;
  siz[y]+=siz[x];
}
void solve(int u,int l,int r){
  int now=top;
  for(auto i:tr[u]) merge(a[i],b[i]);
  
  if(l==r){
    if(siz[find(1)]==n) printf("%d\n",l),exit(0);
  }
  else solve(ls,l,mid),solve(rs,mid+1,r);
  
  while(top>now){ //撤销合并
    node s=st[top--];
    p[s.x]=s.x;
    siz[s.y]-=siz[s.x];
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i) p[i]=i,siz[i]=1;
  for(int i=1;i<=m;++i){
    scanf("%d%d%d",&a[i],&b[i],&w[i]);
    mx=max(mx,w[i]+1);
  }
  for(int i=1;i<=m;++i){
    insert(1,0,mx, 0,w[i]-1, i);
    insert(1,0,mx, w[i]+1,mx,i);    
  }
  solve(1,0,mx);
}

 

标签:C135,int,siz,top,include,P5631,mex
From: https://www.cnblogs.com/dx123/p/18236718

相关文章

  • ABC 308E MEX
    题意给定长度为N的包含0,1,2的a序列,和一个长度为N的包含字符M,E,X的字符串s。对于所以符合条件的1<=i<j<k<=N,使得s[i]s[j]s[k]=="MEX"的三元组(i,j,k),请你求出所有mex(a[i],a[j],a[k])之和。mex()函数表示未出现在序列中的最小非负整数。思路我们先看一个非常典的题目,给你一串由a......
  • 【CodeChef】Limit of MEX(二分、ST表、组合数学)
    题目大意:计算\(\sum_{L=1}^{N}\sum_{R=L}^{N}f(A_L,...,A_R)\),其中\(f(A_1,A_2,...,A_N)=\max(A_1,A_2,...,A_N)-count(A_1,A_2,...,A_N)+1\),\(count\)函数的值为参数中不同元素的个数。考虑计算\(\sum_{L=1}^{N}\sum_{R=L}^{N}max(A_1,A_2,...,A_N)\)。对于任意\(1\lei\len......
  • CF940F.Machine Learning-带修莫队、Mex
    给一个序列\(a\),两个操作:1、给\(l,r\),设\(a_l,\dots,a_r\)这些数集中每个数\(v\)的出现次数是\(c_v\),要求\(\mathrm{mex}(c_i)\).2、单点修改\(1\leqn,q\leq10^5\),时限4s这种一眼看过去很难维护的信息,一般就先找找性质。首先注意到关键性质:要求的是出现次数......
  • Nene and the Mex Operator
    这道题目告诉我们的是,看到\(n\)非常小,不一定是搜索,也不一定是状压,还有可能是枚举是否操作考虑枚举每个不操作的位置,这些位置将序列分成若干个连续段,每一段里面的数字一定会被操作至少一次当一个数字被操作了至少一次之后,他的值就不会比某次操作的区间长度大,于是我们猜想,一个段里......
  • T434199 「LAOI-4」Mex Tower (Hard ver.)
    /* 和上题一样只不过,是换成了检验答案,还是找规律, 自己看看吧awa*///O(n)#pragmaGCCoptimize(2)#include<iostream>#include<algorithm>#include<cstring>#include<ctime>usingnamespacestd;intn,m;strings;charget(chara,charb){ints......
  • T429423 「LAOI-4」Mex Tower (Easy ver.)
    /* 手玩数据找规律 你会发现有很强的规律性*///O(n)#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;intn,m;strings;intx[3]={2,1,0};inty[3]={2,0,1};intx2[3]={1,0,2};inty2[3]={0,1,2};intmai......
  • CF1942B Bessie and MEX 题解
    题目简述给定一个长度为$n$的数组$a$,让你构造一个等长的排列$p$,其中从$0$到$n-1$的每个整数恰好出现一次。满足对于每一个位置$a_i=\texttt{MEX}(p_1,p_2,\ldots,p_i)-p_i$,其中数组的$\texttt{MEX}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并......
  • AP1867 是一种合成的定向配体 | MedChemExpress (MCE)
    AP1867CAS:195514-23-9品牌:MedChemExpress(MCE)存储条件:Powder:-20°C,3years;4°C,2years.Insolvent:-80°C,6months;-20°C,1month.生物活性:AP1867是一种合成的FKBP12F36V定向配体[1]。IC50和目标:FKBP[1]体外:AP1867与野生型FKBP(Kd=67nM)[2]结......
  • PLGA (50:50) 是聚乳酸 (PLA) 和聚乙醇酸 (PGA) 的共聚物 | MedChemExpress (MCE)
    PLGA(50:50)|聚乳酸-羟基乙酸共聚物中文名:聚乳酸-羟基乙酸共聚物CAS:34346-01-5品牌:MedChemExpress(MCE)存储条件:Powder:-20°C,3years;4°C,2years.Insolvent:-80°C,6months;-20°C,1month.生物活性:PLGA(50:50)(poly(lactic-co-glycolicacid)(50:5......
  • 木犀草素 (Luteoline) 是一种类黄酮化合物 | MedChemExpress (MCE)
    Luteolin|木犀草素Luteolin|木犀草素中文名:木犀草素CAS:491-70-3品牌:MedChemExpress(MCE)存储条件:Powder:-20°C,3years;4°C,2years.Insolvent:-80°C,6months;-20°C,1month.生物活性:木犀草素(Luteoline)是一种类黄酮化合物,是一种有效的Nrf2抑制剂......