【线段树分治线性基】luoguP3733 [HAOI2017]八纵八横

不知道为什么bzoj没有HAOI2017

题目描述

Anihc国有n个城市，这n个城市从1~n编号，1号城市为首都。城市间初始时有m条高速公路，每条高速公路都有一个非负整数的经济影响因子，每条高速公路的两端都是城市（可能两端是同一个城市)，保证任意两个城市都可以通过高速公路互达。

国正在筹划“八纵八横”的高铁建设计划，计划要修建一些高速铁路，每条高速铁路两端也都是城市（可能两端是同一个城市)，也都有一个非负整数的经济影响因子。国家还计划在“八纵八横”计划建成之后，将“一带一路”扩展为“一带_路一环”，增加“内陆城市经济环”即选择一条从首都出发沿若一系列高铁与高速公路走的路径，每条高铁或高速公路可以经过多次，每座城市也可以经过多次，最后路径又在首都结束。令“内陆城市经济环”的GDP为依次将这条路径上所经过的高铁或高速公路的经济影响因子异或起来(一条路经过多次则会被计算多次)。

现在Anihc在会议上讨论“八纵八横”的建设计划方案，他们会不断地修改计划方案，希望你能实时反馈对于当前的“八纵八横”的建设计划的方案“内陆城市经济环”的最大是多少。

初始时，八纵八横1计划中不包含任何—条高铁，有以下3种操作

Add x y z

在计划中给在城市x和城市y之间建设一条高铁，其经济影响因子为z，如果这是第k个Add操作，则将这条高铁命名为k号高铁

Cancel k

将计划中的k号高铁取消掉，保证此时k号高铁一定存在

Change k z

表示将第k号高铁的经济影响因子更改为z，保证此时k号高铁一定存在

输入输出格式

输入格式：

第一行3个整数n,m,P，表示城市个数.高速公路条数.操作个数

接下来m行.每行3个整数表示高速公路的信息。

接下来P行.每行为一个操作

注意：输入的所有经济影响因子都将以二进制的形式从高位到低位给出。

输出格式：

第一行一个整数.表示如果不修建任何高铁，“内陆城市经济环”的GDP最大值

接下Q行.每行一个整数.表示进行了对应的每一个操作之后.对于当前的计划.“内陆城市经济环”的CDP最大值。

注意：输出的答案也要以二进制的形式从高位到低位给出。

说明

【数据规模与约定】

令所有的经济因子二进制表示的最多位数为len.数据满足以下表格

数据点    n的规模    m的规模    Q的规模    len的规模    备注
1    <=5    <=8    0    <=31    
2    <= 100    =n + 1    0    <= 100    
3    <= 100    <= 100    0    <= 100    
4    <= 500    <= 500    0    <= 1000    
5    <= 100    <= 100    <= 100    <= 200    只存在 Add搡作
6    <= 500    <= 500    <= 200    <= 1000    
7    <= 100    <= 100    <= 1000    <= 200    
8    <= 500    <= 500    <= 1000    <= 1000    
9    <= 500    <= 500    <= 1000    <= 1000    
10    <= 500    <= 500    <= 1000    <= 1000

对于所有的数据保证：n,m<=500,Q,len<=1000,1<x,y<n.且Add操作不超过500个.两个城市之间可能有多条高速公路或高铁，高速公路或高铁的两端可能是同一个城市(即有重边.有自环)。

题目大意

初始给定一张无向连通图，每次操作动态加、删、修改一条边，询问操作后经过根的环最大异或价值，允许离线。

题目分析

首先考虑不修改是个怎么一回事。这个无向连通图的套路参考WC2011 XOR：因为整张图始终保持连通，那么先对原图求一颗生成树，再将所有的环都放在线性基里，答案就是全局线性基的最大值。

现在相当于每条边有各自的存在时间，那么这就符合线段树分治的模型：“在时间轴上，每一个时间点的答案基于若干个给定元素”。

这里有个线段树分治的撤销小问题。最初我还在想线性基怎么撤销，后来发现$Qlog Q$次的分治每次开一个线性基，在过程里下传就可以了。

于是将以上两者相结合就可以了。

打挂的两点：

记$tag[x]$为第$x$条插入的边在vector中的位置，$tag[x]$在边change（即再开一条边的时候）和$x$弄混了
vector里$w$记录的是整个环的异或值，因此要记录环上的那一条非树边来处理change操作

  1 #include<bits/stdc++.h>
  2 typedef std::bitset<1003> bit;
  3 const int maxn = 535;
  4 const int maxm = 1035;
  5 const int maxq = 1035;
  6 const int maxOpt = 10035;
  7 
  8 struct Opt
  9 {
 10     int l,r;
 11     bit w,rin;
 12     Opt(int a=0, int b=0, bit c=bit(), bit d=bit()):l(a),r(b),w(c),rin(d) {}
 13 }sv[maxm];
 14 struct Edge
 15 {
 16     int v;
 17     bit w;
 18     Edge(int a=0, bit b=bit()):v(a),w(b) {}
 19 }edges[maxm];
 20 struct LinearBasis
 21 {
 22     bit p[1003];
 23     void insert(bit w)
 24     {
 25         for (int i=1000, chk=0; i>=0&&!chk; i--)
 26             if (w[i]){
 27                 if (p[i].any()) w ^= p[i];
 28                 else p[i] = w, chk = 1;
 29             }
 30     }
 31     void query()
 32     {
 33         bit ans = bit();
 34         int pos = 0;
 35         for (int i=1000; i>=0; i--)
 36         {
 37             if (ans[i]==0) ans ^= p[i];
 38             if (ans[i]&&!pos) pos = i;
 39         }
 40         for (int i=pos; i>=0; i--) putchar(ans[i]?'1':'0');
 41         puts("");
 42     }
 43 };
 44 typedef std::vector<Opt> vec;
 45 int n,m,T,cnt;
 46 int fat[maxn],tag[maxq];
 47 int edgeTot,head[maxn],nxt[maxm];
 48 bit dis[maxn],tmp;
 49 char str[13];
 50 vec opt;
 51 
 52 int read()
 53 {
 54     char ch = getchar();
 55     int num = 0, fl = 1;
 56     for (; !isdigit(ch); ch=getchar())
 57         if (ch=='-') fl = -1;
 58     for (; isdigit(ch); ch=getchar())
 59         num = (num<<1)+(num<<3)+ch-48;
 60     return num*fl;
 61 }
 62 void read(bit &x)
 63 {
 64     char str[1035];
 65     scanf("%s",str+1), x = bit();
 66     for (int i=strlen(str+1), j=0; i>=1; i--)
 67         x[j] = str[i]-'0', ++j;
 68 }
 69 int find(int x){return x==fat[x]?x:fat[x]=find(fat[x]);}
 70 void addedge(int u, int v, bit w)
 71 {
 72     edges[++edgeTot] = Edge(v, w), nxt[edgeTot] = head[u], head[u] = edgeTot;
 73     edges[++edgeTot] = Edge(u, w), nxt[edgeTot] = head[v], head[v] = edgeTot;
 74 }
 75 void dfs(int x, int fa, bit c)
 76 {
 77     dis[x] = c;
 78     for (int i=head[x]; i!=-1; i=nxt[i])
 79     {
 80         int v = edges[i].v;
 81         if (v!=fa) dfs(v, x, c^edges[i].w);
 82     }
 83 }
 84 void solve(int l, int r, vec opt, LinearBasis bas)
 85 {
 86     vec L,R;
 87     int mid = (l+r)>>1;
 88     for (int i=0, mx=opt.size(); i<mx; i++)
 89         if (opt[i].l <= l&&r <= opt[i].r) bas.insert(opt[i].w);
 90         else{
 91             if (opt[i].l <= mid) L.push_back(opt[i]);
 92             if (opt[i].r > mid) R.push_back(opt[i]);
 93         }
 94     if (l==r) bas.query();
 95     else solve(l, mid, L, bas), solve(mid+1, r, R, bas);
 96 }
 97 int main()
 98 {
 99     memset(head, -1, sizeof head);
100     n = read(), m = read(), T = read();
101     for (int i=1; i<=n; i++) fat[i] = i;
102     for (int i=1,u,v; i<=m; i++)
103     {
104         u = read(), v = read(), read(tmp);
105         if (find(u)!=find(v))
106             fat[fat[u]] = fat[v], addedge(u, v, tmp);
107         else sv[++cnt] = Opt(u, v, tmp);
108     }
109     dfs(1, 0, bit());
110     for (int i=1; i<=cnt; i++)
111         opt.push_back(Opt(0, T, sv[i].w^dis[sv[i].l]^dis[sv[i].r]));
112     for (int i=1,cnt=0,u,v; i<=T; i++)
113     {
114         scanf("%s",str);
115         if (str[0]=='A'){
116             u = read(), v = read(), read(tmp);
117             opt.push_back(Opt(i, T, dis[u]^dis[v]^tmp, tmp));
118             tag[++cnt] = opt.size()-1;
119         }else if (str[1]=='h'){
120             u = read(), read(tmp), opt[tag[u]].r = i-1;
121             opt.push_back(Opt(i, T, tmp^opt[tag[u]].rin^opt[tag[u]].w, tmp));
122             tag[u] = opt.size()-1;
123         }else opt[tag[read()]].r = i-1;
124     }
125     solve(0, T, opt, LinearBasis());
126     return 0;
127 }

END