首页 > 其他分享 >题解 P2137 Gty的妹子树

题解 P2137 Gty的妹子树

时间:2023-07-17 23:13:48浏览次数:40  
标签:int 题解 cin tp P2137 ++ lst Gty op

神奇的分块。

假如没有 \(2\) 操作,我们可以直接用主席树解决。

我们考虑将询问分块,每遍历完一块就将这一块内出现的所有修改更新。如果在块内,就把当前块之前的所有修改暴力算,当然只有修改的节点在询问的节点的子树内才会发生。

具体的来说,我们可以用分块维护 dfs 序,并将块内的元素排序,询问 \(O(\sqrt n)\)。

对于新加进来的点,暴力跳找到其祖先,这样就能判断包含关系了。

总复杂度 \(O(n\sqrt{n}\cdot \log\sqrt{n})\)。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5,N2=600+5;
int n,m,fa[N],tp[N],l[N],r[N],tot=0,w[N],loc[N],a[N];
vector<int>adj[N];
struct kuai{int l,r,siz,val[N2];}b[N2];
struct node{
  int op,u,x,y;
  node(int op=0,int u=0,int x=0,int y=0):op(op),u(u),x(x),y(y){}
};
vector<node>vec;
void dfs(int u,int lst){
  l[u]=++tot;fa[u]=lst;
  for(int i=0;i<adj[u].size();++i)if(adj[u][i]!=lst)dfs(adj[u][i],u);
  r[u]=tot;
}
void build(){
  int cnt=1,j=0,len=sqrt(n);
  for(int i=1;i<=n;++i)a[l[i]]=w[i];
  b[1].l=1;
  for(int i=1;i<=n;++i){
    ++j;loc[i]=cnt;
    b[cnt].r=i;
    b[cnt].val[j]=a[i];
    if(j==len)b[cnt].siz=b[cnt].r-b[cnt].l+1,j=0,++cnt,b[cnt].l=i+1;
  }
  for(int i=1;i<=cnt;++i)sort(b[i].val+1,b[i].val+b[i].siz+1);
}
int query(int L,int R,int k){
  int res=0,x=loc[L],y=loc[R];
  if(x==y){for(int i=L;i<=R;++i)if(a[i]>k)++res;}
  else{
    for(int i=L;i<=b[x].r;++i)if(a[i]>k)++res;
    for(int i=b[y].l;i<=R;++i)if(a[i]>k)++res;
    if(x+1<y){
      for(int i=x+1;i<y;++i){
        int p=upper_bound(b[i].val+1,b[i].val+b[i].siz+1,k)-b[i].val;
        res+=b[i].siz-p+1;
      }
    }
  }
  return res;
}
int get(int u){
  if(fa[u]<=n)return fa[u];
  return tp[u]=get(fa[u]);
}
bool check(int u,int v){
  if(u>n&&v<=n)return false;
  if(u<=n&&v<=n)return l[u]<=l[v]&&r[u]>=l[v];
  if(u<=n&&v>n){
    if(!tp[v])tp[v]=get(v);
    return l[u]<=l[tp[v]]&&r[u]>=l[tp[v]];
  }else{
    while(fa[v]>n){
      if(v==u)return true;
      v=fa[v];
    }
    return v==u;
  }
}
int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;
  for(int i=1;i<n;++i){
    int u,v;cin>>u>>v;
    adj[u].push_back(v);adj[v].push_back(u);
  }
  for(int i=1;i<=n;++i)cin>>w[i];
  dfs(1,0);build();
  cin>>m;
  int B=sqrt(m),nn=n,j=0,lst=0;
  while(m--){
    int op,u,x;cin>>op>>u>>x;
    u^=lst;x^=lst;
    if(j==B){
      n=nn;memset(tp,0,sizeof(tp));
      for(int i=0;i<vec.size();++i){
        node t=vec[i];
        if(t.op==2)adj[t.y].push_back(t.u);
      }
      tot=0;
      dfs(1,0);build();j=0;vec.clear();
    }
    ++j;
    if(op==0){
      lst=query(l[u],r[u],x);
      for(int i=0;i<vec.size();++i){
        node t=vec[i];
        if(check(u,t.u)){
          if(t.op==1){
            if(t.x<=x&&t.y>x)++lst;
            if(t.x>x&&t.y<=x)--lst;
          }else lst+=t.x>x;
        }
      }
      cout<<lst<<endl;
    }else if(op==1){
      vec.push_back(node(1,u,w[u],x));
      w[u]=x;
    }else{
      vec.push_back(node(2,++nn,x,u));
      w[nn]=x;fa[nn]=u;
    }
  }
  return 0;
}

标签:int,题解,cin,tp,P2137,++,lst,Gty,op
From: https://www.cnblogs.com/HQJ2007/p/17561557.html

相关文章

  • 题解 P4183 [USACO18JAN] Cow at Large P
    带有小trick的点分治。建议先做完弱化版再看。假如奶牛在\(u\),那么所需的最少农夫数为\(\sum\limits_{v\inson(u)}[dis(u,v)\geg_v][dis(u,fa_v)<g_{fa_v}]\)。其中\(dis(u,v)\)为\(u,v\)在树上的距离,\(g_u\)为\(u\)到离它最近的出入口的距离(BFS预处理),\(fa_u\)......
  • 题解 P9415 下楼
    不难推理出当初始绳长为\(len\),需要下降的距离为\(d\),并且满足\(d\lelen<2d\)时,最优的环套法可以只损失\(2d-len\)长度的绳子,留下\(2(len-d)\)的绳子。当\(2d\lelen\)时存在一种不损耗绳长的方法可以下到下一根钢管,即把整根绳子系成一个环,到达下面再剪断。正文:线......
  • 题解 P9437『XYGOI round1』一棵树
    换根DP。本蒟蒻最初没想到换根,把自己写自闭了...定义\(f_u\)为子树\(u\)中的每个结点走到\(u\)的贡献和,\(l_u\)为大于\(a_u\)的最小的\(10\)的幂次方数,\(sum_u\)为\(\sum\limits_{v\inson(u)}{f_v}\)。转移方程为:\(f_u=l_u\cdot\sum\limits_{v\inson(u)}{f_v}+......
  • 决策单调性优化DP 学习笔记 & P4767 [IOI2000] 邮局 题解
    0.题面题目描述高速公路旁边有一些村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局......
  • 题解 P7215
    点分治。考虑当前的分治重心的城市被完全联通。这可以用队列接解决。每次放入一种城市,就把那些城镇的父亲加入队列,如果存在城镇不在当前分治重心的联通块内,那么说明必定存在另一个分治重心能算到它,直接退出即可。剩下的和模板没有任何区别。复杂度\(O(n\logn)\)。code:#in......
  • 题解 P6329
    点分树模板题。是个神奇的算法。点分树就是将分治重心按照层级连边,每个节点父亲的联通块都包含了当前节点的联通块,且高度为\(\logn\)。可以解决不考虑树的形态的多次询问带修改的问题。对于这道题,我们可以在点分树的每个节点上记录两棵树状数组,分别与当前节点距离为\(k\)的......
  • 题解 P3345
    点分树。本题的核心问题在于不好直接确定补给站的位置。但是仔细思考后我们发现,对于当前节点,如果存在一个儿子的答案比它优,那么补给站一定在那个儿子的子树中。增量为\(w\times(sum_u-2\cdotsum_v)\)。当\(v\)优于\(u\)时,\(2\cdotsum_v>sum_u\)。如果\(v_2\)也满足,则......
  • 题解 P5384
    这题有紫??对于询问节点\(u\),倍增地跳到它的\(k\)级祖先,求其子树内有多少深度为\(dep_u\)的节点。我们考虑把询问离线,再通过dfs序把树拍平,然后扫一遍直接求就行了。复杂度\(O(n\logn)\)。code:#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;inlin......
  • 题解 P3806
    点分治模板题。点分治适合处理大规模的树上路径信息问题暴力做法:dfs每个点\(u\),算出其子树内每个点到\(u\)的距离,统计经过\(u\)的所有路径,复杂度\(O(n^2)\)。容易发现,复杂度和子树大小有关。对于当前子树,我们可以求出其重心,计算经过重心的所有路径,删掉重心,递归每个联通......
  • 题解 CF1271D
    贪心+DP。对于一个点,后选显然比先选好,也就是说每个点都对应了唯一一个来源。于是我们可以把每个点所能回溯到的点的收益值从大到小排序,贪心地选前缀。定义\(f_{i,j}\)表示考虑了前\(i\)个点,剩下\(j\)个人,最大收益。转移方程和\(01\)背包的一样。\[f_{i,j}=f_{i-1,j-b......