Codeforces 74 D. Hanger - simezi

問題

n個のハンガーが一列に並んでいて、左から順に1からnの番号がついている。
以下のようなクエリがq個来るので処理せよ。

0 l r l以上r以下の番号のハンガーのうち、上着がかけられているハンガーの数を出力する。
(0以外の数字) 数字のidをもつ人が、次のような手順でハンガーを探し、上着をかける。偶数回目の場合は、その人が自分の上着を持っていく。

連続して上着のかけられていない区間のうち、最も長さの長いものを見つける。（複数ある場合もっとも右にあるものを選ぶ）
区間の中央の番号のハンガーを選ぶ。（区間の長さが偶数の場合、右側のものを選ぶ）

制約条件

n≦10^9
q≦10^5

方針

mapによるbinary indexed tree + set

区間は、長さ（タイの場合は右にある）順に順序づけしてsetに入れれば、使う区間がO(log q)で見つかる。
一つの区間に上着をかけたとき、その区間は二つにわかれるが、それぞれ新しい区間をsetに入れればよい。

上着をもっていくときは、上着の両隣の上着をみることにより（これは二分探索でO(log q)でできる）、
上着の両隣の区間がわかる。
両隣の区間をsetから削除し、それらをつなげた区間をsetに入れればいい。

l以上r以下の上着の個数の求め方であるが、
これはbinary indexed treeを工夫して作ることで対応できる。
普通はbinary indexed treeは配列で作るが、mapで作ることで10^9以下のnに対する累積和が求められるようになる。
（nに対してqは小さいので、メモリも間に合う

ソースコード

struct itv{
  int l,r;
  bool operator<(const itv &b)const{
    return r-l!=b.r-b.l?r-l>b.r-b.l:r>b.r;
  }
};
int n,q;
map<int,int> bit;
int sum(int i){
  int res=0;
  for(;i;i-=i&-i)if(bit.count(i))res+=bit[i];
  return res;
}
void add(int i,int x){
  for(;i<=n;i+=i&-i)bit[i]+=x;
}
set<itv> itvs;
set<int> nums;
set<int>::iterator it,jt;
map<int,int> pos;

void run(){
  scanf("%d%d",&n,&q);
  nums.insert(0);
  nums.insert(n+1);
  itvs.insert((itv){ 1, n });
  
  rep(i,q){
    int id; scanf("%d",&id);
    if(id==0){
      int l,r; scanf("%d%d",&l,&r);
      printf("%d\n",sum(r)-sum(l-1));
    }
    else{
      if(pos[id]==0){
        itv mx=*itvs.begin();
        itvs.erase(mx);
        int mid=(mx.l+mx.r+1)/2;
        pos[id]=mid;
        nums.insert(mid);
        add(mid,1);
        if(mx.l<=mid-1)itvs.insert((itv){ mx.l,mid-1 });
        if(mid+1<=mx.r)itvs.insert((itv){ mid+1,mx.r });
      }
      else{
        int pre,mid,nxt;
        mid=pos[id];
        it=jt=nums.find(mid);
        pre=*--it;
        nxt=*++jt;
        if(pre+1<=mid-1)itvs.erase((itv){ pre+1,mid-1 });
        if(mid+1<=nxt-1)itvs.erase((itv){ mid+1,nxt-1 });
        if(pre+1<=nxt-1)itvs.insert((itv){ pre+1,nxt-1 });
        nums.erase(mid);
        add(mid,-1);
        pos[id]=0;
      }
      cerr<<endl;
    }
  }
}