POJ 2892地道戦Tunnel Warfare(線段樹)
クリックしてタイトルリンクを開いて連続する村に対して3種類の操作と質問を行います 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.
連続区間を更新し、現在の問合せ区間内のノード状態が同じであれば現在の区間連続値を返します.そうでなければ、現在の問合せ点番号と左右の区間の関係に基づいて再帰的に問合せを返します.
連続区間を更新し、現在の問合せ区間内のノード状態が同じであれば現在の区間連続値を返します.そうでなければ、現在の問合せ点番号と左右の区間の関係に基づいて再帰的に問合せを返します.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main{
class SegTree {
class node {
int left, right;
int sum, lsum, rsum;
int mid() {
return (left + right) >>1;
}
int dis() {
return (right - left + 1);
}
void init(int t) {
sum = lsum = rsum = t *dis();
}
}
node tree[];
SegTree(int maxn) {
tree = new node[maxn * 5];
}
void init(int left, int right, int idx) {
tree[idx] = new node();
tree[idx].left=left;
tree[idx].right=right;
tree[idx].init(1);
if (left == right)
return;
int mid = tree[idx].mid();
init(left, mid, idx << 1);
init(mid + 1, right, (idx << 1)|1);
}
void update(int id, int v, int idx) {
if (tree[idx].left == tree[idx].right) {
tree[idx].init(v);
return;
}
int mid = tree[idx].mid();
if (id <= mid)
update(id, v, idx << 1);
else
update(id, v, (idx << 1) + 1);
pushup(idx);
}
int query(int id, int idx) {
if (tree[idx].sum == 0|| tree[idx].sum == tree[idx].dis())
return tree[idx].sum;
int mid = tree[idx].mid();
if (id <= mid) {
if (id > mid - tree[idx << 1].rsum)
return query(id, idx << 1) + query(mid + 1, (idx << 1) + 1);
else
return query(id, idx << 1);
} else {
if (id < mid + 1 + tree[(idx << 1)|1].lsum)
return query(id, (idx << 1)|1) + query(mid, idx << 1);
else
return query(id, (idx << 1)|1);
}
}
void pushup(int idx){
int l = idx << 1;
int r = (idx << 1)|1;
tree[idx].sum = Math.max(tree[l].rsum + tree[r].lsum,
Math.max(tree[r].sum, tree[l].sum));
tree[idx].lsum = tree[l].lsum;
tree[idx].rsum = tree[r].rsum;
if (tree[l].sum == tree[l].dis())
tree[idx].lsum += tree[r].lsum;
if (tree[r].sum == tree[r].dis())
tree[idx].rsum += tree[l].rsum;
}
}
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
final int next() throws IOException {
in.nextToken();
return (int) in.nval;
}
void run() throws IOException {
int n=next();
int m=next();
SegTree st=new SegTree(n);
st.init(1,n, 1);
int stack[]=new int[m];
boolean des[]=new boolean[n+1];
int top=0,k;
while(m-->0){
in.nextToken();
String s=in.sval;
if(s.charAt(0)=='D'){
k=next();
stack[++top]=k;
des[k]=true;
st.update(k,0,1);
}
if(s.charAt(0)=='Q'){
k=next();
if(des[k])
System.out.println(0);
else
System.out.println(st.query(k,1));
}
if(s.charAt(0)=='R'){
k=stack[top--];
des[k]=false;
st.update(k, 1, 1);
}
}
}
public static void main(String[] args) throws IOException {
new Main().run();
}
}