HDu 1540 Tunnel Warfareセグメントツリー
6300 ワード
//Q pos pos
//D pos pos
//R
//
// ,
#include
#include
#include
#include
using namespace std ;
const int maxn = 500010 ;
#define left v<<1
#define right v<<1|1
struct node
{
int l , r ;
int ma_l , ma_r;
}tree[maxn<<2] ;
int stack[maxn] ;
void build(int l , int r , int v)
{
tree[v].l = l ;
tree[v].r = r;
tree[v].ma_l = tree[v].ma_r = r - l + 1 ;
if(l == r)return ;
int mid = (l + r) >> 1 ;
build(l , mid , left) ;
build(mid + 1 , r , right) ;
}
void push_up(int v)
{
tree[v].ma_l = tree[left].ma_l ;
tree[v].ma_r = tree[right].ma_r ;
if(tree[v].ma_l == tree[left].r - tree[left].l + 1)
tree[v].ma_l += tree[right].ma_l ;
if(tree[v].ma_r == tree[right].r - tree[right].l + 1)
tree[v].ma_r += tree[left].ma_r ;
}
int query(int v , int num)
{
if(tree[v].l == tree[v].r)
return tree[v].ma_l ;
int mid = (tree[v].l + tree[v].r) >> 1 ;
if(num <= mid)
{
if(tree[left].r - tree[left].ma_r + 1 <= num)
return tree[left].ma_r + tree[right].ma_l;
else return query(left , num) ;
}
else
{
if(tree[right].l + tree[right].ma_l - 1 >= num)
return tree[left].ma_r + tree[right].ma_l;
else return query(right ,num) ;
}
}
void update(int pos , int op , int v)
{
if(tree[v].l == tree[v].r)
{
tree[v].ma_l = tree[v].ma_r = op ;
return ;
}
int mid = (tree[v].l + tree[v].r) >> 1 ;
if(pos <= mid)
update(pos , op , left);
else update(pos , op , right) ;
push_up(v) ;
}
int main()
{
// freopen("in.txt" ,"r" , stdin) ;
int n , m ;
while(~scanf("%d%d" , &n , &m))
{
build(1 , n , 1) ;
int pos ;
int top = 0 ;
char ch[10] ;
while(m--)
{
scanf("%s" , ch) ;
if(ch[0] == 'D')
{
scanf("%d" , &pos) ;
stack[++top] = pos ;
update(pos , 0 , 1) ;
}
else if(ch[0] == 'R')
{
if(!top)continue ;
pos = stack[top--] ;
update(pos , 1 , 1) ;
}
else
{
scanf("%d" , &pos) ;
printf("%d
" , query(1 , pos)) ;
}
}
}
return 0 ;
}