LCT专题练习

【bzoj2049】洞穴勘测

http://www.cnblogs.com/Sdchr/p/6188628.html

小结

（1）LCT可以方便维护树的连通性，但是图的连通性的维护貌似很麻烦。

【bzoj1050】旅行

题意

给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。备注：两个顶点之间可能有多条路径。

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

分析

这道题实际上并不需要要LCT。

\(O(n^2)\)的复杂度即可解决。

但是，我们还是要追求更优秀的做法。

将边权排序。

二分最大边与最小边的比值，two pointer+LCT维护连通性。

若起点终点连通即可判定成立。

时间复杂度：\(O(n\log^2 n)\)

【bzoj3669】【noi2014】魔法森林

题意

\(n\)个点，\(m\)条边，每条边有两种属性\(a,b\)。

求一条从\(s\)到\(t\)的路径，最小化\(\max(p_a)+\max(p_b),p\in Path(s,t)\)

分析

分析1

假如我们确定了\(\max(p_a)\)的值，那么\(\max(p_b)\)必然越小越好。

而\(\max(p_a)\)的值只有\(O(m)\)个。

我们先把\(p\)按照\(a\)从小到大排序，同时用SPFA不断松弛\(\max(p_b)\)的大小。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int N=50001;
const int M=100001;

struct E {
    int u,v,a,b;
} edge[M];
int n,m;
int f[N];
int q[N],h,t,v[N];
int d[N],res=M+M;
struct G {
    int v,w,nxt,loc;
} map[M+M];
int tt,hd[N];

inline int read(void) {
    int s=0,f=1;
    char c=getchar();
    for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
    for (; '0'<=c&&c<='9'; c=getchar()) s=s*10+c-'0';
    return s*f;
}

inline int cmp(E ea,E eb) {
    return ea.a<eb.a;
}

inline void ins(int u,int v,int w,int loc) {
    map[++tt].v=v;
    map[tt].w=w;
    map[tt].loc=loc;
    map[tt].nxt=hd[u];
    hd[u]=tt;
}

void init(void) {
    n=read(),m=read();
    for (int i=1; i<=m; i++)
        edge[i].u=read(),edge[i].v=read(),edge[i].a=read(),edge[i].b=read();
    sort(edge+1,edge+m+1,cmp);
    for (int i=1; i<=m; i++) {
        ins(edge[i].u,edge[i].v,edge[i].b,i);
        ins(edge[i].v,edge[i].u,edge[i].b,i);
    }
}

int find(int i) {
    return f[i]==i?i:f[i]=find(f[i]);
}

inline int max(int i,int j) {
    return i>j?i:j;
}

inline void add(int i) {
    if (!v[edge[i].u]) v[edge[i].u]=1,q[t=t%n+1]=edge[i].u;
    if (!v[edge[i].v]) v[edge[i].v]=1,q[t=t%n+1]=edge[i].v;
}

inline int min(int i,int j) {
    return i<j?i:j;
}

void work(void) {
    int ednum=1,fu,fv;
    for (int i=1; i<=n; i++) f[i]=i;
    for (; ednum<=m; ednum++) {
        fu=find(edge[ednum].u),fv=find(edge[ednum].v);
        if (fu^fv) f[fu]=fv;
        fu=find(1),fv=find(n);
        if (fu==fv) break;
    }
    ednum--;

    fu=find(1),fv=find(n);
    if (fu^fv) {
        printf("-1\n");
        return;
    }

    for (int i=2; i<=n; i++) d[i]=M+M;
    q[t=1]=1,v[1]=1;
    for (int i=1; i<ednum; i++) add(i);

    int now,w;
    for (; ednum<=m; ednum++) {
        add(ednum);
        for (; h^t;) {
            now=q[h=h%n+1];
            for (int k=hd[now]; k; k=map[k].nxt)
                if (map[k].loc<=ednum) {
                    w=max(map[k].w,d[now]);
                    if (w<d[map[k].v]) {
                        d[map[k].v]=w;
                        if (!v[map[k].v]) q[t=t%n+1]=map[k].v,v[map[k].v]=1;
                    }
                }
            v[now]=0;
        }
        res=min(res,edge[ednum].a+d[n]);
    }
    printf("%d\n",res);
}

int main(void) {
    init();
    work();
    return 0;
}

分析2

我们先把\(p\)按照\(a\)从小到大排序，用LCT维护\(\max(p_b)\)的大小，即动态维护最小生成树。

把边拆成一个点。

小结

（1）这一类\(\max(a_i)+\max(b_i)\)类的问题，由于\(a_i\)限定了\(\max(a_i)\)的取值个数为\(O(n)\)，所以我们通常枚举\(\max(a_i)\)的值，通常表现为排序+枚举。

（2）标号逼近

【bzoj2908】【xsy1663】nand

题意

定义A nand B=not(A and B)（运算操作限制了数位位数为K）比如2 nand 3，K=3，则2 nand 3=not (2 and 3)=not 2=5。

给出一棵树，树上每个点都有点权，定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果，例如：从2号点到5号点顺次经过2->3->5，权值分别为5、7、2，K=3，那么最终结果为0 nand 5 nand 7 nand 2=7 nand 7 nand 2=0 nand 2=7。

现在这棵树需要支持以下操作。

① Replace a b:将点a（1≤a≤N）的权值改为b。

② Query a b:输出点a到点b的费用。

请给出一个程序支持这些操作。

分析1：树剖

拆位，用树剖维护。

注意不满足合并，只能一次搞，所以我们线段树内记\(s[2][2]\)。其中\(s[i][j]\)表示：从\(i\)方向出发，初值为\(j\)的遍历完整个区间的答案。

注意在思想上拆位，实际上不要拆位！！！

分析2：LCT

考虑LCT，重链上维护每一个位为0或为1时从链起点走到链终点后的值。查询时只需makeroot然后access，按位计算即可。时间复杂度\(O(nklogn)\)

小结

（1）关于拆位

注意在思想上拆位，实际上不要拆位！！！

（2）这类不满足交换律又不满足结合律的问题，通常预处理之前的答案情况数。

如果之前的答案情况数比较多，那么就用拆位或中途相遇等方法减少。

【hdu3726】【xsy1173】Chef and Graph Queries

分析

把一些边依次加入图中，每次加有两种情况：

①把两个连通块合并

②构成一个环

我们需要统计的就是区间内情况①的个数。

这是一个连续的区间的询问。

考虑能否利用类似于区间减法的性质。

从1到n依次加边，假设当前加到i这条边，那么i能产生影响，当且仅当i比在与i构成环的边的最小编号大。

所以我们从小到大求出\(a_i\)。

然后就是一个区间不同数问题。

离线+树状数组或者可持久化线段树解决。

注意处理自环问题。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <climits>
#include <algorithm>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(a);i>=(b);i--)

const int N=262144;
const int M=262144;
const int S=524288;
const int Q=262144;
const int MAX=INT_MAX>>1;

int cas;

int n,m,qs;
struct Ed {
    int u,v;
    Ed(int _u=0,int _v=0) {
        u=_u,v=_v;
    }
}ed[M];

int a[M],sum[M];
int c[S][2],fa[S]; int keyED[S],minED[S]; int rev[S];
int st[S],top;

int ans[Q];
struct Ask {
    int l,r; int id;
    Ask(int _l=0,int _r=0,int _id=0) {
        l=_l,r=_r; id=_id;
    }
    friend int operator < (Ask a,Ask b) {
        return a.r<b.r;
    }
}q[Q];

int tr[M];

int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

int IsRoot(int x) {
    int pre=fa[x];
    return c[pre][0]!=x&&c[pre][1]!=x;
}

void Clear(int x) {
    if (rev[x]) {
        rev[x]^=1;
        rev[c[x][0]]^=1;
        rev[c[x][1]]^=1;
        swap(c[x][0],c[x][1]);
    }
}

void Pushup(int x) {
    minED[x]=min(minED[c[x][0]],minED[c[x][1]]);
    minED[x]=min(minED[x],keyED[x]);
}

void Rotate(int x) {
    int y=fa[x],z=fa[y];
    int l=!(c[y][0]==x),r=l^1;
    if (!IsRoot(y)) {
        if (c[z][0]==y)
            c[z][0]=x;
        else c[z][1]=x;
    }
    fa[x]=z; fa[y]=x;
    if (c[x][r]>0) fa[c[x][r]]=y;
    c[y][l]=c[x][r]; Pushup(y);
    c[x][r]=y; Pushup(x);
}

void Splay(int x) {
    top=0; st[++top]=x;
    for (int i=x;!IsRoot(i);i=fa[i])
        st[++top]=fa[i];
    per(i,top,1) Clear(st[i]);

    while (!IsRoot(x)) {
        int y=fa[x],z=fa[y];
        if (!IsRoot(y)) {
            if ((c[z][0]==y)^(c[y][0]==x))
                Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}

void Access(int x) {
    int t=0;
//  while (!IsRoot(x)) {
    while (x>0) {
        Splay(x);
        c[x][1]=t; Pushup(x);
        t=x;
        x=fa[x];
    }
}

void Evert(int x) {
    Access(x);
    Splay(x);
    rev[x]^=1;
}

void Link(int x,int y) {
    Evert(x);
    fa[x]=y;
    Splay(x);
}

void Cut(int x,int y) {
    Evert(x);
    Access(y);
    Splay(y);
    fa[x]=c[y][0]=0;
    Pushup(y);
}

int Find(int x) {
    Access(x);
    Splay(x);
    int t=x;
    while (c[t][0]>0)
        t=c[t][0];
    Splay(t);
    return t;
}

int GetMin(int x,int y) {
    Evert(x);
    Access(y);
    Splay(y);
    return minED[y];
}

int Connect(int x,int y,int id) {
    int fx=Find(x),fy=Find(y);
    if (fx!=fy) {
        Link(x,id);
        Link(y,id);
        return 0;
    }
    else {
        int t=GetMin(x,y);
        Cut(ed[t].u,t+n); Cut(ed[t].v,t+n);
        Link(x,id); Link(y,id);
        return t;
    }
}

int lowbit(int i) {
    return i&-i;
}

void Add(int x,int ad) {
    for (int i=x;i<=m;i+=lowbit(i))
        tr[i]+=ad;
}

int GetSum(int x) {
    int sum=0;
    for (int i=x;i>0;i-=lowbit(i))
        sum+=tr[i];
    return sum;
}

int main(void) {
    #ifndef ONLINE_JUDGE
    freopen("zwl.in","r",stdin);
    freopen("zwl.out","w",stdout);
    #endif

    cas=rd();
    rep(tms,1,cas) {
        n=rd(),m=rd(),qs=rd();
        rep(i,1,m) {
            int x=rd(),y=rd();
            ed[i]=Ed(x,y);
        }

        memset(a,0,sizeof a);
        memset(c,0,sizeof c); memset(fa,0,sizeof fa);
        rep(i,0,n) keyED[i]=minED[i]=MAX; rep(i,n+1,n+m) keyED[i]=minED[i]=i-n;
        memset(rev,0,sizeof rev);
        rep(i,1,m) {
            int u=ed[i].u,v=ed[i].v;
            if (u!=v) {
                sum[i]=sum[i-1]+1;
                a[i]=Connect(u,v,i+n);
            }
            else sum[i]=sum[i-1];
        }

        memset(ans,0,sizeof ans); memset(tr,0,sizeof tr);
        rep(i,1,qs) {
            int u=rd(),v=rd();
            q[i]=Ask(u,v,i);
        }
        sort(q+1,q+qs+1);
        int cur=1;
        rep(r,1,m) {
            if (sum[r]!=sum[r-1])
                Add(a[r]+1,1);
            while (cur<=qs&&q[cur].r==r) {
                int t=GetSum(q[cur].l);
                ans[q[cur].id]=n-(t-sum[q[cur].l-1]);
                cur++;
            }
        }
        rep(i,1,qs) printf("%d\n",ans[i]);
    }

    return 0;
}

小结

（1）一些区间问题的解决思路

区间问题：区间加法，区间减法

考虑转化为前缀和，或总和-两边和

ST表，线段树，块状链表，etc

（2）动态树问题中边的处理：拆成两个点

类似的思想：开区间化为闭区间

（3）以后所有的数据结构题最好都写一下吧。

数据结构题是可以练代码能力的。

不借助所有外力的情况下，独自完成调试吧。

虽然肯定会有那么一丢丢的枯燥~

【bzoj3306】【xsy1665】树

题意

给定一棵大小为 n 的有根点权树,支持以下操作:

• 换根

• 修改点权

• 查询子树最小值

分析1：树链剖分

分类讨论的思路：

首先，把重点的情况进行讨论，即当\(x=rt\)时，很明显是整颗子树的最小值。

现在保证点不重了，就要考虑他们的LCA为anc。

当anc与x相重时，答案是由rt向上最靠近过x的祖先的子树的补集的最小值。

除此之外，皆为子树x。

用dfn序即可判断。

WA的常见问题：go(x,len)写错

#include <cstdio>
#include <cctype>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define pb push_back

const int N=131072;
const int S=262144;
const int MAX=INT_MAX>>1;

int n,m;
vector<int> mp[N];
int pre[N],w[N];

int siz[N],dep[N],son[N];
int num,dfn[N],pid[N],top[N];

int rt;
struct Tree {
    int l,r;
    int mv;
    Tree(int _l=0,int _r=0) {
        l=_l,r=_r;
        mv=MAX;
    }
}tr[S];

int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

void Find(int x) {
    siz[x]=1;
    rep(i,1,mp[x].size()) {
        int nx=mp[x][i-1];
        dep[nx]=dep[x]+1;
        Find(nx);
        siz[x]+=siz[nx];
        if (siz[son[x]]<siz[nx]) son[x]=nx;
    }
}

void Split(int x,int anc) {
    num++; dfn[x]=num; pid[num]=x; top[x]=anc;
    if (son[x]>0) Split(son[x],anc);
    rep(i,1,mp[x].size()) {
        int nx=mp[x][i-1];
        if (nx!=son[x]) Split(nx,nx);
    }
}

int LCA(int x,int y) {
    while (top[x]!=top[y]) {
        if (dep[top[x]]>dep[top[y]])
            x=pre[top[x]];
        else y=pre[top[y]];
    }
    if (dep[x]<dep[y]) return x; else return y;
}

int Go(int x,int len) {
    while (1) {
        int anc=top[x];
        if (dep[x]-dep[anc]>=len) {
            int pt=pid[dfn[x]-len];
            return pt;
        }
        len=len-(dep[x]-dep[anc])-1; x=pre[anc];
    }
}

void Pushup(int x) {
    tr[x].mv=min(tr[x<<1].mv,tr[x<<1|1].mv);
}

void Build(int x,int l,int r) {
    tr[x]=Tree(l,r);
    if (l!=r) {
        int mid=(l+r)>>1;
        Build(x<<1,l,mid);
        Build(x<<1|1,mid+1,r);
        Pushup(x);
    }
    else tr[x].mv=w[pid[l]];
}

void Ins(int x,int loc,int ad) {
    if (tr[x].l==tr[x].r) {
        tr[x].mv=ad;
        return;
    }
    int mid=(tr[x].l+tr[x].r)>>1;
    if (loc<=mid)
        Ins(x<<1,loc,ad);
    else Ins(x<<1|1,loc,ad);
    Pushup(x);
}

int Query(int x,int l,int r) {
    if (l<=tr[x].l&&tr[x].r<=r) return tr[x].mv;
    int tmv=MAX; int mid=(tr[x].l+tr[x].r)>>1;
    if (l<=mid) {
        int t=Query(x<<1,l,r);
        tmv=min(tmv,t);
    }
    if (mid<r) {
        int t=Query(x<<1|1,l,r);
        tmv=min(tmv,t);
    }
    return tmv;
}

void Modify(int x,int y) {
    Ins(1,dfn[x],y);
    w[x]=y;
}

void Evert(int x) {
    rt=x;
}

int SubMin(int x) {
    if (x==rt)
        return tr[1].mv;
    int anc=LCA(x,rt);
    if (anc==x) {
        int nx=Go(rt,dep[rt]-dep[anc]-1);
        int res=MAX;
        if (dfn[nx]>1) {
            int t=Query(1,1,dfn[nx]-1);
            res=min(res,t);
        }
        if (dfn[nx]+siz[nx]-1<n) {
            int t=Query(1,dfn[nx]+siz[nx],n);
            res=min(res,t);
        }
        return res;
    }
    int res=Query(1,dfn[x],dfn[x]+siz[x]-1);
    return res;
}

int main(void) {
    #ifndef ONLINE_JUDGE
    freopen("sdchr.in","r",stdin);
    freopen("sdchr.out","w",stdout);
    #endif

    n=rd(),m=rd();
    rep(i,1,n) {
        pre[i]=rd(),w[i]=rd();
        if (pre[i]>0)
            mp[pre[i]].pb(i);
        else rt=i;
    }

    Find(1);
    Split(1,1);
    Build(1,1,n);

    rep(i,1,m) {
        char c; int x,y; scanf("\n"); c=getchar();
        switch (c) {
            case 'V':
                x=rd(),y=rd();
                Modify(x,y);
                break;
            case 'E':
                x=rd();
                Evert(x);
                break;
            case 'Q':
                x=rd();
                int ans=SubMin(x);
                printf("%d\n",ans);
                break;
        }
    }

    return 0;
}

分析2：LCT

LCT+mutiset。

http://blog.csdn.net/geotcbrl/article/details/48576427

小结

（1）对于没有link和cut，有换根的的问题，可以考虑直接使用树链剖分解决，利用一下dfn序的神奇性质。

（2）查询子树的最小值的方法：我们考虑对于每个位置维护一个set维护当前点的点权还有所有虚边的点权。再记一个值为set中的最小值和儿子中的最小值的最小值。

【hdu5967】【xsy1890】小R与手机

题意

对于基环森林，多次操作：

①求某个点的根

②换父亲

分析

我们把几乎所有边存进去，若有一条构成环的边，那么就不存它。

这样对于一次询问，我们找到lct的根r，若a[r]>0，则无解，否则有解。

对于换父亲的操作，我们考虑怎样维护。

维护分成下面几部分实现：①删边 ②基环边 ③连边

注意基环边变成普通边的判定，Find(a[r])==x与a[r]>0的区别。

#include <cstdio>
#include <cctype>

#define rep(i,a,b) for (int i=(a);i<=(b);i++)

const int N=262144;

int n,m,a[N];
int c[N][2]; int fa[N];

int rd(void) {
    int x=0,f=1; char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

int IsRoot(int x) {
    int pre=fa[x];
    return c[pre][0]!=x&&c[pre][1]!=x;
}

void Rotate(int x) {
    int y=fa[x],z=fa[y];
    int l=!(c[y][0]==x),r=l^1;
    if (!IsRoot(y)) {
        if (c[z][0]==y) c[z][0]=x;
        else c[z][1]=x;
    }
    fa[x]=z,fa[y]=x;
    if (c[x][r]>0) fa[c[x][r]]=y;
    c[y][l]=c[x][r];
    c[x][r]=y;
}

void Splay(int x) {
    while (!IsRoot(x)) {
        int y=fa[x],z=fa[y];
        if (!IsRoot(y)) {
            if ((c[y][0]==x)^(c[z][0]==y))
                Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}

void Access(int x) {
    int g=x,t=0;
    while (x>0) {
        Splay(x);
        c[x][1]=t;
        t=x,x=fa[x];
    }
    Splay(g);
}

int Find(int x) {
    Access(x);
    while (c[x][0]>0)
        x=c[x][0];
    Splay(x);
    return x;
}

void Link(int x,int y) {
    Access(y);
    Splay(x);
    fa[x]=y;
}

void Cut(int x,int y) {
    Access(y);
    Splay(x);
    fa[x]=0;
}

int main(void) {
    #ifndef ONLINE_JUDGE
    freopen("sd.in","r",stdin);
    freopen("sd.out","w",stdout);
    #endif

    n=rd(),m=rd();
    rep(i,1,n) {
        a[i]=rd();
        if (a[i]>0&&i!=Find(a[i]))
            Link(i,a[i]);
    }

    rep(i,1,m) {
        int kd=rd(); int x,y; int r;
        switch (kd) {
            case 1:
                x=rd(),y=rd();
                r=Find(x);
                if (x!=r) {
                    Cut(x,a[x]);
                    if (a[r]>0&&Find(a[r])==x)
                        Link(r,a[r]);
                }
                a[x]=y;
                if (a[x]>0&&x!=Find(a[x]))
                    Link(x,a[x]);
                /*
                x=rd(),y=rd(); r=Find(x);
                if(x==r) {
                    a[x]=y;
                    if(a[x] && Find(a[x])!=x)
                        Link(x,y);
                } else {
                    Cut(x,a[x]);
                    if (a[r] && Find(a[r])==x)
                        Link(r,a[r]);
                    a[x]=y;
                    if(a[x] && Find(y)!=x)
                        Link(x,y);
                }
                */
                break;
            case 2:
                x=rd();
                r=Find(x);
                if (a[r]>0)
                    printf("-1\n");
                else printf("%d\n",r);
                break;
        }
    }

    return 0;
}

小结

（1）基环树的维护：通过对点开一个数组维护基环边的信息，其他就像森林一样弄好了。

（2）LCT如果没有主动的换根操作，可以不用换根，就可以不用记rev数组。

【bzoj2759】【xsy1662】一个动态树好题

传送门

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

分析

http://blog.csdn.net/fuxey/article/details/51426808

先用Exgcd把环上的给求出来，然后就可以求环外的了。

注意ax+b的运算没有交换律，但是具有结合律。

证明：反正顺序都不变，随便你怎么交换都一样的。

巴特西

LCT专题练习

【bzoj2049】洞穴勘测

小结

【bzoj1050】旅行

题意

分析

【bzoj3669】【noi2014】魔法森林

题意

分析

分析1

分析2

小结

【bzoj2908】【xsy1663】nand

题意

分析1：树剖

分析2：LCT

小结

【hdu3726】【xsy1173】Chef and Graph Queries

分析

小结

【bzoj3306】【xsy1665】树

题意

分析1：树链剖分

分析2：LCT

小结

【hdu5967】【xsy1890】小R与手机

题意

分析

小结

【bzoj2759】【xsy1662】一个动态树好题

传送门

分析

最新文章

热门文章