[HAOI 2017]八纵八横

落日映苍穹つ 2021-12-22 01:53 256阅读 0赞

线段树分治+线形基。

线段树分治是个锤子？？

以时间轴构建线段树，把每个环以“对线段树产生影响的时间区间”的形式加入线段树即可。

#include<bits/stdc++.h>
    #define ll bitset<1005>
    using namespace std;
    const int N=1005;
    struct base{
        ll p[N];
        void insert(ll x){
            for (int i=N-1;i>=0;i--)
                if (x[i])
                    if (p[i].any()) x^=p[i];
                    else {p[i]=x;return;}
        }
    } tmp;
    struct edge{
        int u,v,l,r;ll dist;
    } loop[N<<1];
    int head[N],vet[N],nxt[N],fa[N],pos[N];
    int n,m,q,x,y,tot,cnt,len,now;
    ll dist[N],d[N],z,res;
    char ch[N],opt[20];
    vector <int> E[N<<2];
    int getint(){
        int x=0,w=1;
        char ch=getchar();
        while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
        if (ch=='-') w=0,ch=getchar();
        while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return w?x:-x;
    }
    ll getll(){
        scanf("%s",ch);int len=strlen(ch);ll x;
        for (int i=0;i<len;++i) x[len-i-1]=ch[i]-'0';return x;
    }
    void add(int x,int y,ll z){
        nxt[++tot]=head[x];
        vet[tot]=y;
        head[x]=tot;
        dist[tot]=z;
    }
    int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
    void dfs(int u,int father){
        for (int i=head[u];i;i=nxt[i]){
            int v=vet[i];
            if (v!=father) d[v]=d[u]^dist[i],dfs(v,u);
        }
    }
    void modify(int u,int l,int r,int ql,int qr,int i){
        if (ql<=l&&r<=qr){
            E[u].push_back(i);
            return;
        }
        int mid=l+r>>1;
        if (ql<=mid) modify(u<<1,l,mid,ql,qr,i);
        if (qr>mid) modify(u<<1|1,mid+1,r,ql,qr,i);
    }
    void query(int u,int l,int r,base b){
        for (int i=0;i<E[u].size();i++){
            int j=E[u][i];
            b.insert(d[loop[j].u]^d[loop[j].v]^loop[j].dist);
        }
        if (l==r){
            ll res=0;int j=N-1;
            for (int i=N-1;i>=0;i--)
                if (!res[i]) res^=b.p[i];
            while (j>=0&&!res[j]) j--;
            while (j>=0)
                if (res[j]) putchar('1'),j--; else putchar('0'),j--;
            puts("");
            return;
        }
        int mid=l+r>>1;
        query(u<<1,l,mid,b);
        query(u<<1|1,mid+1,r,b);
    }
    int main(){
        scanf("%d%d%d",&n,&m,&q);
        for (int i=1;i<=n;i++) fa[i]=i;
        for (int i=1;i<=m;i++){
            x=getint(),y=getint(),z=getll();
            if (find(x)^find(y)){
                add(x,y,z),add(y,x,z);
                fa[find(x)]=find(y);
            }
            else loop[++cnt]=(edge){x,y,0,q,z};
        }
        dfs(1,0);
        for (int i=1;i<=q;i++){
            scanf("%s",opt);
            if (opt[0]=='A'){
                x=getint(),y=getint(),z=getll();
                loop[++cnt]=(edge){x,y,i,q,z};
                pos[++now]=cnt;
            } else
            if (opt[1]=='h'){
                x=getint(),z=getll();
                loop[++cnt]=(edge){loop[pos[x]].u,loop[pos[x]].v,i,q,z};
                loop[pos[x]].r=i-1;
                pos[x]=cnt;
            }
            else{
                x=getint();
                loop[pos[x]].r=i-1;
                pos[x]=-1;
            }
        }
        for (int i=1;i<=cnt;i++)
            modify(1,0,q,loop[i].l,loop[i].r,i);
        query(1,0,q,tmp);
        return 0;
    }

转载于:https://www.cnblogs.com/WR-Eternity/p/10752572.html