BZOJ3514：Codechef MARCH14 GERALD07加强版 （LCT+可持久化线段树）

时间：2022-09-22 09:43:28

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3514

题目分析：又是一道动态树好题。拿到题面两天之后我都没想出来，结果期末考地理的时候，我做完题无聊在草稿纸上画了画，居然立马知道怎么做了……
因为我是搜LCT练习题的时候见到这题的，所以我知道肯定要用LCT，但LCT之后要怎么做我就不知道了。我发现这题和NOI2014魔法森林很像，都是先给出了一个图。那么我可不可以像那题一样，维护一个原图的生成树或生成森林呢？既然是这样，如果按编号从小到大加边，出现环的时候我必须要舍弃环上的一条边。直觉告诉我应该要舍弃环上编号最小的边，于是我画了个图，看一下加进这条新边，舍弃原环上编号最小的边，对答案会有什么影响：
BZOJ3514：Codechef MARCH14 GERALD07加强版 （LCT+可持久化线段树）
如果我们固定R=5，那么当L=1,2,3,4,5时，联通块的个数分别为2,3,4,5,6。那么当R右移一位=6时，我们发现如果L=4,5,6，联通块的个数在原先的基础上-1。这是因为原先L=4,5,6时6号边所连接的5,7号点不属于同一个联通块，而我现在加入6号边之后，它们就在一个联通块里了。而对于L=1,2,3而言，多连一条编号为6的边没影响，因为5号点和7号点本来就在一个联通块里了。
那么现在要做的事情就很清楚了：我们要找到最大的可以使x,y相连的L，即当前x->y上编号最小的边，假设为last。那么last+1~R这段联通块个数-1，然后踢掉last，将R加进森林。因为要强制在线，我们要写一个带懒惰标记的可持久化线段树。但由于是要改一段查一个，我们可以将[l,r]这段-1变成：在l的位置-1，r+1的位置+1，这样我们查一个数变成查它的前缀和。为了方便我们还可以变成在l处+1，r+1处-1，最后用N-Query到的值。
一开始我写了代码之后RE了，而我手出了好几组数据都没问题。我又检查了一下代码，觉得可能是答案算错了，导致强制在线时解密出错误的信息。然后我找网上大神AC的代码对拍了一下，发现是我为了方便，将a号边对应lct[N+a]，然后我特判x==y的时候直接continue了，漏了句point++，导致有的时候算答案少了1……

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=200010;
const int maxl=25;

struct Tnode
{
int val,L,R,id,path_parent;
bool flip;
    Tnode *fa,*son[2],*Min;
int Get_d() { return fa->son[1]==this; }
void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
void Up()
    {
        Min=this;
if ( son[0] && son[0]->Min->val<val ) Min=son[0]->Min;
if ( son[1] && son[1]->Min->val<Min->val ) Min=son[1]->Min;
    }
void Push_down()
    {
if (flip)
        {
            swap(son[0],son[1]);
if (son[0]) son[0]->flip^=1;
if (son[1]) son[1]->flip^=1;
            flip=false;
        }
    }
} lct[maxn<<1];
int point=0;

struct Seg
{
int sum;
    Seg *lson,*rson;
} tree[(maxn*maxl)<<1];
Seg *Root[maxn];
int cur=-1;

int n,m,k,t,lastans=0;

void New_node(int v,int l,int r)
{
    point++;
    lct[point].val=v;
    lct[point].L=l;
    lct[point].R=r;
    lct[point].id=point;
    lct[point].path_parent=0;
    lct[point].flip=false;
    lct[point].fa=lct[point].son[0]=lct[point].son[1]=NULL;
    lct[point].Min=lct+point;
}

Seg *New_seg()
{
    cur++;
    tree[cur].sum=0;
    tree[cur].lson=tree[cur].rson=tree;
return tree+cur;
}

void Push(Tnode *P)
{
if (!P) return;
    Push(P->fa);
    P->Push_down();
}

void Zig(Tnode *P)
{
int d=P->Get_d();
    Tnode *F=P->fa;
if (P->son[!d]) F->Connect(P->son[!d],d);
else F->son[d]=NULL;
if (F->fa) F->fa->Connect(P, F->Get_d() );
else P->fa=NULL;
    F->Up();
    P->Connect(F,!d);
    P->path_parent=F->path_parent;
    F->path_parent=0;
}

void Splay(Tnode *P)
{
    Push(P);
while (P->fa)
    {
        Tnode *F=P->fa;
if (F->fa) ( F->Get_d()^P->Get_d() )? Zig(P):Zig(F);
        Zig(P);
    }
    P->Up();
}

void Down(int x)
{
    Splay(lct+x);
if (!lct[x].son[1]) return;
    lct[x].son[1]->fa=NULL;
    lct[x].son[1]->path_parent=x;
    lct[x].son[1]=NULL;
    lct[x].Up();
}

void Access(int x)
{
    Down(x);
int y=lct[x].path_parent;
while (y)
    {
        Down(y);
        lct[y].Connect(lct+x,1);
        lct[x].path_parent=0;
        lct[y].Up();
        x=y;
        y=lct[x].path_parent;
    }
}

int Find(Tnode *P)
{
    P->Push_down();
if (P->son[0]) return Find(P->son[0]);
return P->id;
}

int Find_root(int x)
{
    Access(x);
    Splay(lct+x);
return Find(lct+x);
}

void Evert(int x)
{
    Access(x);
    Splay(lct+x);
    lct[x].flip^=1;
}

void Cut(int x,int y)
{
    Evert(x);
    Access(y);
    Splay(lct+x);
    Down(x);
    Splay(lct+y);
    lct[y].path_parent=0;
}

void Link(int x,int y)
{
    Evert(x);
    lct[x].path_parent=y;
}

int Work(int x,int y,int Time)
{
    New_node(Time,x,y);
int temp=1;
if ( Find_root(x)==Find_root(y) )
    {
        Evert(x);
        Access(y);
        Splay(lct+x);

int z=lct[x].Min->id;
        Cut(z,lct[z].L);
        Cut(z,lct[z].R);
        temp=z-n+1;
    }

    Link(point,x);
    Link(point,y);
return temp;
}

void Update(Seg *root,int l,int r,int x,int v)
{
if (l==r)
    {
        root->sum+=v;
return;
    }

int mid=(l+r)>>1;
    Seg *y=New_seg();

if (x<=mid)
    {
        *y=*(root->lson);
        root->lson=y;
        Update(y,l,mid,x,v);
    }
else
    {
        *y=*(root->rson);
        root->rson=y;
        Update(y,mid+1,r,x,v);
    }

    root->sum=root->lson->sum+root->rson->sum;
}

int Query(Seg *root,int l,int r,int x,int y)
{
if ( y<l || r<x ) return 0;
if ( x<=l && r<=y ) return root->sum;

int mid=(l+r)>>1;
int vl=Query(root->lson,l,mid,x,y);
int vr=Query(root->rson,mid+1,r,x,y);

return vl+vr;
}

int main()
{
    freopen("3514.in","r",stdin);
    freopen("3514.out","w",stdout);

scanf("%d%d%d%d",&n,&m,&k,&t);
for (int i=1; i<=n; i++) New_node(maxn,0,0);

    Root[0]=New_seg();
for (int i=1; i<=m; i++)
    {
int x,y;
scanf("%d%d",&x,&y);
if (x==y)
        {
            point++;
            Root[i]=Root[i-1];
continue;
        }
int last=Work(x,y,i);

        Seg *z=New_seg();
        *z=*Root[i-1];
        Update(z,1,m+1,last,1);

        Root[i]=New_seg();
        *Root[i]=*z;
        Update(Root[i],1,m+1,i+1,-1);
    }

for (int i=1; i<=k; i++)
    {
int l,r;
scanf("%d%d",&l,&r);
if (t) l^=lastans,r^=lastans;
        lastans=n-Query(Root[r],1,m+1,1,l);
printf("%d\n",lastans);
    }

return 0;
}
标签：

相关文章