[luogu3733]八纵八横

根据$[WC2011]XOR$的思路，每次暴力重构线性基，令$l'=\frac{l^{2}}{w}$，则有一个$nql'$的做法（这里线性基位数很多，所以要用bitset）

由于初始连通，因此每一个环一定可以由若干个[树边+1条非树边]的环构成（构成指异或），那么预处理出每一个操作的环大小，相当于维护一个支持插入和删除的线性基（修改操作可以看成删除+插入操作）

证明：归纳k条新边（$k=1$显然成立）可以划分，对$k+1$条新边的环，设新边依次为$(l1,r1),(l2,r2),……,(l_{k+1},r_{k+1})$，前k条边所构成的环被划分，多出的部分为树边上的$(l_{1},r_{k}),(l_{1},r_{k+1}),({r_{k},l_{k+1})}$和新边$(l_{k+1},r_{k+1})$，容易发现这个恰好构成了[树边+$(l_{k+1},r_{k+1})$]的环

但线性基无法支持删除，因此用线段树分治：将操作打在区间上，在当前点到根的链上的每一个点维护一个线性基，时间复杂度$o((n\log_{2}n+l')q\log_{2}q)$（要注意$q=0$的情况，特判$l>r$）

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 1005

  4 #define bt bitset<N>

  5 #define L (k<<1)

  6 #define R (L+1)

  7 #define mid (l+r>>1)

  8 struct ji{

  9     int nex,to;

 10     bt len;

 11 }edge[N];

 12 int V,E,n,m,t,q,x,y,head[N],vis[N],tim[N];

 13 char s[N];

 14 bt o,sh[N],f[31][N];

 15 pair<bt,bt>val[N];

 16 vector<bt>v[N<<2];

 17 void read(){

 18     scanf("%s",s);

 19     o.reset();

 20     int l=strlen(s);

 21     for(int i=0;i<l;i++)o[l-i-1]=s[i]-'0';

 22 }

 23 void write(bt o){

 24     bool flag=0;

 25     for(int i=N-6;i>=0;i--)

 26         if ((flag)||(o[i])){

 27             x=o[i];

 28             printf("%d",x);

 29             flag=1;

 30         }

 31     if (!flag)printf("0");

 32     printf("\n");

 33 }

 34 void add(bt x){

 35     for(int i=N-6;i>=0;i--)

 36         if (x[i])

 37             if (f[V][i].any())x^=f[V][i];

 38             else{

 39                 f[V][i]=x;

 40                 break;

 41             }

 42 }

 43 bt query(){

 44     o.reset();

 45     for(int i=N-6;i>=0;i--)

 46         if (!o[i])o^=f[V][i];

 47     return o;

 48 }

 49 void add(int x,int y,bt z){

 50     edge[E].nex=head[x];

 51     edge[E].to=y;

 52     edge[E].len=z;

 53     head[x]=E++;

 54 }

 55 void dfs(int k,bt x){

 56     vis[k]=1;

 57     sh[k]=x;

 58     for(int i=head[k];i!=-1;i=edge[i].nex)

 59         if (!vis[edge[i].to])dfs(edge[i].to,x^edge[i].len);

 60         else add(sh[edge[i].to]^sh[k]^edge[i].len);

 61 }

 62 void New(){

 63     V++;

 64     for(int i=0;i<N-5;i++)f[V][i]=f[V-1][i];

 65 }

 66 void update(int k,int l,int r,int x,int y,bt z){

 67     if ((l>y)||(x>r))return;

 68     if ((x<=l)&&(r<=y)){

 69         v[k].push_back(z);

 70         return;

 71     }

 72     update(L,l,mid,x,y,z);

 73     update(R,mid+1,r,x,y,z);

 74 }

 75 void dfs(int k,int l,int r){

 76     if (l>r)return;

 77     New();

 78     for(int i=0;i<v[k].size();i++)add(v[k][i]);

 79     if (l==r)write(query());

 80     else{

 81         dfs(L,l,mid);

 82         dfs(R,mid+1,r);

 83     }

 84     V--;

 85 }

 86 int main(){

 87     scanf("%d%d%d",&n,&m,&q);

 88     memset(head,-1,sizeof(head));

 89     for(int i=1;i<=m;i++){

 90         scanf("%d%d",&x,&y);

 91         read();

 92         add(x,y,o);

 93         add(y,x,o);

 94     }

 95     o.reset();

 96     dfs(1,o);

 97     for(int i=1;i<=q;i++){

 98         scanf("%s",s);

 99         if (s[0]=='A'){

100             scanf("%d%d",&x,&y);

101             read();

102             tim[++t]=i;

103             val[t]=make_pair(sh[x]^sh[y],o);

104         }

105         else{

106             scanf("%d",&x);

107             update(1,1,q,tim[x],i-1,val[x].first^val[x].second);

108             if (s[1]=='a')tim[x]=-1;

109             else{

110                 read();

111                 tim[x]=i;

112                 val[x].second=o;

113             }

114         }

115     }

116     for(int i=1;i<=t;i++)

117         if (tim[i]>0)update(1,1,q,tim[i],q,val[i].first^val[i].second);

118     write(query());

119     dfs(1,1,q);

120 }

巴特西

[luogu3733]八纵八横

最新文章

热门文章