UOJ Logo immortalCO的博客

博客

【广告向】求更优算法：带Link、Cut树上路径k小值

2015-08-04 19:13:08 By immortalCO

本萌萌哒弱菜出了一题（其实思路是集训队论文给的），但～算法不是很优美，求各位神犇去虐一虐～～～

提交地址

http://www.lydsy.com/JudgeOnline/problem.php?id=4234

测试数据

测试数据： http://pan.baidu.com/s/1qWDV9la 密码： c7nj

命题报告：http://pan.baidu.com/s/1o6qtgJC （写的很傻逼，神犇轻D）

如果有了更优的算法，一定记得告诉本弱菜一声哦～～～

代码什么的

写的很长，因为前面有2k的输入输出优化……

lgg语句是debug语句

具体实现和命题报告里的有一些差别

//pb_ds NOI template 20150710
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <cmath>
#include <vector>
#include <set>
#include <utility>
#include <queue>
#define For(i, a, b) for(register int i = a, ___u = b; i <= ___u; ++i)
#define ForDown(i, a, b) for(register int i = b, ___d = a; i >= ___d; --i)
#define cmax(i, j) ((i) < (j) ? (i) = (j) : (i))
#define cmin(i, j) ((i) > (j) ? (i) = (j) : (i))
#define dmax(i, j) ((i) > (j) ? (i) : (j))
#define dmin(i, j) ((i) < (j) ? (i) : (j))
#define ddel(i, j) ((i) > (j) ? (i) - (j) : (j) - (i))

#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>

namespace io
{
    const int MAXBUF = 1 << 18;
    char B[MAXBUF], *S = B, *T = B;
    #define getc() (S == T && (T = (S = B) + fread(B, 1, MAXBUF, stdin), S == T) ? 0 : *S++)
    inline int F()
    {
        register int ch, aa = 0, bb = 0;
        register char *S = io::S, *T = io::T;
        for(ch = getc(); (ch < '0' || ch > '9') && ch != '-'; ch = getc())
            ;
        for(ch == '-' ? bb = 1 : aa = ch - '0', ch = getc(); '0' <= ch && ch <= '9'; ch = getc())
            aa += (aa << 3) + aa + ch - '0';
        io::S = S, io::T = T;
        return bb ? -aa : aa; 
    }

    inline double Ff()
    {
        register double aa, bb;
        register char ch;
        register char *S = io::S, *T = io::T;
        while(ch=getc(),(ch<'0'||ch>'9'))
            ;aa=ch-'0';
        while(ch=getc(),(ch>='0'&&ch<='9'))aa=aa*10+ch-'0';
        if(ch=='.'){bb=1;while(ch=getc(),ch>='0'&&ch<='9')bb*=0.1,aa+=bb*(ch-'0');}
        io::S = S, io::T = T;
        return aa;
    }

    char buff[MAXBUF], *iter = buff;
    template<class T>inline void P(register T x, register char ch = '\n')
    {
        static int stack[110];
        register int O = 0;
        register char *iter = io::iter;
        if(!x)*iter++ = '0';
        else
        {
            (x < 0) ? x = -x, *iter++ = '-' : 1;
            for(; x; x /= 10)
                stack[++O] = x % 10;
            for(; O; *iter++ = '0' + stack[O--])
                ;
        }
        *iter++ = ch, io::iter = iter;
    }

    inline int gets(register char *o)
    {
        register char *s = o, ch = getc();
        for(; ch && (ch == ' ' || ch == '\n'); ch = getc())
            ;
        for(; ch && (ch != ' ' && ch != '\n'); ch = getc())
            *s++ = ch;
        *s = 0;
        return s - o;
    }

    inline void output() {fwrite(buff, 1, iter - buff, stdout);}
}

#include <ext/pb_ds/priority_queue.hpp>

namespace pb_ds
{
    using io::F;
    using io::P;
    #define RG register
    int n;
    const int MAXN = 200010, MAXM = 400010;
    namespace lct
    {
        const int MAXN = pb_ds::MAXN << 1;
        int tot;
        int fa[MAXN], son[MAXN][2], time[MAXN], cho[MAXN];
        bool rev[MAXN], mark[MAXN], have[MAXN];
        #define type(i) (son[fa[i]][1] == (i))
        #define not_root(i) (son[fa[i]][type(i)] == (i))
        inline void push_up(register int i)
        {
            static int A, B;
            have[i] = have[son[i][0]] || mark[i] || have[son[i][1]];
            time[i] < time[cho[i] = ((time[A = cho[son[i][0]]] < time[B = cho[son[i][1]]]) ? A : B)]
                ? cho[i] = i : 1;
///*lgg*/assert(time[cho[i]] <= time[i] && time[cho[i]] <= time[cho[son[i][0]]] && time[cho[i]] <= time[cho[son[i][1]]]);
        }
        inline void push_down(register int i)
        {
            if(rev[i])
            {
                rev[i] = 0, rev[son[i][0]] ^= 1, rev[son[i][1]] ^= 1;
                register int t = son[i][0]; son[i][0] = son[i][1], son[i][1] = t;
            }
        }
        inline void rotate(register int i)
        {
            register int f = fa[i], t = type(i);
            fa[i] = fa[f], not_root(f) ? son[fa[f]][type(f)] = i : 1;
            (son[f][t] = son[i][!t]) ? fa[son[f][t]] = f : 1;
            push_up(son[fa[f] = i][!t] = f);
        }
        inline void preview(register int i)
        {
            if(not_root(i)) preview(fa[i]);
            push_down(i);
        }
        inline void splay(register int i, register bool need = 1)
        {
            if(need) preview(i);
            for( ; not_root(i); rotate(i))
                if(not_root(fa[i])) rotate(type(i) ^ type(fa[i]) ? i : fa[i]);
            push_up(i);
        }
        inline void dfs_print(register int i)
        {
            if(!i)return;
            dfs_print(son[i][0]);
            printf("%d ", i);
            dfs_print(son[i][1]);
        }
        inline void debug(register int root)
        {
            splay(root);
            printf("root = %d chain = ", root);
            dfs_print(root);
            puts("");
        }
        inline int access(register int i)
        {
            register int j = 0;
            for( ; i; splay(i), son[i][1] = j, j = i, i = fa[i])
                ;
            return j;
        }
        inline int query(RG int x, RG int y) {return access(x), access(y);}
        inline void make_root(register int i) {access(i), splay(i, 0), rev[i] ^= 1;}
        inline void link(register int i, register int j) 
        {
///*lgg*/printf("link %d ~ %d\n", i, j);
            make_root(i), fa[i] = j;
///*lgg*///printf("linked "); debug(j);
        }
        inline void cut(register int i, register int j) 
        {
            make_root(i), access(j), splay(i, 0), son[i][1] = fa[j] = 0;
///*lgg*/ assert(son[i][1] == j);
///*lgg*/// puts("cut"); printf("i: "); debug(i); printf("j: "); debug(j);
        }
        inline int find_root(register int i)
        {
            for(access(i), splay(i, 0); son[i][0]; i = son[i][0])
                ;
            return i;
        }
        inline int expose(register int i, register int j) 
        {
            if(i == j) return j;
            make_root(i), access(j), splay(j, 0);
            return j;
        }
        inline void set_mark(RG int i, RG bool b)
        {
            splay(i), mark[i] = b, push_up(i);
        }    
    }
    namespace graph
    {
        int fir[MAXN], tot = 1, next[MAXM], to[MAXM];
        inline void reset() {memset(fir, 0, sizeof fir); tot = 1;}
        inline void link(RG int x, RG int y)
        {
            next[++tot] = fir[x], to[fir[x] = tot] = y;
            next[++tot] = fir[y], to[fir[y] = tot] = x;
        }    
    }
    namespace segment
    {
        const int MAXNODE = 10000000;
        const int LL = 1, RR = 1000000;
        int tot, lef[MAXNODE], rig[MAXNODE], size[MAXNODE];
        inline int insert(RG int val, RG int old, RG int l = LL, RG int r = RR)
        {
            RG int at = ++tot;
            size[at] = size[old] + 1;
///*lgg*/if(l==LL&&r==RR)printf("insert val = %d at = %d l = %d r = %d size = %d\n", val, at, l, r, size[at]);
            if(l < r)
            {
                RG int m = (l + r) >> 1;
                (val <= m)
                    ? (lef[at] = insert(val, lef[old], l, m), rig[at] = rig[old])
                    : (lef[at] = lef[old], rig[at] = insert(val, rig[old], m + 1, r));
///*lgg*/assert(size[at] == size[lef[at]] + size[rig[at]]);
            }
            return at;
        }
    }
    int val[MAXN];
    struct E {int x, y;} e[MAXN];
    int root[MAXN], top[MAXN], fa[MAXN], dep[MAXN] = {0, 1};
    bool chosen[MAXN], vis[MAXN];
    inline int dfs_init(RG int at)
    {
///*lgg*///printf("at = %d fa = %d\n", at, fa[at]);
        using namespace graph;
        root[at] = segment::insert(val[at], root[fa[at]]);
        vis[at] = 1;
        RG int size = 1, cho = 0, max_cho = 0, d = dep[at] + 1, temp;
        for(RG int i = fir[at]; i; i = next[i])
            !vis[to[i]]
                ?    fa[to[i]] = at, dep[to[i]] = d,
                     size += (temp = dfs_init(to[i])), 
                    temp > max_cho ? cho = to[i], max_cho = temp : 1 : 1;
        chosen[cho] = 1;
///*lgg*///printf("dfs_init at = %d val = %d dep = %d size = %d cho = %d\n", at, val[at], dep[at], size, cho);
        return size;
    }
    inline void dfs_make(RG int at)
    {
///*lgg*/printf("at = %d fa = %d\n", at, fa[at]);
        using namespace graph;
        vis[at] = 0,
        top[at] = (chosen[at] ? top[fa[at]] : at);
///*lgg*///printf("at = %d top = %d\n", at, top[at]);
        for(RG int i = fir[at]; i; i = next[i])
            if(vis[to[i]]) dfs_make(to[i]);
    }
    inline int lca(RG int x, RG int y)
    {
        while(top[x] != top[y])
            dep[top[x]] > dep[top[y]]
                ? x = fa[top[x]] : y = fa[top[y]];
        return dep[x] < dep[y] ? x : y;
    }
    struct Change {int at, val, cnt; } change[MAXN];
    struct Segment {int root, cnt; } seg[MAXN];
    int change_cnt, seg_cnt;
    int marked[MAXN], marked_cnt;
    namespace lct
    {
        inline void dfs(RG int at)
        {
            if(!have[at]) return;
            push_down(at);
            dfs(son[at][0]);
///*lgg*///printf("at = %d\n", at);
            if(mark[at])
            {
///*lgg*/printf("found mark %d\n", at);
                marked[++marked_cnt] = at;
            }
            dfs(son[at][1]);
        }
    }
    inline void build()
    {
        RG int x, y;
        graph::reset();
        segment::tot = change_cnt = 0;
        memset(chosen, 0, sizeof chosen);
        For(i, 1, n) 
            if(lct::mark[i]) lct::set_mark(i, 0);
        For(i, n + 1, n + n - 1)
        {
            graph::link(x = e[i].x, y = e[i].y);
            if(lct::mark[i])
                lct::set_mark(i, 0);
///*lgg*/assert(!lct::mark[i]);
///*lgg*/printf("link %d ~ %d time = %d\n", x, y, lct::time[i]+(1<<30));
        }
///*lgg*/For(i,0,n*2)assert(!lct::mark[i]);
        fa[1] = 0;
        dfs_init(1);
        dfs_make(1);
    }


    inline void main()
    {
        n = F();
        RG int q = F(), H = 2 * sqrt(n), timer = -1 << 30;
        For(i, 1, n) val[i] = F();
        RG int x, y;
        For(i, n + 1, n + n - 1)
        {
            e[i] = (E) {x = F(), y = F()};
            lct::time[i] = ++timer;
            lct::link(x, i);
            lct::link(i, y);
        }
        build();
        RG int k, modify_tot = 0, cho;
///*lgg*/printf("H = %d\n", H);
        For(aaaa, 1, q)
        {
            k = F(), x = F(), y = F();
///*lgg*/if(k==-2)build();else
            if(k == -1)
            {
                cho = lct::cho[lct::expose(x, y)];
                lct::cut(e[cho].x, cho);
                lct::cut(cho, e[cho].y);
///*lgg*/printf("replace %d (%d ~ %d) time = %d with (%d ~ %d) time = %d\n", cho, e[cho].x, e[cho].y,lct::time[cho]+(1<<30),x,y,timer+1+(1<<30));
                e[cho] = (E) {x, y};
                lct::time[cho] = ++timer;
                lct::mark[cho] = lct::mark[x] = lct::mark[y] = 1;
                lct::link(x, cho);
                lct::link(cho, y);
                if(!(++modify_tot % H))
                    build();
                lct::expose(x, y);
///*lgg*///lct::debug(lct::expose(x,y));
            }
            else if(!k)
            {
                change[++change_cnt] = (Change) {x, val[x], -1};
///*lgg*/printf("change at = %d cnt[%d] -1 cnt[%d] +1\n", x,val[x],y);
                change[++change_cnt] = (Change) {x, val[x] = y, 1};
                if(!(++modify_tot % H))
                    build();
            }
            else
            {
///*lgg*/printf("query %d %d\n", x, y);
                if(x == y)
                {
                    P(val[x]);
                    continue;
                }
                seg_cnt = marked_cnt = 0;
                if(!lct::mark[x]) marked[++marked_cnt] = x;
                lct::dfs(lct::expose(x, y));
                if(!lct::mark[y]) marked[++marked_cnt] = y;

                //现在是处理mark的点的时候
                marked[++marked_cnt] = MAXN;
                RG int a, b, c;
                For(i, 1, marked_cnt)
                {
                    a = marked[i];
                    while(marked[i] <= n) ++i;
                    b = marked[i - 1];
                    if(a == b)
                    {
                        seg[++seg_cnt] = (Segment) {root[a], 1};
                        if(fa[a])seg[++seg_cnt] = (Segment) {root[fa[a]], -1};    
///*lgg*/printf("add_point %d fa = %d\n", a, fa[a]);                    
                    }
                    else
                    {
                        c = lca(a, b);
                        seg[++seg_cnt] = (Segment) {root[a], 1};
                        seg[++seg_cnt] = (Segment) {root[b], 1};
                        seg[++seg_cnt] = (Segment) {root[c], -1};
                        if(fa[c])seg[++seg_cnt] = (Segment) {root[fa[c]], -1};
///*lgg*/printf("add_chain %d ~ %d lca = %d flca = %d\n", a, b, c, fa[c]);
                    }
                }

                static int temp[2][MAXN];
                RG int *f = temp[0], *g = temp[1], *t, l = segment::LL, r = segment::RR, left, m;
                f[0] = 0, lct::make_root(x);
                For(i, 1, change_cnt)
                    if(lct::query(y, change[i].at) == change[i].at)
                        f[++f[0]] = i;
///*lgg*/For(i, 1,seg_cnt)printf("root = %d cnt = %d size = %d\n", seg[i].root, seg[i].cnt, segment::size[seg[i].root]); 
                while(l < r)
                {
///*lgg*/printf("l = %d r = %d k = %d m = %d\n", l, r, k, (l+r)/2);
///*lgg*/For(i,1,f[0])printf("assoc change at = %d val = %d cnt = %d\n", change[f[i]].at, change[f[i]].val, change[f[i]].cnt);
                    left = 0;
                    m = (l + r) >> 1;
                    For(i, 1, seg_cnt)
                        left += segment::size[segment::lef[seg[i].root]] * seg[i].cnt;
///*lgg*/printf("segment left = %d\n", left);
                    For(i, 1, f[0])
                        if(change[f[i]].val <= m)
                            left += change[f[i]].cnt;
///*lgg*/printf("segment + change left = %d\n", left);    
                    if(k <= left)
                    {
                        r = m;
                        For(i, 1, seg_cnt)
                            seg[i].root = segment::lef[seg[i].root];
                        g[0] = 0;
                        For(i, 1, f[0])
                            if(change[f[i]].val <= m)
                                g[++g[0]] = f[i];
                    }                
                    else
                    {
                        l = m + 1;
                        k -= left;
                        For(i, 1, seg_cnt)
                            seg[i].root = segment::rig[seg[i].root];
                        g[0] = 0;
                        For(i, 1, f[0])
                            if(m < change[f[i]].val)
                                g[++g[0]] = f[i];
                    }
                    t = g, g = f, f = t;
///*lgg*/getchar();    
                }
///*lgg*/printf("ans = %d\n", l);
                P(l);

            }
//if(!(modify_tot % H)) fprintf(stderr, "rebuild i = %d\n", aaaa);
        }
        io::output();
    }
}

int main()
{
    pb_ds::main();
}

评论

wangyisong1996
跪！ @ link-cut jry
xllend3
%%%
YJMWOI
%%%
worse
。。。。。据说Topology Tree可以$O(\sqrt{N})$。。。？（雾
immortalCO
@vfleaking 这题是否可以添加到UOJ题库中？ ![233](http://img.uoj.ac/utility/bear-applaud.gif) 题面和数据都有了……时间限制除以2即可…… 希望能搜集到更多神犇的更优解

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

Server time: 2024-04-17 08:00:05