首页 > 其他分享 >C136 线段树分治 P4219 [BJOI2014] 大融合

C136 线段树分治 P4219 [BJOI2014] 大融合

时间:2024-06-10 20:22:59浏览次数:23  
标签:C136 int siz ++ BJOI2014 find tim et P4219

视频链接:

 

P4219 [BJOI2014] 大融合 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

#define ls (u<<1)
#define rs (u<<1|1)
#define mid ((l+r)>>1)
const int N=100005;
int n,m;
int p[N],siz[N],top; //并查集
vector<pair<int,int>> tr[N<<4]; //节点
struct node{
  int x,y;
}st[N<<1]; //栈

void insert(int u,int l,int r,int L,int R,pair<int,int> e){
  if(L<=l&&r<=R) return tr[u].push_back(e);
  if(L<=mid) insert(ls,l,mid,L,R,e);
  if(R>mid) insert(rs,mid+1,r,L,R,e);
}
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];
}

int cnt,tim,ans[N<<2];
struct tims{
  pair<int,int> e; int l,r;
}tms[N<<2];                 //边出现的时间
map<pair<int,int>,int> et;  //边出现的时刻
map<int,pair<int,int>> qe;  //该时刻查询的边
map<int,bool> qt;           //查询时刻的标记

void solve(int u,int l,int r){
  int now=top;
  for(auto i:tr[u]) merge(i.first,i.second);
  
  if(l==r){
    if(qt[l]){
      int x=qe[l].first,y=qe[l].second;
      ans[l]=siz[find(x)]*siz[find(y)];
    }
  } 
  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); char c[5]; int x,y;
  for(int i=1;i<=n;i++) p[i]=i,siz[i]=1;
  while(m--){
    scanf("%s%d%d",c,&x,&y);
    if(x>y) swap(x,y);    //保证边的映射
    pair<int,int> e={x,y};
    if(c[0]=='A') et[e]=++tim;  //e出现的时刻
    else{
      tms[++cnt]={e,et[e],tim}; //e出现的时间
      qe[++tim]=e; //tim时刻查询的边
      qt[tim]=1;   //查询时刻的标记
      et[e]=++tim; //e再次出现时刻
    }
  }
  for(auto i:et)   //每条边出现的时间
    tms[++cnt]={i.first,et[i.first],tim}; 
  for(int i=1;i<=cnt;i++)
    insert(1,1,tim,tms[i].l,tms[i].r,tms[i].e);
  solve(1,1,tim);
  for(int i=1;i<=tim;i++)
    if(qt[i])printf("%d\n",ans[i]);
}

 

标签:C136,int,siz,++,BJOI2014,find,tim,et,P4219
From: https://www.cnblogs.com/dx123/p/18239905

相关文章

  • 洛谷 P4580 [BJOI2014] 路径
    传送门分析可以考虑dp。先朴素地定义\(dp[i][j]\)表示当前在结点\(i\),已经走过了\(j\)个结点(含当前)的方案数。发现没法处理括号匹配,于是加一维\(k\)表示当前还剩\(k\)个前括号没有匹配。又发现没法处理前导\(0\)。于是考虑再加一维表示当前的最后一位是什么状态。发......
  • [ARC136E] Non-coprime DAG
    [ARC136E]Non-coprimeDAG显然只和可达性有关。注意到这样一件事情:所有偶数都是可达的。而对于奇数而言,\((x-\operatorname{lpf}(x),x+\operatorname{lpf}(x))\)这个区间内的数和\(x\)一定不可达。定义\(x\)控制的区间为\((x-\operatorname{lpf}(x),x+\operator......
  • arc136,arc137,arc138题解
    ARC136A-EAA↔BB贪心。可以把BB换成A,可以把BA换成AB。BTripleShift直观上觉得只要数集相同,那么就是可以变换的。大概方法就是每次找到正确的数把它挪到数列的端点,这样显然是可行的。但是在相反的三个上出现了问题,原因在于只剩最后两个数时方向可能是反着的。分析......
  • NC13611 树
    题目链接题目题目描述shy有一颗树,树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的,当且仅当对于所有相同颜色的点对(x,y),x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。输入描述第一行两个整数n,k代表点数和颜色数;接下来n-1行,每行两个整数x,y表......
  • Luogu P4219 [BJOI2014]大融合
    [BJOI2014]大融合题目描述小强要在\(N\)个孤立的星球上建立起一套通信系统。这套通信系统就是连接\(N\)个点的一个树。这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。例如,在上图中,现在一共有了\(5\)......
  • [ABC136E] Max GCD
    2023-02-02题目传送门翻译难度&重要性(1~10):4题目来源AtCoder题目算法数学,贪心解题思路记这个数列的和为\(sum\)。那么对于每一次操作,\(sum\)的值都不会改变。最后的答案,也一定是\(sum\)的因数。那么我们枚举一下\(sum\)的因数,然后判断一下这个值是否可行。考虑......
  • 「解题报告」ARC136F Flip Cells
    感觉AtCoder上高于铜的难度就完全是随机了,这题完全是金吧,怎么可能只有铜啊,我快写自闭了。以下记\(n=hw\)。我们设三个DP数组:\(f_i\)为从初始状态经过\(i\)步之......
  • 「解题报告」ARC136E Non-coprime DAG
    很妙啊这题。我们来分析\(x\)能到\(y\)的数有什么性质。既然是不互质,那么可以考虑看这个数的最小质因子是什么。记\(f(x)\)为\(x\)的最小质因子。我们将质因子......
  • arc136D Without Carry 题解
    这阵子没一道题能自己想出来,开道黄题以下找找信心qwq又一道比C简单的D。题意:给出\(n\)个\(6\)位及以下数字,问有几对数字的和在十进制下无进位。\(n\leq10^6\)......
  • ARC136C
    结论题。先给出结论,答案为\(\max(\dfrac{1}{2}\sum\limits_{i=0}^{n-1}\left|a_i-a_{(i+1)\bmodn}\right|,\max\limits_{i=0}^{n-1}a_i)\)。证明:记前者为\(S\),后者为......