H - Tunnel Warfare HDU - 1540

題意：

n個數順序排列，左右數相連，
現在有三個操作：
1.摧毀一個位置上的數
2.回復上一次摧毀的數
3.查詢包含該位置的最長連續區間長度

題解：

有兩個方法，第一個是區間的最大值-最小值-1，這個就不講了
第二個方法是區間合并更新答案
參考文章
利用線段樹 求出每個線段左端點長度lsum（自左端點向右的連續長度），右端點長度rsum（自右端點向左連續長度） 以及區間內最長連續長度sum（以為可能存在一個連續長度既不包含左端點也不包含右端點）
破壞和修復的區別其實就是lsum，rsum，sum的值
我們用一個函數來求，1表示存在，0表示被破壞
詳細講講過程：
如果區間合并更新答案？
我們已經定義了lsum，rsum，和sum
我們更新lsum，rsum，然后用來更新sum
如果左子樹滿了，root的lsum的長度就等于左子樹（root<<1）的長度加上右子樹(root<<1|1)的lsum

右子樹同理
最長區間是三部分取最大值
1.左子樹從左端點開始的最長連續區間
2.右子樹從右端點開始的最長連續區間
（上面這倆就是剛才講的更新）
3.左子樹的右端點向左+右子樹的左端點向右 （如圖）

更新時就將lsum,rsum,sum更新為所指坐標，如果是摧毀就賦值為0
查詢就是找點在哪個區間，輸出答案就行

代碼：

#include <iostream> #include <bits/stdc++.h> using namespace std;const int maxn = 50005;struct node {int L, R, lsum, rsum, sum;//左端點長度lsum（自左端點向右的連續長度）//區間內最長連續長度int Mid() {return (L+R)/2;}int Len() {return (R-L+1);} }a[maxn*4]; void pushup(int p) {a[p].lsum = a[p << 1].lsum;a[p].rsum = a[p << 1|1].rsum;if (a[p << 1].lsum == a[p << 1].Len())//左子樹滿 a[p].lsum = a[p << 1].Len()+a[p << 1|1].lsum;if (a[p << 1|1].rsum == a[p << 1|1].Len())//右子樹滿 a[p].rsum =a[p << 1|1].Len()+a[p << 1].rsum;/*然后是三部分取最大值1.左子樹從左端點開始的最長連續區間2.右子樹從右端點開始的最長連續區間3.左子樹的右端點向左+右子樹的左端點向右 */int len=a[p<<1].rsum+a[p<<1|1].lsum;a[p].sum = max(a[p].lsum, max(a[p].rsum, len)); }void Build(int p, int l, int r) {a[p].L = l;a[p].R = r;a[p].lsum = a[p].rsum = a[p].sum = a[p].Len();if (l == r) return;Build(p << 1, l, a[p].Mid());Build(p << 1|1, a[p].Mid()+1, r); }void Insert(int p, int k, int x) {if (a[p].L == a[p].R) {a[p].lsum = a[p].rsum = a[p].sum = x;return;}if (k <= a[p].Mid())Insert(p << 1, k, x);elseInsert(p << 1|1, k, x);pushup(p); }int Query(int p, int k) {if (a[p].sum == 0) return 0;//先查看k是否被左右倆個區間包括在內 if (k < a[p].L+a[p].lsum) return a[p].lsum;if (k > a[p].R-a[p].rsum) return a[p].rsum;//然后查看左子樹有部分+右子樹左部分 if (k > a[p << 1].R-a[p << 1].rsum&&k < a[p << 1|1].L+a[p << 1|1].lsum)return a[p << 1].rsum+a[p << 1|1].lsum;if (k <= a[p].Mid())return Query(p << 1, k);elsereturn Query(p << 1|1, k); } int main() {int n, m;while (~scanf("%d%d", &n, &m)) {int x;char s[10];stack <int> sta;Build(1, 1, n);while (m--) {scanf("%s", s);if (s[0] == 'D') {scanf("%d", &x);Insert(1, x, 0);sta.push(x);} else if (s[0] == 'R'&&sta.size()) {Insert(1, sta.top(), 1);sta.pop();} else if (s[0] == 'Q') {scanf("%d", &x);printf("%d\n", Query(1, x));}}}return 0; }

總結

以上是生活随笔為你收集整理的H - Tunnel Warfare HDU - 1540的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。