【线段树分治 线性基】luoguP3733 [HAOI2017]八纵八横
不知道為什么bzoj沒有HAOI2017
題目描述
Anihc國(guó)有n個(gè)城市，這n個(gè)城市從1~n編號(hào)，1號(hào)城市為首都。城市間初始時(shí)有m條高速公路，每條高速公路都有一個(gè)非負(fù)整數(shù)的經(jīng)濟(jì)影響因子，每條高速公路的兩端都是城市（可能兩端是同一個(gè)城市)，保證任意兩個(gè)城市都可以通過高速公路互達(dá)。
國(guó)正在籌劃“八縱八橫”的高鐵建設(shè)計(jì)劃，計(jì)劃要修建一些高速鐵路，每條高速鐵路兩端也都是城市（可能兩端是同一個(gè)城市)，也都有一個(gè)非負(fù)整數(shù)的經(jīng)濟(jì)影響因子。國(guó)家還計(jì)劃在“八縱八橫”計(jì)劃建成之后，將“一帶一路”擴(kuò)展為“一帶_路一環(huán)”，增加“內(nèi)陸城市經(jīng)濟(jì)環(huán)”即選擇一條從首都出發(fā)沿若一系列高鐵與高速公路走的路徑，每條高鐵或高速公路可以經(jīng)過多次，每座城市也可以經(jīng)過多次，最后路徑又在首都結(jié)束。令“內(nèi)陸城市經(jīng)濟(jì)環(huán)”的GDP為依次將這條路徑上所經(jīng)過的高鐵或高速公路的經(jīng)濟(jì)影響因子異或起來(lái)(一條路經(jīng)過多次則會(huì)被計(jì)算多次)。
現(xiàn)在Anihc在會(huì)議上討論“八縱八橫”的建設(shè)計(jì)劃方案，他們會(huì)不斷地修改計(jì)劃方案，希望你能實(shí)時(shí)反饋對(duì)于當(dāng)前的“八縱八橫”的建設(shè)計(jì)劃的方案“內(nèi)陸城市經(jīng)濟(jì)環(huán)”的最大是多少。
初始時(shí)，八縱八橫1計(jì)劃中不包含任何—條高鐵，有以下3種操作
- Add x y z
在計(jì)劃中給在城市x和城市y之間建設(shè)一條高鐵，其經(jīng)濟(jì)影響因子為z，如果這是第k個(gè)Add操作，則將這條高鐵命名為k號(hào)高鐵
- Cancel k
將計(jì)劃中的k號(hào)高鐵取消掉，保證此時(shí)k號(hào)高鐵一定存在
- Change k z
表示將第k號(hào)高鐵的經(jīng)濟(jì)影響因子更改為z，保證此時(shí)k號(hào)高鐵一定存在
輸入輸出格式
輸入格式：
第一行3個(gè)整數(shù)n,m,P，表示城市個(gè)數(shù).高速公路條數(shù).操作個(gè)數(shù)
接下來(lái)m行.每行3個(gè)整數(shù)表示高速公路的信息。
接下來(lái)P行.每行為一個(gè)操作
注意：輸入的所有經(jīng)濟(jì)影響因子都將以二進(jìn)制的形式從高位到低位給出。
?
輸出格式：
第一行一個(gè)整數(shù).表示如果不修建任何高鐵，“內(nèi)陸城市經(jīng)濟(jì)環(huán)”的GDP最大值
接下Q行.每行一個(gè)整數(shù).表示進(jìn)行了對(duì)應(yīng)的每一個(gè)操作之后.對(duì)于當(dāng)前的計(jì)劃.“內(nèi) 陸城市經(jīng)濟(jì)環(huán)”的CDP最大值。
注意：輸出的答案也要以二進(jìn)制的形式從高位到低位給出。
說(shuō)明
【數(shù)據(jù)規(guī)模與約定】
令所有的經(jīng)濟(jì)因子二進(jìn)制表示的最多位數(shù)為len.數(shù)據(jù)滿足以下表格
數(shù)據(jù)點(diǎn) n的規(guī)模 m的規(guī)模 Q的規(guī)模 len的規(guī)模 備注
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 對(duì)于所有的數(shù)據(jù)保證：n,m<=500,Q,len<=1000,1<x,y<n.且Add操作不超過500個(gè).兩個(gè)城市之間可能有多條高速公路或高鐵，高速公路或高鐵的兩端可能是同一個(gè)城市(即 有重邊.有自環(huán))。
題目大意
初始給定一張無(wú)向連通圖，每次操作動(dòng)態(tài)加、刪、修改一條邊，詢問操作后經(jīng)過根的環(huán)最大異或價(jià)值，允許離線。
題目分析
首先考慮不修改是個(gè)怎么一回事。這個(gè)無(wú)向連通圖的套路參考WC2011 XOR：因?yàn)檎麖垐D始終保持連通，那么先對(duì)原圖求一顆生成樹，再將所有的環(huán)都放在線性基里，答案就是全局線性基的最大值。
現(xiàn)在相當(dāng)于每條邊有各自的存在時(shí)間，那么這就符合線段樹分治的模型：“在時(shí)間軸上，每一個(gè)時(shí)間點(diǎn)的答案基于若干個(gè)給定元素”。
這里有個(gè)線段樹分治的撤銷小問題。最初我還在想線性基怎么撤銷，后來(lái)發(fā)現(xiàn)$Q\log Q$次的分治每次開一個(gè)線性基，在過程里下傳就可以了。
于是將以上兩者相結(jié)合就可以了。
打掛的兩點(diǎn)：
- 記$tag[x]$為第$x$條插入的邊在vector中的位置，$tag[x]$在邊change（即再開一條邊的時(shí)候）和$x$弄混了
- vector里$w$記錄的是整個(gè)環(huán)的異或值，因此要記錄環(huán)上的那一條非樹邊來(lái)處理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
轉(zhuǎn)載于:https://www.cnblogs.com/antiquality/p/10263632.html
總結(jié)
以上是生活随笔為你收集整理的【线段树分治 线性基】luoguP3733 [HAOI2017]八纵八横的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
