Submission #1227245

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;

//根ノードを1としているので，
//左の子:k*2
//右の子:k*2+1
//親:floor(k/2)
//となる．
//根ノードを1とすると非再帰が書きやすい(二進数的性質が優れているため)のだが，
//再帰的に書くのであればどちらでも問題ない．

const int N=1<<19;//葉の個数
const int NIL = INT_MAX;

int maxi[N*2];//ノードkに対応する区間の最大値
int lazy[N*2];//lazy[k]はノードkの配下全体をlazy[k]で塗りつぶすという命令を表す．lazy[k]=NILのときは何もしないと約束する.

void setLazy(int k,int v){
     lazy[k]=lazy[k]+v;
     maxi[k]+=v;

     //***余談***
     //この発想が遅延セグメント木ではもっとも重要
     //命令がO(1)のメモリで表現でき，命令のマージが高速にできるのであれば遅延セグメント木で対処できる．
     //たとえば，区間加算と区間塗りつぶしの機能を両方備えたセグメント木を作るのであれば，
     //
     //fill v:=vで塗りつぶせ
     //add  v:=vを加算しろ
     //という二種類の命令が必要になるだろう
     //add uをした後にfill vをすることを(fill v)・(add u)と書くことにしよう．
     //この時，以下の関係式が成り立つ.
     //
     //(add v)・(add u) = (add v+u)
     //(add v)・(fill u)=(fill v+u)
     //(fill v)・(add u)=(fill v)
     //(fill v)・(fill u)=(fill v)
     //つまり add uと fill u同士の演算は(add or fill,Int)で閉じている
     //よって，命令はadd であるか fill であるかという二値情報と，加算/塗りつぶす値の2つの情報によって表現できる．
     //複数の命令を，等価な単一の命令に置き換えられるか?，と考えるとわかりやすいかも知れない
     //
     //遅延セグメント木はかならず時系列順にマージすることになる
     //これが遅延伝搬セグメント木の最大の利点と言える
     //要するに，非可換の命令を扱うのに適している
     //
     //誤解を生まないように一応書いておくが，塗りつぶしを遅延伝搬なしに書く事は不可能ではない．
     //塗りつぶした時間も保持しておけば，
     //(time S,value S)・(time T,value T)=max((timeS,valueS),(timeT,valueT))
     //として可換操作に変形できる
}

void push(int k){
   //遅延命令がなにもなければ何もしない
   if(lazy[k]==0){
      return;
   }
   
   setLazy(k*2+0,lazy[k]);
   setLazy(k*2+1,lazy[k]);
   
   //子に命令を伝搬させたので，命令を空にする
   lazy[k] =0;
}

void fix(int k){
     //ノードkに対応する区間の最大値は，「左の子の最大値」と「右の子の最大値」の最大値
     maxi[k]=min(maxi[k*2],maxi[k*2+1]);
}

//区間[queryL,queryR)にvalを足す
void add(int queryL, int queryR, int val, int k=1,int nodeL =0,int nodeR=N){
     //クエリ区間とノード区間が交差していないのなら，これ以上，処理する必要はない
     if(nodeR <= queryL || queryR<=nodeL){
        return;
     }
     //ノード区間がクエリ区間に完全に覆われたら，遅延命令をセットして，さっさと帰る
     if(queryL <= nodeL && nodeR<=queryR){
        setLazy(k,val);
        return;
     }
     //ノードが下がる時には命令をpushする
     push(k);
     int nodeM =(nodeL + nodeR) /2;
     add(queryL,queryR, val, k*2+0,nodeL, nodeM);
     add(queryL,queryR, val ,k*2+1,nodeM, nodeR);
     //ノードが上がる時には情報をfixする
     fix(k);
}

//区間[queryL,queryR)の最大値を求める
int maximum(int queryL, int queryR, int k=1,int nodeL=0,int nodeR =N){
    //クエリ区間とノード区間が交差していない
    if(nodeR<=queryL||queryR<=nodeL){
       return INT_MAX;
    }
    //ノード区間がクエリ区間に完全に覆われた
    if(queryL <= nodeL && nodeR <=queryR){
       return maxi[k];
    }
    //ノードが下がるときは命令をpushする
    push(k);
    int nodeM =(nodeL+nodeR)/2;
    int vl =maximum(queryL,queryR, k*2+0,nodeL,nodeM);
    int vr =maximum(queryL,queryR, k*2+1,nodeM,nodeR);
    fix(k);
    return min(vl,vr);
}

//初期化
void init(){
     REP(i,2*N){
         lazy[i]=0;
         maxi[i]=0;
     }
}
int S[100010];
int T[100010];
int ans[100010];
int main(){
	int W,M;
	cin>>W>>M;
	//初期化
	init();
	REP(i,M){
	    int l,r;
	    cin>>l>>r;
	    S[i]=l;
	    T[i]=r;
	    add(l,r+1,1);
	}
	int count=0;
	REP(i,M){
	    add(S[i],T[i]+1,-1);
	    if(maximum(S[i],T[i]+1)>0){
	       ans[count]=i+1;
	       count++;
	    }
	    add(S[i],T[i]+1,1);
	}
        cout<<count<<endl;
        REP(i,count){
            cout<<ans[i]<<endl;
        }
	return(0);
}

Submission Info

Judge Result