首页 > 其他分享 >CF207C3 Game with Two Trees 题解

CF207C3 Game with Two Trees 题解

时间：2023-03-08 21:11:56浏览次数：32  
标签：int 题解 CF207C3 son Game maxn null id size

脑子不够，科技来凑。

不过好像也没有用多么高级的科技……

首先这个题目很坏，它让你翻转 \(S_{t_2}\)。即从 \(t_2\) 某个节点往下走到另一个节点的路径所表示的字符串。这个非常难以维护。因此我们不翻转 \(S_{t_2}\)，转而翻转 \(S_{t_1}\)。两者的效果是相同的。于是询问就变成了从 \(t_1\) 的根走到某个节点的路径，以及从 \(t_2\) 某个节点向上走的路径，两者相等的情况数。

由于节点只加不删，考虑算出加入每个节点会产生的贡献，最后再滚一遍前缀和得到答案。由于 \(t_2\) 询问的是从某个节点向上的路径。考虑离线建出两棵树并把边权下放到点，对 \(t_2\) 进行树上后缀排序。按深度从小到大处理每个 \(t_1\) 节点 \(i\)。显然 \(i\) 能够匹配到的 \(t_2\) 的 SA 区间只会比其父亲更小。在其父亲能够匹配到的 SA 区间内二分。由于 \(i\) 所代表的字符串长度只比其父亲多 1，所以在二分时只需要判断 \(SA_{mid}\) 的第 \(k\) 级祖先是否与 \(i\) 的字符相等即可（\(k=dep_i\)，\(dep_1=-1\)，\(dep_i=dep_{fa_i}+1\)）。这样就可以得到每个 \(t_1\) 节点 \(i\) 能够匹配到的 \(t_2\) 的 SA 区间。记作 \([L_i, R_i)\)。

现在来具体分析一下插入一个节点时会产生的贡献。

当插入一个 \(t_1\) 节点时：

  1. 每个之前插入的能与其匹配的 \(t_2\) 节点会对答案产生贡献。因此要记录 \(rec1_i\) 表示 \(SA_i\) 有无被插入。这部分是对 \(rec1\) 进行一个区间求和。
  2. 该点将与未来每个能与其匹配的 \(t_2\) 节点产生贡献。考虑记录 \(rec2_i\) 表示每个 \(t_2\) 节点 \(i\) 能与多少个 \(t_1\) 节点匹配。这部分是对 \(rec2\) 进行一次区间加 1。

当插入一个 \(t_2\) 节点时：

  1. 每个之前插入的能与其匹配的 \(t_1\) 节点会对答案产生贡献。这部分是对 \(rec2\) 进行一个单点求值。
  2. 该点将与未来每个能与其匹配的 \(t_1\) 节点产生贡献。这部分是对 \(rec1\) 进行一次单点加 1。

以上操作均能用树状数组简单地维护。于是问题只剩下如何进行树上后缀排序了。因为我没有脑子，所以我直接用后缀平衡树了。感觉没那么难写。

若使用长剖求树上 k 级祖先，则复杂度 \(O(n\log n)\)。然而长剖常数太大，实际跑起来不如重剖。因此实现时使用了朴素的重剖求树上 k 级祖先。复杂度 \(O(n\log^2 n)\)。常数不大。

Code：

constexpr int maxn = 100010;
int faA[maxn], faB[maxn], SA[maxn], Rank[maxn], *_p = SA, cntA, cntB, op[maxn];

typedef long long i64;
typedef unsigned long long u64;
constexpr u64 INF = 1ull << 62;
#define isNull(x) (x->son[0] == x)
char sA[maxn], sB[maxn];

struct Suffix_n {
  constexpr static double ALPHA = 0.75;
  Suffix_n *son[2];
  int id, size;
  u64 val;

  inline void pushup() {
    if (isNull(this))
      return;
    size = son[0]->size + son[1]->size + 1;
  }
  inline bool need_rebuild() {
    return ALPHA * size <= max(son[0]->size, son[1]->size);
  }
} *rec[maxn];

struct Suffix_t {
  constexpr static int SIZE = maxn;
  Suffix_n MemoryPool[SIZE], *const null = MemoryPool, *root = null, *pointer = null;
  Suffix_t() {
    rec[0] = null->son[0] = null->son[1] = null;
  }
  inline bool cmp(int a, int b) {
    return sB[a] ^ sB[b] ? sB[a] < sB[b] : rec[faB[a]]->val < rec[faB[b]]->val;
  }
  inline Suffix_n *allocate(int id, u64 num) {
    return *++pointer = {null, null, id, 1, num}, pointer;
  }
  vector<Suffix_n *> _need;
  void pre_rebuild(Suffix_n *r) {
    (r->son[0] != null) && (pre_rebuild(r->son[0]), 0), _need.emplace_back(r),
        (r->son[1] != null) && (pre_rebuild(r->son[1]), 0);
  }
  Suffix_n *rebuild_main(int left, int right, u64 L, u64 R) {
    if (left > right)
      return null;
    int mid     = (left + right) >> 1;
    u64 vmid    = (L + R) >> 1;
    Suffix_n *r = _need[mid];
    r->val      = vmid;
    r->son[0] = rebuild_main(left, mid - 1, L, vmid), r->son[1] = rebuild_main(mid + 1, right, vmid, R);
    r->pushup();
    return r;
  }
  inline void rebuild(Suffix_n *&r, u64 L, u64 R) {
    _need.clear(), pre_rebuild(r), r = rebuild_main(0, _need.size() - 1, L, R);
  }
  void insert(Suffix_n *&r, int id, u64 L = 0, u64 R = INF) {
    if (r == null) {
      rec[id] = r = allocate(id, (L + R) >> 1);
      return;
    }
    cmp(id, r->id) ? insert(r->son[0], id, L, r->val) : insert(r->son[1], id, r->val, R);
    r->pushup();
    if (r->need_rebuild())
      rebuild(r, L, R);
  }
  inline void dfs(Suffix_n *r) {
    (r->son[0] != null) && (dfs(r->son[0]), 0), *++_p = r->id, (r->son[1] != null) && (dfs(r->son[1]), 0);
  }
} Suffix;

basic_string<int> edge[maxn];
int size[maxn], fa[maxn], dep[maxn], son[maxn], top[maxn], dfn[maxn], MAP[maxn], _id, root;
void dfs1(int u, int _fa) {
  size[u] = 1, fa[u] = _fa, dep[u] = dep[_fa] + 1;
  for (const int &v : edge[u])
    dfs1(v, u), size[u] += size[v], (size[v] > size[son[u]]) && (son[u] = v);
}
void dfs2(int u, int _top) {
  dfn[u] = ++_id, MAP[_id] = u, top[u] = _top;
  if (!son[u])
    return;
  dfs2(son[u], _top);
  for (const int &v : edge[u])
    (v != son[u]) && (dfs2(v, v), 0);
}
inline char kthF(int x, int k) {
  if (dep[x] <= k)
    return 0;
  int tmp;
  while (k) {
    tmp = dep[x] - dep[top[x]] + 1;
    if (tmp <= k)
      x = fa[top[x]], k -= tmp;
    else
      return sB[MAP[dfn[x] - k]];
  }
  return sB[x];
}

int L[maxn], R[maxn];
inline void build() {
  for (int i = 1; i <= cntB; i++)
    Rank[SA[i]] = i;
  static int _dep[maxn];
  L[1] = 1, R[1] = cntB + 1, _dep[1] = -1;
  for (int i = 2; i <= cntA; i++) {
    _dep[i]  = _dep[faA[i]] + 1;
    int left = L[faA[i]], right = R[faA[i]], mid;
    while (left < right)
      mid = (left + right) >> 1, (kthF(SA[mid], _dep[i]) >= sA[i]) ? right = mid : left = mid + 1;
    L[i] = left, right = R[faA[i]];
    while (left < right)
      mid = (left + right) >> 1, (kthF(SA[mid], _dep[i]) > sA[i]) ? right = mid : left = mid + 1;
    R[i] = left;
  }
}

namespace BIT1 {
#define lowbit(x) (x & -x)
i64 tree[maxn];
inline void update(int id, int val) {
  for (int i = id; i <= cntB; i += lowbit(i))
    tree[i] += val;
}
inline i64 query(int l, int r) {
  l--, r--;
  i64 res = 0;
  for (int i = r; i; i -= lowbit(i))
    res += tree[i];
  for (int i = l; i; i -= lowbit(i))
    res -= tree[i];
  return res;
}
}  // namespace BIT1
namespace BIT2 {
i64 tree[maxn];
inline void update(int l, int r, int val) {
  for (int i = l; i <= cntB; i += lowbit(i))
    tree[i] += val;
  for (int i = r; i <= cntB; i += lowbit(i))
    tree[i] -= val;
}
inline i64 query(int id) {
  i64 res = 0;
  for (int i = id; i; i -= lowbit(i))
    res += tree[i];
  return res;
}
}  // namespace BIT2
i64 ANS[maxn];

int main() {
  int q;
  in(q);
  op[1] = 1, op[2] = 2, cntA = cntB = 1, q += 2;
  for (int i = 3; i <= q; i++)
    in(op[i]), (op[i] == 1) ? (cntA++, in(faA[cntA], sA[cntA])) : (cntB++, in(faB[cntB], sB[cntB]));

  for (int i = 1; i <= cntB; i++)
    Suffix.insert(Suffix.root, i), edge[faB[i]] += i;
  Suffix.dfs(Suffix.root), dfs1(1, 0), dfs2(1, 1);
  build();

  for (int i = 1, p1 = 0, p2 = 0; i <= q; i++)
    if (op[i] == 1)
      p1++, ANS[i] = BIT1::query(L[p1], R[p1]), BIT2::update(L[p1], R[p1], 1);
    else
      p2++, ANS[i] = BIT2::query(Rank[p2]), BIT1::update(Rank[p2], 1);
  for (int i = 2; i <= q; i++)
    ANS[i] += ANS[i - 1];
  for (int i = 3; i <= q; i++)
    out(ANS[i]), enter;
}

标签：int,题解,CF207C3,son,Game,maxn,null,id,size
From： https://www.cnblogs.com/DRPLANT/p/CF207C3_solution.html

相关文章

  • Python自动化登录验证码问题解决
     1.测试环境中通常解决验证码问题的方法 在测试环境中我们通常通过各种手段来逃避或者获得验证，而这些手段主要是要求开发者在开发的时候留有一定的后门。下面简述几种......
  • 【题解】ARC157 A-D
    因为有的题代码没写出来，所以代码就先咕咕咕了。A.XXYYX题目分析：可以发现每一个XY必然伴随着出现一次YX，当然可能会有一个XY没有伴随的YX的。而且若必须存在XX......
  • 【题解】[Ynoi2015] 我回来了
    题目分析：所谓的期望乘以\(R-L+1\)其实就是求亵渎的触发次数，因为我们能选择的伤害只有\(R-L+1\)种。有一个很显然的转化，就是对于伤害\(d\)，我们以随从的血量......
  • DP练习1题解
    这是2023.3.7DP题单十个题的题解。T1ColoredSubgraphs(CF1796E)简要题意：给定一棵树，你要对树进行链剖分，必须剖成上下竖直的链，求剖后最短链的长度最大值。最小值最大......
  • 【题解】[Ynoi2013] 大学
    题目分析：考虑对于一次修改至少会让\(x\)变成\(\frac{x}{2}\)所以对于每一个数最多被操作\(\log{n}\)次，那么直接暴力操作就好了。所以其实关键问题是每次怎么找到哪......
  • QOJ5256 [CERC2022] H. Insertions 题解
    题面题意：给定字符串\(S,T,P\)，求将\(T\)插入进\(S\)之后\(P\)最多的出现次数。输出：最多的出现次数；达到这个最多出现次数的插入位置数量；达到这个最多出现次数......
  • 【题解】[Ynoi2010] y-fast trie
    题目分析：显然可以对于所有的\(x\)对\(C\)取模后处理。那么就是两种情况：\(x+y\geC\)\(x+y<C\)对于第一种情况直接找最大的两个数就好了，关键就是第二种情......
  • 春测2023 T2题解
    这是一个从暴力到正解的过程。暴力从\(1\)枚举到\(\sqrtn\)，枚举每一个\(x\)，进行累乘，顺便用一个map数组判重，时间复杂度\(\mathcal{O}(\sqrtn\logn\logn)\)，直接T飞......
  • Ubuntu服务器ssh缓慢问题解决
    Ubuntu服务器ssh缓慢问题解决现象：ssh登陆或su-账号时间较长 排查：1、查看了/var/log/syslog未发现明显报错2、查看/var/log/auth.log发现有pam_systemd:Failedtocreate......
  • AGC060C题解
    Link简要题意：称一个长为\(2^n-1\)的排列\(P\)像堆，如果\(P_i\ltP_{2i}\),且\(P_i\ltP_{2i+1}\)。给定\(a,b\),设\(u=2^a,v=2^{b+1}-1\)，在所有像堆的排列中任取......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99