星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

posted on 2018-09-26 19:06:03 | under 题解 |
线段树分治傻题。
                                            ——zsyzsy

在 $Faker\_Beng,ShichengXiao$ 的开黑下总算解决了一个心结。同时被zsy吊打

如果你做过 $[WC2011]XOR$ 的话,那么你对这道题应该有一个大概的思路:把所有的环搜出来,然后塞到线性基里。
然后你可以选择每次修改都直接暴力重新搜环建线性基,这样的复杂度应该是 $O(\frac{qmL^2}{\omega})$ ,可以获得 $70$ 分的好成绩。
为什么这样做是正确的呢?显然我们的询问实际上就是找一堆环的异或最大值,在最后的选择中这堆环有没有经过首都的环都没关系,反正走两遍的话,这个环的影响就被消掉了。
由于一开始的边是不会删除的,所以我们可以对一开始读入的边用并查集找环,然后搞出一棵原图的生成树,这样之后的插入就会构造出一个唯一的环,然后这个环的权值也可以方便地算出。
因为线性基不好撤销,我们考虑进行线段树分治。这样可以直接把线性基存在分治结构里,最多只会同时存在 $O(\log)$ 个,空间复杂度是没有问题的。
我们先记录好每条环边的存在区间,一开始的环边直接就是 $[0,q]$ 。注意每次对环边进行权值修改时,我们也要划分成两个存在区间。
做成这样后直接把这些边插到线段树里,然后直接线段树分治就可以了。
时间复杂度应该是 $O(n\alpha(n)+\frac{(m-n+q+q\log q)L^2}{\omega})$ 。 $O(m-n+q)$ 是环的个数。

#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;
}

比较细节的主要是 $bitset$ 的处理主要是这题目东西怎么这么多因为数组开错 $RE$ 好几次
然后就写完了。
~~为什么 $HA$ 省会把这题和新型城市化放在一天 $\cdots\cdots$ ~~