题解 P3733 【[HAOI2017]八纵八横】

2018-09-26 19:25:06


现在你看到的是本篇题解的第三迭代,之前的内容因为不可预知的信息危害导致内容失踪。


线段树分治傻题。
                                            ——zsyzsy

在与 $Faker\_Beng,ShichengXiao$ 的开黑下终于了却了一大心结。同时被zsy吊打
如果你做过 $[WC2011]XOR$ 的话,对这题你应该有一个基本的思路:把所有的环搜出来,然后把它们插到线性基里查询异或最大值。
于是有一个暴力的做法:对每次修改都暴力重新搜环并重构线性基,这样的复杂度应该是 $O(\frac{qmL^2}{\omega})$ ,可以获得 $70$ 分的好成绩。
这样做为什么是对的呢?因为实际上我们的询问就是要求一堆环中的异或最大值,最终选出来的环有没有经过首都都没有关系,因为对于任意一个环,只要我们再走一遍,影响就消掉了。
既然线性基不好撤销,我们考虑线段树分治。因为这样就可以把线性基存到分治结构里,最多只会同时存在 $O(\log)$ 个线性基,所以空间复杂度是没有问题的。
因为一开始的边是不会删除的,所以我们可以用并查集找到一开始的环边,然后搞出一个原图的生成树。那么对于之后的插入,我们可以直接找出一个唯一的环,而环上的权值和也可以方便地求出。
于是我们可以直接求出对于每条环边的存在区间,一开始的环边就是 $[0,q]$ 。
注意对于环边权值的修改,我们也要划分成两个存在区间。
然后我们直接把所有环边插到线段树里,进行线段树分治就可以了。
这题主要的细节就是 $bitset$ 了吧,但是为什么这题东西这么多啊因为数组开多了 $RE$ 好几次
时间复杂度应该是 $O(n\alpha(n)+\frac{(m-n+q+q\log q)L^2}{\omega})$ , $O(m-n+q)$ 是环的个数。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define neko 510
#define meko 1010
#define feko 6010
#define pb push_back
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i)) 
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i)) 
using namespace std;
namespace IO
{
    template<typename T>
        void read(T &x)
        {
            char c=getchar();x=0;
            for(;!isdigit(c);c=getchar());
            for(;isdigit(c);x=(x<<1)+(x<<3)+(c^'0'),c=getchar());
        }
}
typedef bitset<1005> bs;
struct Basis
{
    bs bas[meko];
//  Basis()
//  {f(i,1,1000)bas[i].reset();}
}B;
struct node
{int v,nex;bs w;}e[meko<<1];
struct edge
{int u,v,l,r;bs w;}E[meko<<1];
int n,m,q,TT;
typedef int arr[neko];
arr head,fa;
vector<int>vec[feko];
bs dis[neko];
int pos[meko];
namespace Lin_Bsis
{
    int maxbit=0;
    void print(bs x)
    {
        int flag=0;
        rf(i,maxbit,0)
        {
            if(x[i])flag=1;
            if(flag)putchar(x[i]+'0');
        }if(!flag)putchar('0');
        putchar('\n');
    }
    void insert(Basis &L,bs x)
    {
        rf(i,maxbit,0)
        {
            if(!x[i])continue;
            if(!L.bas[i].any()){L.bas[i]=x;break;}
            else x^=L.bas[i];
        }
    }
    bs query(Basis L)
    {
        bs ans;ans.reset();
        rf(i,maxbit,0)if(!ans[i])ans^=L.bas[i];
        return ans;
    }
}
namespace Seg_DC
{
    #define ori tagl,tagr
    #define lson root<<1,l,mid
    #define rson root<<1|1,mid+1,r
    using namespace Lin_Bsis;
    void update(int root,int l,int r,int tagl,int tagr,int x)
    {
        if(tagl<=l&&r<=tagr)return (void)vec[root].pb(x);
        int mid=(l+r)>>1;
        if(tagl<=mid)update(lson,ori,x);
        if(tagr>mid)update(rson,ori,x);
    }
    void dfs(int root,int l,int r,Basis bas)
    {
        for(auto x:vec[root])insert(bas,dis[E[x].u]^dis[E[x].v]^E[x].w);
        int mid=(l+r)>>1;
        if(l==r)return print(query(bas));
        else dfs(lson,bas),dfs(rson,bas);
    }
}
namespace Graph
{
    int t=0;
    int find(int x){return fa[x]^x?fa[x]=find(fa[x]):x;}
    void add(int x,int y,bs z)
    {
        e[++t].v=y,e[t].w=z;e[t].nex=head[x],head[x]=t;
        e[++t].v=x,e[t].w=z;e[t].nex=head[y],head[y]=t;
    }
    void dfs(int u,int fa)
    {
        for(register int i=head[u],v=e[i].v;i;i=e[i].nex,v=e[i].v)if(v^fa)dis[v]=dis[u]^e[i].w,dfs(v,u);
    }
}
int cmax(int x,int y){return x>y?x:y;}
int main()
{
    using namespace Graph;
    using namespace Seg_DC;
    using namespace IO;
    int x,y,cnt=0;
    string str;
    char s[20];
    read(n),read(m),read(q);
    f(i,1,n)fa[i]=i;
    f(i,1,m)
    {
        read(x),read(y),cin>>str;
        maxbit=cmax(maxbit,str.size());
        if(find(x)^find(y))fa[find(y)]=find(x),add(x,y,bs(str));
        else E[++TT]=(edge){x,y,0,q,bs(str)};
    }
    Graph::dfs(1,0);
    f(i,1,q)
    {
        scanf("%s",s);
        if(s[0]=='A')
        {
            read(x),read(y),cin>>str;
            maxbit=cmax(maxbit,str.size());
            E[++TT]=(edge){x,y,i,q,bs(str)},pos[++cnt]=TT;
        }
        else if(s[1]=='a')read(x),E[pos[x]].r=i-1,pos[x]=0;
        else
        {
            read(x),cin>>str;
            maxbit=cmax(maxbit,str.size());
            E[pos[x]].r=i-1;
            E[++TT]=(edge){E[pos[x]].u,E[pos[x]].v,i,q,bs(str)};
            pos[x]=TT;
        }
    }
    f(i,1,TT)update(1,0,q,E[i].l,E[i].r,i);
    return dfs(1,0,q,B),0;
}