HDU 1540

3323 단어 데이터 구조
void pushup(int pos){
    node[pos].lx = node[lson].lx;
    node[pos].rx = node[rson].rx;
    if(node[pos].lx == node[lson].len()) node[pos].lx += node[rson].lx;
    if(node[pos].rx == node[rson].len()) node[pos].rx += node[lson].rx;
    node[pos].mx = node[lson].rx + node[rson].lx;
    node[pos].mx = max(node[pos].mx,max(node[lson].mx,node[rson].mx));
}
/*
Tunnel Warfare
   :    
            
*/
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define lson (pos<<1)
#define rson (pos<<1|1)
const int maxn = 55555;
int n,m,x;
char op[10];
struct Node{
   int l,r,lx,rx,mx;
   int mid(){
        return (l + r) >> 1;
   }
   int len(){
        return (r - l + 1);
   }
}node[maxn << 2];
void pushup(int pos){
    node[pos].lx = node[lson].lx;
    node[pos].rx = node[rson].rx;
    if(node[pos].lx == node[lson].len()) node[pos].lx += node[rson].lx;
    if(node[pos].rx == node[rson].len()) node[pos].rx += node[lson].rx;
    node[pos].mx = node[lson].rx + node[rson].lx;
    node[pos].mx = max(node[pos].mx,max(node[lson].mx,node[rson].mx));
}
void build(int l,int r,int pos){
    node[pos].l = l;
    node[pos].r = r;
    if(l == r){
        node[pos].lx = node[pos].rx = node[pos].mx = 1;
        return;
    }
    int mid = node[pos].mid();
    build(l,mid,lson);
    build(mid + 1,r,rson);
    pushup(pos);
}
void update(int pos,int m,int d){
    if(node[pos].l == node[pos].r){
        node[pos].lx = node[pos].rx = node[pos].mx = d;
        return;
    }
    int mid = node[pos].mid();
    if(m <= mid)
        update(lson,m,d);
    else
        update(rson,m,d);
    pushup(pos);
}
int query(int pos,int m){
    if(node[pos].l == node[pos].r || node[pos].mx == 0 || node[pos].mx == node[pos].len()){
        return node[pos].mx;
    }
    int mid = node[pos].mid();
    if(m <= mid){
        int v = mid - node[lson].rx + 1;
        if(m >= v)
            return query(lson,m) + query(rson,mid + 1);
        else
            return query(lson,m);
    }
    if(m > mid){
        int v = mid + node[rson].lx;
        if(m  <=  v)
            return query(rson,m) + query(lson,mid);
        else
            return query(rson,m);
    }
}
void debug(int pos){
    printf("[%d %d] lx:%d rx:%d mx:%d
",node[pos].l,node[pos].r,node[pos].lx,node[pos].rx,node[pos].mx); if(node[pos].l == node[pos].r) return; debug(lson); debug(rson); } int main(){ while(scanf("%d%d",&n,&m) != EOF){ build(1,n,1); stackst; for(int i = 0; i < m; i++){ scanf("%s",op); if(op[0] == 'D'){ scanf("%d",&x); st.push(x); update(1,x,0); } else if(op[0] == 'R'){ if(st.empty()) continue; x = st.top(); st.pop(); update(1,x,1); } else if(op[0] == 'Q'){ scanf("%d",&x); printf("%d
",query(1,x)); } } } return 0; }

좋은 웹페이지 즐겨찾기