[UOJ 195][ZJOI2016]大♂森林

danihao123 posted @ 2018年4月27日 16:53 in 题解 with tags ZJOI LCT uoj , 531 阅读
转载请注明出处:http://danihao123.is-programmer.com/

ETT野蛮,LCT文明,,,

换生长结点这个操作非常的麻烦。所以考虑给每个生长操作建立一个虚点,每个实点(就是在树中真实存在的点)向他之前最晚建立的一个虚点认父。

然后虚点初始的时候应该向上一次的那个虚点认父(我们可以近似的认为第一个虚点就是1)。然后我们用类似于扫描线的做法,等到了虚点存在的区间里就把它爸爸改成相应的实点,出去了相应区间之后就再改回来。这样这题就很好做了,我们认为虚点点权为0,实点点权为1,然后查询就好做了。

然后还有一点细节问题……比如说换生长结点的时候如何处理x在某一棵树里不存在的情况。但这个不难处理,因为同一个编号的结点一定分布编号连续的一段树里,所以真实起作用的操作范围可以认定为数据给出的操作范围和x的分布区间的交。

再有一点就是查询的时候……如果直接查询两点间splay的和的话,可能会忽略掉一些本来在原图上该有的实点。所以我们要求两点到根的距离,再用LCA去掉不需要的。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
const int maxn = 100005;
const int maxm = 200005;
const int maxs = maxm + maxm;
struct Node {
  Node *fa, *ch[2];
  int val, sumv;
  bool rev;
  int d() {
    return ((this == fa -> ch[1]) ? 1 : 0);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c;
    c -> fa = this;
  }
  void maintain() {
    sumv = ch[0] -> sumv + ch[1] -> sumv + val;
  }
  void paint() {
    rev = !rev;
    std::swap(ch[0], ch[1]);
  }
  void pushdown() {
    if(rev) {
      ch[0] -> paint();
      ch[1] -> paint();
      rev = false;
    }
  }
};
Node pool[maxs];
Node *nil, *cur;
void init_pool() {
  nil = cur = pool;
  nil -> val = nil -> sumv = 0;
  nil -> rev = false;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
}
#define T(x) (pool + (x))
Node *refresh(Node *x, int val = 0) {
  x -> val = x -> sumv = val;
  x -> rev = false;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
  return x;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  Node *y = x -> fa; int d = x -> d();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  y -> sc(x -> ch[1 ^ d], d);
  x -> sc(y, 1 ^ d);
  y -> maintain(); x -> maintain();
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) y -> fa -> pushdown();
    y -> pushdown(); x -> pushdown();
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
  // x -> maintain();
}
Node *access(Node *x) {
  Node *nx = x, *y = nil;
  Node *ct = T(1);
  while(x != nil) {
    splay(x); x -> pushdown();
    if(x -> fa == nil) ct = x;
    x -> sc(y, 1); x -> maintain();
    y = x; x = x -> fa;
  }
  splay(nx); return ct;
}
Node *evert(Node *x) {
  access(x); x -> paint();
  return x;
}
void link(Node *x, Node *y) {
  evert(x); x -> fa = y;
}
void cut(Node *x) {
  access(x);
  x -> ch[0] -> fa = nil;
  x -> ch[0] = nil; x -> maintain();
}
void cut(Node *x, Node *y) {
  evert(x); access(y);
  int d = x -> d();
  y -> ch[d] = nil; y -> maintain();
  x -> fa = nil;
}

int ans[maxm];
using pii = std::pair<int, int>;
int n;
pii seg_and(int a, int b, int x, int y) {
  if(a > x) {
    std::swap(a, x), std::swap(b, y);
  }
  if(b < x) return std::make_pair(n + 1, n + 1);
  if(b >= y) return std::make_pair(x, y);
  return std::make_pair(x, b);
}

int ope[maxm][4];
int seg[maxm][2];
Node *bef[maxm];
std::vector<int> beg[maxn], end[maxn];
std::vector<int> query[maxn];
// #define OUTP
// #define LOCAL
int main() {
#ifdef OUTP
  freopen("forest1.in", "r", stdin);
  freopen("out", "w+", stdout);
#endif
  int m; scanf("%d%d", &n, &m);
  init_pool(); refresh(T(1), 1);
  int cnt0 = 1, cnt1 = 0, cnt2 = 0;
  Node *last1 = T(1);
  seg[1][0] = 1; seg[1][1] = n;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d", &ope[i][0], &ope[i][1], &ope[i][2]);
    if(ope[i][0]) {
      scanf("%d", &ope[i][3]);
    }
    if(ope[i][0] == 0) {
      int c = ++ cnt0;
      refresh(T(c), 1);
      link(last1, T(c));
      seg[c][0] = ope[i][1]; seg[c][1] = ope[i][2];
#ifdef LOCAL
      printf("Node %d : (%d, %d)\n", c, seg[c][0], seg[c][1]);
#endif
    } else if(ope[i][0] == 1) {
      Node *n1 = T(m + i);
      refresh(n1); link(n1, bef[i] = last1);
      int l = ope[i][1], r = ope[i][2], x = ope[i][3];
      auto s = seg_and(l, r, seg[x][0], seg[x][1]);
      l = s.first, r = s.second;
#ifdef LOCAL
      printf("Change : (%d, %d) -> %d\n", l, r, x);
#endif
      beg[l].push_back(i); end[r + 1].push_back(i);
      last1 = n1;
    } else {
      int x = ope[i][1], u = ope[i][2], v = ope[i][3];
      query[x].push_back(i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(auto id : end[i]) {
      Node *n1 = T(m + id);
      cut(n1, T(ope[id][3])); link(n1, bef[id]);
    }
    for(auto id : beg[i]) {
      Node *n1 = T(m + id);
      cut(n1, bef[id]); link(n1, T(ope[id][3]));
    }
    for(auto id : query[i]) {
      int u = ope[id][2], v = ope[id][3];
      evert(T(1)); access(T(u));
      int ret = T(u) -> sumv;
      Node *lca = access(T(v));
      ret += T(v) -> sumv;
      access(lca);
      ret -= lca -> sumv;
      ret -= lca -> sumv - 1;
      ans[id] = ret - 1;
    }
  }
  for(int i = 1; i <= m; i ++) {
    if(ope[i][0] == 2) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}
Kar 11th Previous Pa 说:
Aug 22, 2022 03:29:50 AM

It was created for the Karnataka Secondary Education examination Board. The board administers exams for grades 1 through 11. It is one of the most well-known boards, and many public and private schools are linked with it. board on the same corporate website. After the test, students are looking for their KSEEB 11th class Question Paper 2023. Kar 11th Previous Paper 2023 They may check this from the official web portal site, and we also have a direct link to check Ist PUC Important Question Paper 2023 quickly. For students, we have provided some instructions on how to check the Kar 11th Class Important Question Paper 2023, which they can get by following the links provided below.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter