首页 > 其他分享 >C138 线段树分治 P2056 [ZJOI2007] 捉迷藏

C138 线段树分治 P2056 [ZJOI2007] 捉迷藏

时间:2024-06-13 21:55:43浏览次数:27  
标签:int C138 捉迷藏 P2056 ZJOI2007 include col

视频链接:C138 线段树分治 P2056 [ZJOI2007] 捉迷藏_哔哩哔哩_bilibili

 

 

 

P2056 [ZJOI2007] 捉迷藏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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

#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
const int N=500005;
int n,q;
int head[N],ne[N<<1],to[N<<1],idx;
void add(int u,int v){
  to[++idx]=v;ne[idx]=head[u];
  head[u]=idx;
}
int fa[N],son[N],dep[N],siz[N],top[N];

void dfs1(int u,int f){ //搞fa,son,dep
  fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==f) continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
  }
}
void dfs2(int u,int t){ //搞top
  top[u]=t;  //记录链头
  if(son[u])dfs2(son[u],t);//搜重儿子
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v); //搜轻儿子
  }
}
int lca(int u,int v){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    u=fa[top[u]];
  }
  return dep[u]<dep[v]?u:v;
}

int lst[N];    //上次出现的时刻
bitset<N> col; //黑色=0
bitset<N> qb;  //查询=1
vector<int> tr[N<<2];   //节点
stack<pair<int,int>>st; //栈
int u,v,ans[N];

void insert(int i,int l,int r,int L,int R,int x){
  if(L>r||R<l) return;
  if(L<=l&&r<=R) return tr[i].push_back(x);
  insert(ls,l,mid,L,R,x);
  insert(rs,mid+1,r,L,R,x);
}
int dis(int x,int y){ //两点距离
  return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void solve(int i,int l,int r){
  auto now=st.size();
  for(int x:tr[i]){
    st.push({u,v}); //旧直径入栈
    if(!u&&!v) u=x,v=x;
    else{
      int d0=dis(u,v),d1=dis(u,x),d2=dis(v,x);
      int d=max(d0,max(d1,d2));
      if(d1==d) v=x;
      else if(d2==d) u=x; //更新直径端点
    }
  }
  
  if(l==r) ans[l]=(!u||!v)?-1:dis(u,v);
  else solve(ls,l,mid),solve(rs,mid+1,r);
  
  while(st.size()!=now){ //撤销
    auto t=st.top();
    u=t.first,v=t.second;
    st.pop();
  }
}
int main(){
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1,u,v;i<n;i++){
    cin>>u>>v; add(u,v);add(v,u);
  }
  dfs1(1,0);dfs2(1,0); //树链剖分
  
  for(int i=1;i<=n;i++) lst[i]=1;
  cin>>q;
  for(int i=1,x;i<=q;i++){ //操作为时间轴
    char c; cin>>c;
    if(c=='C'){
      cin>>x;
      if(!col[x]){ //黑色=0
        col[x]=1;
        insert(1,1,q,lst[x],i,x); //插入x的出现时间
      }
      else col[x]=0,lst[x]=i; //记录x再次出现时刻
    }
    else qb[i]=1; //i时刻是查询
  }
  for(int i=1;i<=n;i++) //插入i的出现时间
    if(!col[i]) insert(1,1,q,lst[i],q,i);
  solve(1,1,q);
  for(int i=1;i<=q;i++)
    if(qb[i])printf("%d\n",ans[i]);
}

 

标签:int,C138,捉迷藏,P2056,ZJOI2007,include,col
From: https://www.cnblogs.com/dx123/p/18239898

相关文章

  • P1110 [ZJOI2007] 报表统计 题解
    考察点:STL的熟练运用。记:\(l_i\)表示序列中不超过\(a_i\)的最大数,\(r_i\)表示序列中超过\(a_i\)的最小数。开一个vectorinsert[N]存储\(a_i\)后面插入的所有数字。首先,我们使用一个multisets1来存储相邻元素的差的绝对值,然后再开一个multisets2来存储当前出......
  • P1129 [ZJOI2007] 矩阵游戏 建模部分
    link题解没一个说为什么能用最小割的...(当然可能是只有我不知道)设交换后行、列数相同的第\(x\)行和第\(y\)列(\(x,y\)为原始位置),发现它们的交点现在位于\((i,i)\),原来位于\((x,y)\)。因为无论怎么交换位置,原来的交点仍是交点。所以可以得出一个构造方案:先选定\(n\)个点......
  • 斜率优化 [ZJOI2007] 仓库建设
    [ZJOI2007]仓库建设题目描述L公司有\(n\)个工厂,由高到低分布在一座山上,工厂\(1\)在山顶,工厂\(n\)在山脚。由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于......
  • P1129 [ZJOI2007] 矩阵游戏
    挺喜欢的一题。首先我们很容易观察到一个性质:每一行和每一列上的黑色方格的数量是不变的,只能改变它在那一行和那一列的排列顺序。由此若是有某一行或某一列上没有黑色方格,直接输出No即可。此时我们考虑的情况就是每一行和每一列上至少都会有一个黑色方格。这时有一个结论:若有......
  • LC1388 3n 块披萨
    环形DP求最大值。题目可以转化为:在一个大小为\(3n\)的环上选取互不相邻的\(n\)个数,使其和最大。这个问题如果在链上,显然可以通过DP解决。设\(dp_{i,j}\)表示截止到\(i\),选取了\(j\)个数的最大值,可以写出转移方程:\(dp_{i,j}=\max(dp_{i-1,j},dp_{i-2,j-2}+slices_i......
  • arc136,arc137,arc138题解
    ARC136A-EAA↔BB贪心。可以把BB换成A,可以把BA换成AB。BTripleShift直观上觉得只要数集相同,那么就是可以变换的。大概方法就是每次找到正确的数把它挪到数列的端点,这样显然是可行的。但是在相反的三个上出现了问题,原因在于只剩最后两个数时方向可能是反着的。分析......
  • [ZJOI2007]报表统计
    P1110[ZJOI2007]报表统计考虑到操作MIN_SORT_GAP比较简单,用一个set维护前驱后继即可,重点关注INSERT,MIN_GAP。发现我们可以先开一个单链表来存储所有数,开数组表示原数列的第\(i\)个元素现在的位置。每次插入只需要在对应位置插入,然后更新数组的值。关于维护最小差值,用......
  • [ARC138D] Differ by K bits 题解
    小清新构造题。首先\(K=1\)的情况是trival的,直接格雷码即可。对于\(K>1\),我们发现题目的约束相当于\(\operatorname{popcount}(P_i\oplusP_{(i+1)\bmod2^N})=K\),考虑\(P_i\)的差分序列\(D_i\),那么\(D_i\)一定是一个恰好有\(K\)位\(1\)的二进制数,记\(S=\{i\mid......
  • P1131 [ZJOI2007] 时态同步
    P1131[ZJOI2007]时态同步-洛谷|计算机科学教育新生态(luogu.com.cn)这更多是一个思维题   看到上面这副图,我们的想法是先让1→2和1→3拉伸到1→4的深度,再......
  • LQB02控制LED灯,74HC138芯片,74HC02芯片,74HC573芯片。
    一,硬件图解读。二,控制LED需要的74HC595程序编程。三,控制某个LED亮,其他保持不变,或者控制整8个LED,其他不变;四,读取某个LED的状态,一秒时间读取一次,如果是低电平,那么变为高电......