题解 P3733 【[HAOI2017]八纵八横】
teafrogsf
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)$是环的个数。
```cpp
// 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;
}
```