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

xtx1092515503 · 2020-07-21 09:02:09 · 题解

~~为什么大家写的都是线段树分治的呀，就没人写可删除线性基的吗，这可是少一个\log呢~~

首先，先介绍一下如何写可删除线性基。

不知道大家有没有用过LCT维护过动态图联通性呢？如果可以离线的话，我们可以在LCT上维护关于删除时间的最大生成树。当新加入一条边后，树上肯定成环，则只需要删掉环上删除时间最早的那条边即可。

~~没听懂没关系，反正这题也不用LCT，举这个例子只是类比一下而已~~

书归正传。如果我们要写可删除线性基的话，借鉴上面的思想，我们肯定希望在线性基中维护删除时间最晚的元素。

我们设d_i表示线性基中第i位的元素，tms_i表示该元素将在何时被删去。

按照贪心的思想，我们肯定希望越高位的线性基越晚删除——不然如果你到了时间，下面的能选而上面不能选，不是会令答案变小吗？

因此我们可以从上到下枚举每一位，能换就换，之后继续向下尝试替换。

这是尝试插入一个删除时间为now，值为x的一个bitset的代码：

void ins(int now,bi x){
//  print(x);
    for(int i=1000;i>=0;i--){
        if(!x[i])continue;
        if(tms[i]<now)swap(tms[i],now),swap(x,d[i]);
        if(!now)break;
        x^=d[i];
    }
}

有了插入代码，自然会有查询代码，查询now时刻的答案：

void ask(int now){
    bi res;
    for(int i=1000;i>=0;i--)if(tms[i]>now&&!res[i])res^=d[i];
    print(res);
}

这两者的复杂度都是O(\dfrac{len^2}{w})的，其中len是01串长度，而w是bitset常数。

那么这可删除线性基在本题中有什么应用呢？

不知道大家有没有做过[WC2011]最大XOR和路径啊，如果做过，就应该能看出来，任意一条从首都出发再回到首都的路径，\operatorname{xor}值能做出贡献的，只有环上的边，路径上的边因为来时异或一次走时再来一次，所以异或值就被消掉了。

因此我们仍然可以借鉴那题的思想，将所有的环搜出来扔进线性基中，找到线性基中的最大值即可。只需要保证每条边都会被包括在某个环中即可——线性基中进行的是异或过程，自然会保留出最优的一组解，不需要的边自然会被异或两次然后抵消掉。

我们可以设dis_x为x节点到一号节点的任意一条路径的异或值。则当我们插入一条边x,y,z时，只需要往线性基中加入dis_x\operatorname{xor}dis_y\operatorname{xor}z即可。

当然，这个操作是要离线下来的——不然你怎么知道新加入的边会在啥时候被删掉呢？

至于修改——你把它变成一次删除，一次加边即可。

当然，这里还可以给出一种在线做法（只不过多一个\log）：

对于插入线性基失败的某个数，记录它在插入过程中由哪些数异或起来得到了0。令一个集合\mathbb{S}表示这些数。

对于插入线性基成功的某个数，记录它在后来者的插入过程中，异或了哪些数。

当你插入一个数x时，维护上述集合。

当你删除一个数x时：

如果它不在线性基中，直接删除。
如果它在线性基中，且存在一个\mathbb{S}使得x\in\mathbb{S}，则删去x并用\mathbb{S}对应的那个数替代x即可——因为\mathbb{S}中所有数异或起来为0，故\mathbb{S}中任何数都可以替代x。在本次替代后，记得将x在其他集合中的所有出现，全都替换成替代的这个数。
如果它在线性基中，且不存在一个\mathbb{S}使得x\in\mathbb{S}，则找到\mathbb{T}_x，并用x异或\mathbb{T}_x中所有数，即可消去x的影响。

~~但是，因为在线做法太恶心了，笔者还是选择了离线做法~~

丑的要命的代码：

#include<bits/stdc++.h>
using namespace std;
typedef bitset<1010> bi;
int n,m,q,tms[1010],ed[1010],cnt,tot,head[1010],op[1010],qwq,bkw[1010];
pair<int,int>nw[1010];
bi d[1010],dis[510],aft[1010];
struct node{
    int to,next;
    bi val;
}edge[1010];
string s;
bi read(){
    cin>>s;
    bi w(s);
    return w;
}
void ae(int u,int v){
    bi w=read();
    edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
    edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
void print(bi &x){
    bool stt=false;
    for(int i=999;i>=0;i--){
        if(x[i]||stt)putchar('0'+x[i]);
        if(x[i])stt=true;
    }
    if(!stt)putchar('0');
    putchar('\n');
}
void ins(int now,bi x){
//  print(x);
    for(int i=1000;i>=0;i--){
        if(!x[i])continue;
        if(tms[i]<now)swap(tms[i],now),swap(x,d[i]);
        if(!now)break;
        x^=d[i];
    }
}
bool vis[510];
void dfs(int x){
    for(int i=head[x];i!=-1;i=edge[i].next){
        if(vis[edge[i].to])ins(0x3f3f3f3f,dis[x]^dis[edge[i].to]^edge[i].val);
        else vis[edge[i].to]=true,dis[edge[i].to]=dis[x]^edge[i].val,dfs(edge[i].to);
    }
}
void ask(int now){
    bi res;
    for(int i=1000;i>=0;i--)if(tms[i]>now&&!res[i])res^=d[i];
    print(res);
}
int main(){
    cin>>n>>m>>q,memset(head,-1,sizeof(head)),qwq=q+1;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,ae(x,y);
    dfs(1);
    ask(0);
    for(int i=1,x,y;i<=q;i++){
        cin>>s;
        if(s[1]=='d')cin>>x>>y,op[i]=++tot,aft[tot]=(read()^dis[x]^dis[y]),nw[tot]=make_pair(x,y),bkw[tot]=tot;
        else if(s[1]=='h')cin>>x,ed[bkw[x]]=i,op[i]=--qwq,aft[qwq]=(dis[nw[x].first]^dis[nw[x].second]^read()),bkw[x]=qwq;
        else if(s[1]=='a')cin>>x,ed[bkw[x]]=i;
    }
    for(int i=1;i<=q;i++)if(!ed[i])ed[i]=0x3f3f3f3f;
    for(int i=1;i<=q;i++){
        if(op[i])ins(ed[op[i]],aft[op[i]]);
        ask(i);
    }
    return 0;
}