[HNOI2016]网络 [树链剖分，可删除堆]

考虑在 |不在| 这条链上的所有点上放上一个 \(x\)，删除也是，然后用可删除堆就随便草掉了。
// powered by c++11

// by Isaunoya

#pragma GCC optimize("Ofast")

#pragma GCC optimize("unroll-loops")

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define rep(i, x, y) for (register int i = (x); i <= (y); ++i)

#define Rep(i, x, y) for (register int i = (x); i >= (y); --i)

using namespace std;

using db = double;

using ll = long long;

using uint = unsigned int;

using pii = pair<int, int>;

#define ve vector

#define Tp template

#define all(v) v.begin(), v.end()

#define sz(v) ((int)v.size())

#define pb emplace_back

#define fir first

#define sec second

// the cmin && cmax

Tp<class T> void cmax(T& x, const T& y) {

  if (x < y) x = y;

}

Tp<class T> void cmin(T& x, const T& y) {

  if (x > y) x = y;

}

// sort , unique , reverse

Tp<class T> void sort(ve<T>& v) { sort(all(v)); }

Tp<class T> void unique(ve<T>& v) {

  sort(all(v));

  v.erase(unique(all(v)), v.end());

}

Tp<class T> void reverse(ve<T>& v) { reverse(all(v)); }

const int SZ = 0x191981;

struct FILEIN {

  char qwq[SZ], *S = qwq, *T = qwq, ch;

  char GETC() { return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T) ? EOF : *S++; }

  FILEIN& operator>>(char& c) {

    while (isspace(c = GETC()))

      ;

    return *this;

  }

  FILEIN& operator>>(string& s) {

    while (isspace(ch = GETC()))

      ;

    s = ch;

    while (!isspace(ch = GETC())) s += ch;

    return *this;

  }

  Tp<class T> void read(T& x) {

    bool sign = 1;

    while ((ch = GETC()) < 0x30)

      if (ch == 0x2d) sign = 0;

    x = (ch ^ 0x30);

    while ((ch = GETC()) > 0x2f) x = x * 0xa + (ch ^ 0x30);

    x = sign ? x : -x;

  }

  FILEIN& operator>>(int& x) { return read(x), *this; }

  FILEIN& operator>>(unsigned& x) { return read(x), *this; }

} in;

struct FILEOUT {

  const static int LIMIT = 0x114514;

  char quq[SZ], ST[0x114];

  signed sz, O;

  ~FILEOUT() { flush(); }

  void flush() {

    fwrite(quq, 1, O, stdout);

    fflush(stdout);

    O = 0;

  }

  FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }

  FILEOUT& operator<<(string str) {

    if (O > LIMIT) flush();

    for (char c : str) quq[O++] = c;

    return *this;

  }

  Tp<class T> void write(T x) {

    if (O > LIMIT) flush();

    if (x < 0) {

      quq[O++] = 0x2d;

      x = -x;

    }

    do {

      ST[++sz] = x % 0xa ^ 0x30;

      x /= 0xa;

    } while (x);

    while (sz) quq[O++] = ST[sz--];

    return;

  }

  FILEOUT& operator<<(int x) { return write(x), *this; }

  FILEOUT& operator<<(unsigned x) { return write(x), *this; }

} out;

int n, m;

struct P {

  priority_queue<int> a, b;

  inline void push(int x) { a.push(x); }

  inline void erase(int x) { b.push(x); }

  inline int top() {

    while (!a.empty() && !b.empty() && a.top() == b.top()) a.pop(), b.pop();

    if (a.empty()) return -1;

    return a.top();

  }

};

const int maxn = 1e5 + 51;

P s[maxn << 2];

void upd(int a, int b, int l, int r, int rt, int x) {

  if (a <= l && r <= b) {

    s[rt].push(x);

    return;

  }

  int mid = l + r >> 1;

  if (a <= mid) upd(a, b, l, mid, rt << 1, x);

  if (b > mid) upd(a, b, mid + 1, r, rt << 1 | 1, x);

}

void erase(int a, int b, int l, int r, int rt, int x) {

  if (a <= l && r <= b) {

    s[rt].erase(x);

    return;

  }

  int mid = l + r >> 1;

  if (a <= mid) erase(a, b, l, mid, rt << 1, x);

  if (b > mid) erase(a, b, mid + 1, r, rt << 1 | 1, x);

}

int ans = -1;

void qry(int l, int r, int x, int rt) {

  cmax(ans, s[rt].top());

  if (l == r) return;

  int mid = l + r >> 1;

  (x <= mid) ? qry(l, mid, x, rt << 1) : qry(mid + 1, r, x, rt << 1 | 1);

}

vector<int> g[maxn];

int sz[maxn], son[maxn], d[maxn], fa[maxn];

void dfs(int u) {

  sz[u] = 1;

  for (int v : g[u])

    if (v ^ fa[u]) {

      fa[v] = u, d[v] = d[u] + 1, dfs(v), sz[u] += sz[v];

      if (sz[v] > sz[son[u]]) son[u] = v;

    }

}

int top[maxn], dfn[maxn], idx = 0;

void dfs(int u, int t) {

  dfn[u] = ++idx, top[u] = t;

  if (son[u]) dfs(son[u], t);

  for (int v : g[u])

    if (v ^ fa[u] && v ^ son[u]) dfs(v, v);

}

vector<pii> v, vec;

void swap(int& x, int& y) { x ^= y ^= x ^= y; }

void upd(int x, int y, int c) {

  v.clear(), vec.clear();

  while (top[x] ^ top[y]) {

    if (d[top[x]] < d[top[y]]) swap(x, y);

    v.push_back({ dfn[top[x]], dfn[x] });

    x = fa[top[x]];

  }

  if (d[x] > d[y]) swap(x, y);

  v.push_back({ dfn[x], dfn[y] });

  sort(v);

  int las = 1;

  for (pii x : v) {

    if (x.first > las) vec.push_back({ las, x.first - 1 });

    las = x.second + 1;

  }

  if (las <= n) vec.push_back({ las, n });

  for (pii x : vec) upd(x.first, x.second, 1, n, 1, c);

}

void erase(int x, int y, int c) {

  v.clear(), vec.clear();

  while (top[x] ^ top[y]) {

    if (d[top[x]] < d[top[y]]) swap(x, y);

    v.push_back({ dfn[top[x]], dfn[x] });

    x = fa[top[x]];

  }

  if (d[x] > d[y]) swap(x, y);

  v.push_back({ dfn[x], dfn[y] });

  sort(v);

  int las = 1;

  for (pii x : v) {

    if (x.first > las) vec.push_back({ las, x.first - 1 });

    las = x.second + 1;

  }

  if (las <= n) vec.push_back({ las, n });

  for (pii x : vec) erase(x.first, x.second, 1, n, 1, c);

}

const int maxm = 2e5 + 52;

int A[maxm], B[maxm], V[maxm];

signed main() {

#ifdef _WIN64

  freopen("testdata.in", "r", stdin);

#else

  ios_base ::sync_with_stdio(false);

  cin.tie(nullptr), cout.tie(nullptr);

#endif

  // code begin.

  in >> n >> m;

  rep(i, 2, n) {

    int u, v;

    in >> u >> v, g[u].pb(v), g[v].pb(u);

  }

  dfs(1), dfs(1, 1);

  rep(i, 1, m) {

    int op;

    in >> op;

    if (op == 0) {

      int x, y, c;

      in >> x >> y >> c;

      upd(x, y, c);

      A[i] = x, B[i] = y, V[i] = c;

    }

    if (op == 1) {

      int t;

      in >> t, erase(A[t], B[t], V[t]);

    }

    if (op == 2) {

      int u;

      in >> u, ans = -1, qry(1, n, dfn[u], 1);

      out << ans << '\n';

    }

  }

  return 0;

  // code end.

}
巴特西

[HNOI2016]网络 [树链剖分，可删除堆]

最新文章

热门文章
