BZOJ 1146: [CTSC2008]网络管理Network

树上路径第k大
二分第k大是哪个再check有几个大于mid的即可~
这题就是传说中的只能用树链剖分而不能用动态树做的题!!!
[好像是一个模板题么 = =]
写了快400行的代码 (好吧我写得真心za….)
看到网上某犇随便虐了个130行代码水过瞬间就跪烂了。。。。。
另。我们机房的电脑是有多慢。。。
跑第三个点就要16s+ 跑所有点差不多150s
在八中跑所有点才用了10s+!!!
<以后一定不能相信机房电脑的运行速度= =>
————————–code————————————

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 100005;
struct point
{
  int sum, fa, id, deep, hav, v;
}a[maxn];
struct line
{
  int to, next;
}li[maxn * 2];
struct seg_tree
{
  int root, fa, n;
}st[maxn * 8];
struct seg_node
{
  int l, r, lf, rt, root;
}sn[maxn * 8];
struct splay_node
{
  int l, r, fa, sum, v, faa;
}t[maxn * 15];
int n, q, l, be[maxn], n_lt, n_st, n_sn, n_spn, tt[maxn], m;
void makeline(int fr, int to)
{
  l++;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}
int makesplaytree(int v, int faa)
{
  n_spn++;
  t[n_spn].sum = 1;
  t[n_spn].v = v;
  t[n_spn].faa = faa;
  return n_spn;
}
void left(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].r = t[now].l;
  t[t[now].l].fa = fa;
  t[now].l = fa;
  t[fa].fa = now;
  t[fa].sum = t[t[fa].l].sum + t[t[fa].r].sum + 1;
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
}
void right(int now)
{
  int fa = t[now].fa;
  t[now].fa = t[fa].fa;
  if (t[t[fa].fa].l == fa) t[t[fa].fa].l = now;
  if (t[t[fa].fa].r == fa) t[t[fa].fa].r = now;
  t[fa].l = t[now].r;
  t[t[now].r].fa = fa;
  t[now].r = fa;
  t[fa].fa = now;
  t[fa].sum = t[t[fa].l].sum + t[t[fa].r].sum + 1;
  t[now].sum = t[t[now].l].sum + t[t[now].r].sum + 1;
}
void splay(int now, int ffa)
{
  while (t[now].fa != ffa)
  {
    int fa = t[now].fa;
    if (t[fa].fa == ffa)
      if (t[fa].l == now) right(now);
      else left(now);
    else
      if (t[t[fa].fa].l == fa)
        if (t[fa].l == now) right(fa), right(now);
        else left(now), right(now);
      else
        if (t[fa].l == now) right(now), left(now);
        else left(fa), left(now);
  }
  if (t[now].fa == 0) sn[t[now].faa].root = now;
}
void inssplaynode(int root, int v, int faa)
{
  n_spn++;
  int now = n_spn;
  t[now].sum = 1;
  t[now].v = v;
  t[now].faa = faa;
  while (true)
  {
    t[root].sum++;
    if (v <= t[root].v)
    {
      if (t[root].l) root = t[root].l;
      else
      {
        t[root].l = now;
        t[now].fa = root;
        break;
      }
    }
    else
    {
      if (t[root].r) root = t[root].r;
      else
      {
        t[root].r = now;
        t[now].fa = root;
        break;
      }
    }
  }
  splay(now, 0);
}
int mksegtree(int l, int r)
{
  n_sn++;
  int now = n_sn;
  sn[now].l = l;
  sn[now].r = r;
  if (l == r)
  {
    sn[now].root = makesplaytree(tt[l], now);
    return now;
  }
  int mid = (l + r) / 2;
  sn[now].lf = mksegtree(l, mid);
  sn[now].rt = mksegtree(mid + 1, r);
  sn[now].root = makesplaytree(tt[l], now);
  for (int i = l + 1; i <= r; i++) inssplaynode(sn[now].root, tt[i], now);
  return now;
}
void makesegtree(int now)
{
  m = 1;
  n_st++;
  st[n_st].fa = now;
  while (now)
  {
    tt[m++] = a[now].v;
    a[now].id = n_st;
    now = a[now].hav;
  }
  m -= 1;
  st[n_st].n = m;
  st[n_st].root = mksegtree(1, m);
}
void makerealtree(int now, int fa, int d)
{
  a[now].fa = fa;
  a[now].sum = 1;
  a[now].deep = d;
  int mx = 0, k = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (to == fa) continue;
    makerealtree(to, now, d + 1);
    a[now].sum += a[to].sum;
    if (a[to].sum > mx)
    {
      if (k) makesegtree(k);
      mx = a[to].sum;
      k = to;
    }
    else makesegtree(to);
  }
  a[now].hav = k;
}
int lca(int fr, int to)
{
  while (a[fr].id != a[to].id)
  {
    if (a[st[a[fr].id].fa].deep < a[st[a[to].id].fa].deep) swap(fr, to);
    fr = a[st[a[fr].id].fa].fa;
  }
  return a[fr].deep < a[to].deep ? fr : to;
}
int getnum(int fr, int to)
{
  int t = lca(fr, to);
  return a[to].deep + a[fr].deep – a[t].deep * 2 + 1;
}
int querysplay(int now, int k)
{
  int ans = 0;
  while (now)
  {
    if (t[now].v >= k) now = t[now].l;
    else
    {
      ans += t[t[now].l].sum + 1;
      now = t[now].r;
    }
  }
  return ans;
}
int get(int now, int l, int r, int k)
{
  if (sn[now].l >= l && sn[now].r <= r) return querysplay(sn[now].root, k);
  int mid = (sn[now].l + sn[now].r) / 2;
  int ans = 0;
  if (l <= mid) ans += get(sn[now].lf, l, r, k);
  if (r >= mid + 1) ans += get(sn[now].rt, l, r, k);
  return ans;
}
int check(int fr, int to, int k)
{
  int ans = 0;
  while (a[fr].id != a[to].id)
  {
    if (a[st[a[fr].id].fa].deep < a[st[a[to].id].fa].deep) swap(fr, to);
    ans += get(st[a[fr].id].root, 1, a[fr].deep – a[st[a[fr].id].fa].deep + 1, k);
    fr = a[st[a[fr].id].fa].fa;
  }
  if (a[fr].deep < a[to].deep) swap(fr, to);
  return ans + get(st[a[fr].id].root, a[to].deep – a[st[a[fr].id].fa].deep + 1, a[fr].deep – a[st[a[fr].id].fa].deep + 1, k);
}
int query(int fr, int to, int k)
{
  int l = 0;
  int r = 100000001;
  while (l + 1 < r)
  {
    int mid = (l + r) / 2;
    if (check(fr, to, mid) >= k) r = mid;
    else l = mid;
  }
  return l;
}
int findsmaller(int now)
{
  now = t[now].l;
  while (t[now].r) now = t[now].r;
  return now;
}
int findbigger(int now)
{
  now = t[now].r;
  while (t[now].l) now = t[now].l;
  return now;
}
void splaych(int now, int fr, int to, int faa)
{
  while (now)
  {
    if (t[now].v == fr) break;
    if (t[now].v < fr) now = t[now].r;
    else now = t[now].l;
  }
  splay(now, 0);
  if (!t[now].l && !t[now].r)
  {
    t[now].v = to;
    return;
  }
  if (!t[now].l)
  {
    sn[faa].root = t[now].r;
    t[t[now].r].fa = 0;
  }
  else
  if (!t[now].r)
  {
    sn[faa].root = t[now].l;
    t[t[now].l].fa = 0;
  }
  else
  {
    int t1 = findsmaller(now);
    int t2 = findbigger(now);
    splay(t1, 0);
    splay(t2, t1);
    t[t2].l = 0;
    t[t2].sum–;
    t[t1].sum–;
  }
  inssplaynode(sn[faa].root, to, faa);
}
void segch(int now, int lr, int fr, int to)
{
  splaych(sn[now].root, fr, to, now);
  if (sn[now].l == sn[now].r) return;
  int mid = (sn[now].l + sn[now].r) / 2;
  if (lr <= mid) segch(sn[now].lf, lr, fr, to);
  else segch(sn[now].rt, lr, fr, to);
}
void change(int now, int k)
{
  segch(st[a[now].id].root, a[now].deep – a[st[a[now].id].fa].deep + 1, a[now].v, k);
  a[now].v = k;
}
int main()
{
  int test;
  scanf(“%d%d”, &n, &test);
  for (int i = 1; i <= n; i++) scanf(“%d”, &a[i].v);
  for (int i = 1; i < n; i++)
  {
    int fr, to;
    scanf(“%d%d”, &fr, &to);
    makeline(fr, to);
    makeline(to, fr);
  }
  makerealtree(1, 0, 1);
  makesegtree(1);
  for (int i = 0; i < test; i++)
  {
    int k, fr, to;
    scanf(“%d%d%d”, &k, &fr, &to);
    if (!k) change(fr, to);
    else
    {
      int t = getnum(fr, to);
      if (t < k) printf(“invalid request!\n”);
      else printf(“%d\n”, query(fr, to, t – k + 1));
    }
  }

}

 

发表评论