さかなのきもち

競技プログラミングの話が主になるかもしれません

全国統一プログラミング王決定戦本戦 D - Deforestation 解説

感想

本戦は4完で157位でした。
もっと頑張りたかった……

思考過程

  • こういう場合は、視点を逆にすると良い。つまり、「各操作について、どこの竹を刈り取って何ポイント獲得するか」と考えるのではなくて、「各竹について、どの操作によってポイントを獲得できているのか」と考える。
  • そこで各竹ごとに考えると、要するに最後に刈り取った時間が大事なのだと気づく。
  • よって、操作するたびに、操作した竹に「何回目の操作か」を意味する番号を振っていき、最後に竹ごとにみるときにその最大値を取り出して計算する。

実装その1

  • 範囲に関する操作を行う問題なので、(計算量を減らすために)セグメント木を使おうと(本戦中は)思った。

1回目の操作で2番目から4番目、2回目の操作で1番目から7番目の竹を刈り取ったとすると、
1回目の操作では[2-3],[4-4]、2回目の操作では[1-1][2-3][4-7]のノードが、それぞれ1と2に更新される。
(※[a-b] := a以上b以下の竹)

  • 全操作が終わったときに、各竹について「何回目の操作か」を意味する番号の最大値を求める。

例えば3番目の竹について求めるときだったら、[0-7][0-3][2-3][3-3]のうち、もっとも大きい値を取り出す。
(ちなみに、今回最大値のみを取り出せばよいので、「操作を後ろから行っていき、すでに番号を振ったところはスルーする」という方法でやろうかとも思ったけど難しそうなのでやめた。)

ll segtree[800005];
ll segn;
 
void seginit(ll n_){
    segn = 1;
    while(segn < n_)segn *= 2;
    for(int i=0;i<2*segn-1;i++)segtree[i] = -1;
}
void paint(ll a,ll b,ll k,ll l,ll r,ll times){
	//a以上b未満の範囲に、timesの値を更新する
    if(r <= a || b <= l){
	//ノードがa以上b未満の範囲と重ならない場合
	return;
    }
    if(a <= l && r <= b){
	//ノードがa以上b未満の範囲にすっぽり含まれる場合
        segtree[k] = times;
        return;
    }else{
        //以上のどちらでもない場合
        paint(a,b,k * 2 + 1,l ,(l + r) / 2,times);
        paint(a,b,k *+ 2 + 2,(l + r )/2 ,r,times);
        return;
    }
}
ll query(ll a,ll k,ll l,ll r){
    //aを含む部分についてのクエリ
	//k番目のノードの範囲がl以上r未満
    if(r <= a || a <  l){
	//aを含まない場合
	//不適なので、負の無限大を返すことにする
        return -INF;
    }
    if(a == l && r == a + 1){
	//aを含み、それ以上分割できない範囲の場合
        return segtree[k];
    }else{
	//aを含む、ある程度長い範囲の場合
	//最大値を返すことに注意
        ll one = query(a,k * 2 + 1,l ,(l + r) / 2);
        ll two = query(a,k *+ 2 + 2,(l + r )/2 ,r);
        ll three = segtree[k];
        one = max(one,two);
        return max(one,three);
    }
}
 
int main(){
    cin >> n >> m;
    for(i=0;i<m;i++){
        cin >> t[i] >> l[i] >> r[i];
    }
    seginit(n+5);
    for(i=0;i<m;i++){
	//0-indexedにするために1ずつ引いている
        paint(l[i] - 1,r[i],0, 0, segn,i);
    }
    ans = 0;
    for(i=0;i<n;i++){
        a = query(i,0,0,segn);
        if(a == -1)continue;
        ans += t[a];
    }
    p(ans);        
    return 0;
}