BZOJ1146 [CTSC2008]网络管理Network

2014.12.31 10:30 Wed| 16 visits oi_2015| 2015_刷题日常| Text

Solution

CTSC这是和网络有仇么?到处都是网络网络网络……

上课的时候提到这个题的时候我都忘记了是哪一个了……

不得不佩服这道题考察真是全面:树链剖分+二分法+线段树套平衡树……

求两点间第K大值的时候可以用树链剖分找出DFS树上的区间,然后二分答案,利用树套树验证。

其实这份代码敲起来还是蛮爽的……我平衡树萌萌哒的的模板君真是可爱。

另外,Splay常数大的证据(这也没差多少啊,那道题为毛不A……)

824223 1146 Accepted 67656 kb 22864 ms C++/Splay 9466 B

824196 1146 Accepted 67196 kb 16684 ms C++/Treap 8264 B

Code

注:Treap的模板请参见本人其他博客。

#include <bits/stdc++.h>
using namespace std;

//=============<Treap>===============

namespace Treap
{
}

//============<Declare>==============

#define N 80005
#define M 160005
#define lson (pos<<1)
#define rson (pos<<1|1)

int n, q, a[N], head[N], cnt, now;
int size[N], deep[N], fa[N], son[N], top[N], p_id[N], id_p[N];
Treap::treap<int> t[N << 2];

//============<Add Edge>=============

struct data{
    int next, to;
} edge[M];

inline void add(int x, int y)
{
    edge[++cnt].to = y;
    edge[cnt].next = head[x];
    head[x] = cnt;
}

//====<Heavy Path Decomposition>=====

void dfs(int x, int d)
{
    size[x] = 1; deep[x] = d;
    for(int y, i = head[x]; i; i = edge[i].next)
        if((y = edge[i].to) != fa[x])
        {
            fa[y] = x;
            dfs(y, x+1);
            if(size[y] > size[son[x]])
                son[x] = y;
            size[x] += size[y];
        }
}

void create(int x, int d)
{
    p_id[x] = ++now;
    id_p[now] = x;
    top[x] = d;
    if(son[x]) create(son[x], d);
    for(int y, i=head[x]; i; i = edge[i].next)
        if((y = edge[i].to) != fa[x] && y != son[x])
            create(y, y);
}

//==========<Segment Tree>===========

void build(int pos, int l, int r)
{
    if(l == r) { t[pos].insert(a[id_p[l]]); return ; }
    int mid = (l+r) >> 1;
    build(lson, l, mid);
    build(rson, mid+1, r);
    t[pos].insert(t[lson]);
    t[pos].insert(t[rson]);
}

void modify(int pos, int l, int r, int p, int x, int y)
{
    t[pos].erase(x); t[pos].insert(y);
    if(l == r) return;
    int mid = (l+r) >> 1;
    if(p <= mid) modify(lson, l, mid, p, x, y);
    else modify(rson, mid+1, r, p, x, y);
}

int seg_query(int pos, int l, int r, int x, int y, int z)
{
    if(x<=l && r<=y) return t[pos].size() - t[pos].find(z) + 1;
    int mid = (l+r) >> 1, re = 0;
    if(x <= mid) re += seg_query(lson, l, mid, x, y, z);
    if(y > mid) re += seg_query(rson, mid+1, r, x, y, z);
    return re;
}

//=========<Binary Search>==========

typedef vector< pair<int, int> > vec;

int search(vec &v, int k)
{
    int l = 0, r = 100000000, re = 0;
    vec::iterator it;
    while(l <= r)
    {
        int mid = (l+r) >> 1, temp = 0;
        for(it = v.begin(); it != v.end(); ++it)
            temp += seg_query(1, 1, n, it->first, it->second, mid);
        if(temp < k) r = mid - 1;
        else l = mid + 1, re = mid;
    }
    return re;
}

//=========<Query on Tree>===========

int tree_query(int x, int y, int k)
{
    int f1 = top[x], f2 = top[y], re = 0;
    vec v;
    while(f1 != f2)
    {
        if(deep[f1] < deep[f2])
            swap(x, y), swap(f1, f2);
        v.push_back(make_pair(p_id[f1], p_id[x]));
        re += p_id[x] - p_id[f1] + 1;
        x = fa[f1]; f1 = top[x];
    }
    if(deep[x] > deep[y])
        swap(x, y);
    v.push_back(make_pair(p_id[x], p_id[y]));
    re += p_id[y] - p_id[x] + 1;
    if(re < k) return -1;
    return search(v, k);
}

//==============<Read>===============

inline int read()
{
    int x=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); }
    return x*f;
}

//==============<Main>===============

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        a[i] = read();
    for(int x, y, i = 1; i < n; i++)
        x = read(), y = read(),
        add(x, y), add(y, x);
    dfs(1, 1);
    create(1, 1);
    build(1, 1, n);
    for(int k, x, y, i = 1; i <= q; i++)
    {
        k = read(); x = read(); y = read();
        if(k == 0)
            modify(1, 1, n, p_id[x], a[x], y), a[x] = y;
        else
        {
            int ans = tree_query(x, y, k);
            if(ans == -1) puts("invalid request!");
            else printf("%d\n", ans);
        }
    }
}