视频链接:C141 线段树分治+线性基 P3733 [HAOI2017] 八纵八横_哔哩哔哩_bilibili
P3733 [HAOI2017] 八纵八横 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 线段树分治+线性基 O(q*logq*logL*logL) #include <iostream> #include <cstring> #include <algorithm> #include <bitset> #include <vector> using namespace std; #define ls (u<<1) #define rs (u<<1|1) #define mid (l+r>>1) const int N=1005; typedef bitset<N> bit; vector<bit> tr[N<<2]; //节点 bit sum[N],val[N]; int n,m,q,x,y,k; char s[N],z[N]; int vis[N],tim[N],cnt; int head[N],idx; struct edge{ int to,ne; bit w; }e[N<<1]; //原边 struct edge2{ int x,y; }a[N<<1]; //新边 bit p[N]; //初始的线性基 void add(int x,int y,bit w){ e[++idx].to=y; e[idx].ne=head[x]; e[idx].w=w; head[x]=idx; } void print(bit a[]){ int i,j; bit c; for(i=1000;i>=0&&!a[i].any();i--) if(i<0){puts("0");return;} for(j=i;j>=0;j--) if(a[j].any()&&!c[j]) c^=a[j]; for(j=i;j>=0;j--) putchar('0'+c[j]); puts(""); } void insert(bit a[],bit x){ //插入线性基 if(!x.any()) return; for(int i=1000;i>=0;i--){ if(x[i]){ if(!a[i].any()){ a[i]=x; break; } x^=a[i]; } } } void dfs(int x){ vis[x]=1; for(int i=head[x];i;i=e[i].ne){ int y=e[i].to; if(!vis[y]) sum[y]=sum[x]^e[i].w,dfs(y); else insert(p,sum[x]^e[i].w^sum[y]); } } void ins(int u,int l,int r,int L,int R,bit x){ if(l>R||r<L) return; if(L<=l&&r<=R){ tr[u].push_back(x); return; } ins(ls,l,mid,L,R,x); ins(rs,mid+1,r,L,R,x); } void solve(int u,int l,int r,bit a[]){ bit b[N]; for(int i=1000;i>=0;i--) b[i]=a[i]; for(auto i:tr[u]) insert(b,i); //插入基 if(l==r){ print(b); return; } solve(ls,l,mid,b); solve(rs,mid+1,r,b); } int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++){ scanf("%d%d%s",&x,&y,z); bit w(z); add(x,y,w); add(y,x,w); } dfs(1); print(p); for(int i=1;i<=q;i++){ scanf("%s",s); if(s[1]=='d'){ //Add scanf("%d%d%s",&x,&y,z); tim[++cnt]=i; //第k号边的出现时刻 bit w(z); a[cnt]={x,y}; val[cnt]=sum[x]^sum[y]^w; //环值 } else if(s[1]=='h'){ //Change scanf("%d%s",&k,z); ins(1,1,q,tim[k],i-1,val[k]); //插入树 tim[k]=i; //第k号边的出现时刻 bit w(z); val[k]=sum[a[k].x]^sum[a[k].y]^w; //环值 } else{ //Cancel scanf("%d",&k); ins(1,1,q,tim[k],i-1,val[k]); //插入树 tim[k]=q+1; //第k号边消失 } } for(int i=1;i<=cnt;i++) ins(1,1,q,tim[i],q,val[i]); //插入树 if(q) solve(1,1,q,p); //分治 }
// 线段树分治+线性基 O(q*logq*logL*logL) #include <iostream> #include <cstring> #include <algorithm> #include <bitset> #include <vector> using namespace std; #define ls (u<<1) #define rs (u<<1|1) #define mid (l+r>>1) const int N=1005; typedef bitset<N> bit; vector<bit> tr[N<<2]; //节点 bit sum[N],val[N]; int n,m,q,x,y,k; char s[N],z[N]; int vis[N],tim[N],cnt; int head[N],idx; struct edge{ int to,ne; bit w; }e[N<<1]; //原边 struct edge2{ int x,y; }a[N<<1]; //新边 struct bs{ bit b[N]; }p; //初始的线性基 void add(int x,int y,bit w){ e[++idx].to=y; e[idx].w=w; e[idx].ne=head[x]; head[x]=idx; } void print(bs &a){ int i,j; bit c; for(i=1000;i>=0&&!a.b[i].any();i--) if(i<0){puts("0");return;} for(j=i;j>=0;j--) if(a.b[j].any()&&!c[j]) c^=a.b[j]; for(j=i;j>=0;j--) putchar('0'+c[j]); puts(""); } void insert(bs &a,bit x){ //注意bs传地址 if(!x.any()) return; for(int i=1000;i>=0;i--){ if(x[i]){ if(!a.b[i].any()){ a.b[i]=x; break; } x^=a.b[i]; } } } void dfs(int x){ vis[x]=1; for(int i=head[x];i;i=e[i].ne){ int y=e[i].to; if(!vis[y]) sum[y]=sum[x]^e[i].w,dfs(y); else insert(p,sum[x]^e[i].w^sum[y]); } } void ins(int u,int l,int r,int L,int R,bit x){ if(l>R||r<L) return; if(L<=l&&r<=R){ tr[u].push_back(x); return; } ins(ls,l,mid,L,R,x); ins(rs,mid+1,r,L,R,x); } void solve(int u,int l,int r,bs a){ //注意bs传值 for(auto i:tr[u]) insert(a,i); //插入基 if(l==r){ print(a); //输出 return; } solve(ls,l,mid,a); solve(rs,mid+1,r,a); } int main(){ scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++){ scanf("%d%d%s",&x,&y,z); bit w(z); add(x,y,w); add(y,x,w); } dfs(1); print(p); for(int i=1;i<=q;i++){ scanf("%s",s); if(s[1]=='d'){ //Add scanf("%d%d%s",&x,&y,z); tim[++cnt]=i; //第k号边的出现时刻 bit w(z); a[cnt]={x,y}; val[cnt]=sum[x]^sum[y]^w; //环值 } else if(s[1]=='h'){ //Change scanf("%d%s",&k,z); ins(1,1,q,tim[k],i-1,val[k]); //插入树 tim[k]=i; //第k号边的出现时刻 bit w(z); val[k]=sum[a[k].x]^sum[a[k].y]^w; //环值 } else{ //Cancel scanf("%d",&k); ins(1,1,q,tim[k],i-1,val[k]); //插入树 tim[k]=q+1; //第k号边消失 } } for(int i=1;i<=cnt;i++) ins(1,1,q,tim[i],q,val[i]); //插入树 if(q) solve(1,1,q,p); //分治 }
标签:C141,int,八横,sum,P3733,--,bit,include,any From: https://www.cnblogs.com/dx123/p/18248613