Tunnel Warfare
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 9329 Accepted Submission(s): 3639
Problem Description During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast areas of north China Plain. Generally speaking, villages connected by tunnels lay in a line. Except the two at the ends, every village was directly connected with two neighboring ones.
Frequently the invaders launched attack on some of the villages and destroyed the parts of tunnels in them. The Eighth Route Army commanders requested the latest connection state of the tunnels and villages. If some villages are severely isolated, restoration of connection must be done immediately!
Input The first line of the input contains two positive integers n and m (n, m ≤ 50,000) indicating the number of villages and events. Each of the next m lines describes an event.
There are three different events described in different format shown below:
D x: The x-th village was destroyed.
Q x: The Army commands requested the number of villages that x-th village was directly or indirectly connected with including itself.
R: The village destroyed last was rebuilt.
Output Output the answer to each of the Army commanders’ request in order on a separate line.
Sample Input
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4
Sample Output
1
0
2
4
題意：一些村莊在一條直線上，每個村莊都與相鄰的兩個村莊相連。現在有三種操作：1.破壞某個村莊。2.修複最近破壞的一個村莊。3.詢問某個村莊與它直接或間接相連的村莊的數量。
思路：這個題解法有兩種，線段樹或者暴力分塊。目的都是找出詢問村莊的左邊界和右邊界，然後直接計算出結果。
分塊代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAX 50005
using namespace std;
struct Node{
int left,right;
}node[MAX];
int Stack[MAX],top;
int n,m;
int area,prot;
void Distory(int pos) //在破壞時，對區域進行更新（down和up之間）。
{
int down = pos/area*area;
int up = min(n,(pos/area + 1)*area - 1);
node[pos].left = node[pos].right = pos;
for(int j = pos - 1; j >= down && node[j].left != node[j].right; j--)
node[j].right = pos;
for(int j = pos + 1; j <= up && node[j].left != node[j].right; j++)
node[j].left = pos;
return ;
}
void Rebuild(int pos) //在修複是，對區域進行更新
{
int down = pos/area*area;
int up = min(n,(pos/area + 1)*area - 1);
int left = pos == down ? down - 1 : node[pos - 1].left,
right= pos == up ? up + 1 : node[pos + 1].right;
node[pos].left = left,node[pos].right = right;
for(int j = pos - 1; j >= down && node[j].left != node[j].right; j--)
node[j].right = right;
for(int j = pos + 1; j <= up && node[j].left != node[j].right; j++)
node[j].left = left;
return ;
}
int find_left(int pos) //找到左邊界
{
return (node[pos].left == pos || node[pos].left == -1) ? node[pos].left : find_left(node[pos].left);
}
int find_right(int pos) //找到右邊界
{
return (node[pos].right == pos || node[pos].right == n) ? node[pos].right : find_right(node[pos].right);
}
void PUT()
{
for(int j = 0; j < n; j++)
cout << node[j].left << "|" << node[j].right << endl;
}
int main( )
{
while(scanf("%d%d",&n,&m) != EOF){
top = 0;
area = sqrt(n);
if(n%area > 0) area++;
for(int j = 0; j < area; j++) //先做分塊預處理，之後的所有處理都在對應塊中進行
for(int k = 0; k < area; k++)
node[area*j + k].left = area*j - 1,node[area*j + k].right = min(area*(j + 1),n);
while(m--){
getchar();
char c = getchar();
int poit;
if(c == 'D'){
scanf("%d",&poit);
poit--;
Distory(poit);
Stack[top++] = poit;
}
if(c == 'Q'){
scanf("%d",&poit);
poit--;
int ans = find_right(poit) - find_left(poit) - 1;
printf("%d\n",ans == -1 ? 0 : ans);
}
if(c == 'R'){
poit = Stack[--top];
Rebuild(poit);
}
}
}
return 0;
}
分塊就是O（n）暴力的優化，優化後的複雜度是O（sqrt(n)）。在此處的複雜度一共是O(m*sqrt(n)).。
線段樹代碼：
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAX 50004
using namespace std;
struct Node{
int left,mid,right;
bool OK;
}Tree[MAX*3];
int Stack[MAX],top;
int node_tree[MAX];
int l,r,n,m;
void BuildTree(int left,int right,int pos) //建樹
{
Tree[pos].left = left,Tree[pos].right = right;
Tree[pos].mid = (left + right) >> 1;
Tree[pos].OK = true;
if(left == right){
node_tree[left] = pos;
return ;
}
BuildTree(left,(right + left)>>1,pos<<1);
BuildTree(((right + left)>>1) + 1,right,(pos<<1) + 1);
return ;
}
void DistoryNode(int pos) //在破壞時更新
{
Tree[pos].OK = false;
if(pos == 1) return ;
DistoryNode(pos>>1);
}
void RebuildNode(int pos) //在修複是更新
{
Tree[pos].OK = true;
if(pos == 1 || !Tree[pos^1].OK) return ;
RebuildNode(pos>>1);
}
void LeftQueryTree(int node,int pos); //尋找區間内最左邊的被破壞的村莊
void RightQueryTree(int node,int pos);//尋找區間内最右邊的被破壞的村莊
int main( )
{
while(cin >> n >> m){
BuildTree(1,n,1);
while(m--){
getchar();
char c = getchar();
int node;
if(c == 'D'){
scanf("%d",&node);
Stack[top++] = node;
DistoryNode(node_tree[node]);
}
if(c == 'Q'){
scanf("%d",&node);
l = 0;
RightQueryTree(node,1);//左邊界在[1,node]區間中最右邊的點
r = n + 1;
LeftQueryTree(node,1); //右邊界在[node,n - 1]區間中最左邊的點
int ans = 0;
if(l == r) ans = 0;
else ans = r - l - 1;
printf("%d\n",ans);
}
if(c == 'R'){
node = Stack[--top];
RebuildNode(node_tree[node]);
}
}
}
return 0;
}
void RightQueryTree(int node,int pos)
{
if(Tree[pos].OK || l != 0){
return ;
}
if(Tree[pos].left == Tree[pos].right){
if(!Tree[pos].OK) l = Tree[pos].left;
return;
}
if(Tree[pos].mid < node){
RightQueryTree(node,pos<<1|1); //優先搜尋右子樹
}
RightQueryTree(node,pos<<1);
return ;
}
void LeftQueryTree(int node,int pos)
{
if(Tree[pos].OK || r != n + 1){
return ;
}
if(Tree[pos].left == Tree[pos].right){
if(!Tree[pos].OK) r = Tree[pos].left;
return ;
}
if(Tree[pos].mid >= node){
LeftQueryTree(node,pos<<1); //優先搜尋左子樹
}
LeftQueryTree(node,pos<<1|1);
return ;
}
線段樹做法每步操作的複雜度O(log(n))，總複雜度是O(m*log(n))。
這個是線段樹模闆題，是以往上的很多題解也都是線段樹。而這個題的資料量完全可以用分塊解決，是以，我就自己把這個題再拉出來鞭屍，在多寫一個分塊題解。
![哈理工oj Touring （最短路 dij算法 鄰接表 + 隊列 ）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)