题解 P3733 【[HAOI2017]八纵八横】
teafrogsf
2018-09-26 19:06:03
```
线段树分治傻题。
——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)$是环的个数。
```cpp
#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$~~