题目:https://loj.ac/problem/2312

   https://www.luogu.org/problemnew/show/P3733

原本以为要线段树分治+LCT,查了查发现环上的值直接是 dis[ u ] ^ dis[ v ] ^ w[ i ] 就行了(其中 u , v 是边的两端, i 是边的标号)。

再看一下题,发现一开始一定是连通的。所以剩下的就和 bzoj 4184 shallot 一样用线性基就行了。

因为有 1000 位,所以用 bitset 。

线性基求最大值原来不用判断 if( ( ans^b[ i ] ) > ans ) ans ^= b[ i ] ,直接看 ans 的这一位上是不是 0 就行了。

线段树的一个点不要用 vector 存 bitset ,存一下边的编号,然后每条边开 bitset 存一下自己就行了,能省出很多空间。

在线段树上 dfs 求答案的时候不要把一个线性基带在参数上,给每个点用 vector 记录一下它改了线性基的哪些位就行了,这样好像对栈空间更友好。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
#define ls Ls[cr]
#define rs Rs[cr]
#define pb push_back
#define BT bitset<M>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=,M=;
int n,m,hd[N],xnt,to[M],nxt[M],fa[N],dy[/*N*/M],mx;
int tot,Ls[M<<],Rs[M<<];
char ch[M]; bool vis[/*N*/M];
BT dis[N],w[M],b[M],ew[M],tmp;
vector<int> vt[M<<],cg[M<<];
struct Ed{int x,y; BT w;}ed[/*N*/M]; void cz(BT k,int cr)
{
for(int i=mx-;i>=;i--)
{
if(!k[i])continue;
if(!b[i].any()){ b[i]=k;cg[cr].pb(i);break;}
else k^=b[i];
}
}
void print()
{
tmp.reset();
for(int i=mx-;i>=;i--)
if(!tmp[i])tmp^=b[i];
int st=mx-; for(;st>&&!tmp[st];st--);
for(;st>=;st--) putchar(tmp[st]+'');
puts("");
}
void rd1()
{
scanf("%s",ch); int len=strlen(ch);
mx=Mx(mx,len); tmp.reset();//
for(int i=,j=len-;i<len;i++,j--)
tmp[i]=(ch[j]-'');
}
int fnd(int a){return fa[a]==a?a:fa[a]=fnd(fa[a]);}
void add(int x,int y)
{
int u=fnd(x),v=fnd(y);
if(u==v)
{
ed[++tot].x=x; ed[tot].y=y; ed[tot].w=tmp;
}
else
{
fa[u]=v;
to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=tmp;
to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;w[xnt]=tmp;
}
}
void dfs(int cr,int fa)
{
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa)
{
dis[v]=dis[cr]^w[i]; dfs(v,cr);
}
}
void build(int l,int r,int cr)
{
if(l==r)return; int mid=l+r>>;
ls=++tot; build(l,mid,ls);
rs=++tot; build(mid+,r,rs);
}
void ins(int l,int r,int cr,int L,int R,int k)
{
if(l>=L&&r<=R){vt[cr].pb(k);return;}
int mid=l+r>>;
if(L<=mid)ins(l,mid,ls,L,R,k);
if(mid<R)ins(mid+,r,rs,L,R,k);
}
void dfs(int l,int r,int cr)
{
int sz=vt[cr].size();
for(int i=;i<sz;i++)cz(ew[vt[cr][i]],cr);
if(!ls)print();
else dfs(l,l+r>>,ls), dfs((l+r>>)+,r,rs);
sz=cg[cr].size();
for(int i=;i<sz;i++)b[cg[cr][i]].reset();
}
int main()
{
n=rdn();m=rdn();int Q=rdn();
for(int i=;i<=n;i++)fa[i]=i;
for(int i=,u,v;i<=m;i++)
{
u=rdn();v=rdn();rd1();
add(u,v);
}
dfs(,); int t2=tot;
if(Q){ tot=;build(,Q,);}
for(int i=,u;i<=t2;i++)
{
tmp=dis[ed[i].x]^dis[ed[i].y]^ed[i].w;
cz(tmp,);
}
int cnt=; tot=;
for(int i=,x;i<=Q;i++)
{
scanf("%s",ch);
if(ch[]=='A')
{
cnt++; dy[cnt]=i;
ed[cnt].x=rdn();ed[cnt].y=rdn();
rd1(); ed[cnt].w=tmp;
}
else if(ch[]=='a')
{
x=rdn();
ew[++tot]=dis[ed[x].x]^dis[ed[x].y]^ed[x].w;
ins(,Q,,dy[x],i-,tot); vis[x]=;
}
else
{
x=rdn(); rd1();
ew[++tot]=dis[ed[x].x]^dis[ed[x].y]^ed[x].w;
ins(,Q,,dy[x],i-,tot);
dy[x]=i; ed[x].w=tmp;
}
}
for(int i=;i<=cnt;i++)
if(!vis[i])
{
ew[++tot]=dis[ed[i].x]^dis[ed[i].y]^ed[i].w;
ins(,Q,,dy[i],Q,tot);
}
print();
if(Q)dfs(,Q,); return ;
}

最新文章

  1. [转]js 将图片连接转换称base64格式
  2. Android Studio使用org.apache.http报错
  3. Java高级编程之URL处理
  4. crontab 的使用
  5. php中alert弹出时单双引号问题
  6. Linux里设置环境变量的方法(export PATH)
  7. C++箴言:理解 new-handler的行为
  8. KVC和KVO实现监听容器类(数组等)的变化
  9. [HNOI 2016]最小公倍数
  10. java的3大特性
  11. Cisco 4507R+E四引擎VSS故障解决
  12. 定时器中的this和函数封装的简单理解;
  13. Ubuntu16.04+Java8+Mysql5.7+Tomcat8.5服务器环境配置
  14. Linux(Red hat)无网离线安装TensorFlow
  15. 如何运行Struts2官网最新Demo?
  16. python 添加进度条
  17. 软工2017第五周——个人PSP
  18. 51nod 1295 XOR key-区间异或最大值-可持久化01Trie树(模板)
  19. 在nodejs中 Object的toString()方法 querystring的stringify() JSON.stringify()
  20. canvas图片压缩,局部放大,像素处理

热门文章

  1. 手机号的 AES/CBC/PKCS7Padding 加解密
  2. nginx随机模块——ngx_http_random_index_module
  3. VS2010,MFC动态按钮和窗体背景图片,以及是静态文字控件透明,并避免静态文字刷新出现的重叠问题
  4. lvm逻辑卷扩容
  5. Oracle表的查询(一)
  6. Python学习笔记第十六周
  7. Jquery的deferred对象,看这2篇牛人的文章,基本就够了。
  8. 查看Windows端口及端口关闭方法
  9. python2.7.9安装mysql-python模块
  10. TS 基础数据类型