AtCoder Beginner Contest 080 D - Recording

問題URL

D - Recording

解法

との種類がとても少ないので、これを利用することにします。
ある時間のテレビの利用状況は、bit整数を一つ用いて、番目のbitが立っていたらチェンネルを録画するというように表現できます。
ここで、ある時間に、録画したいチャンネルを新たに加えることを考えます。
それは、ある時間の既に録画予定のチャンネルを表す整数を、新たに録画したいチャンネルをとして、bit演算を用いて、
<< と表せます。
これは、ある時間のあるチャンネルを録画するクエリが複数来ることがないので、<< と加算の形で表してしまって問題ないです。
この操作を区間について行います。
この操作は加算の形で表せるので、予め で初期化した長さの数列に対し、クエリごとに区間に<< を加算します。
すべてのクエリを処理したあとに、数列の各要素について、立っているbitの数の中で最も多いものがこの問題の答えです。
区間加算にimos法を用いることによって、回程度の計算で答えを得ることができます。

ACしたコード

区間加算に遅延評価セグメントツリーを用いています。

atcoder.jp

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

class SegmentTreeRSQ {
private:
    int n;
    vector<LL> node, lazy;

public:
    void init(vector<LL> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, LL x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

   LL getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        LL vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        LL vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};

int main(){
    int N,C;cin >> N >> C;
    SegmentTreeRSQ Seg;
    Seg.init(vector<LL>(1e5+1));
    for(int i = 0;i < N;i++){
        int s,t;cin >>s >> t;
        s--,t--;
        int c;cin >> c;
        Seg.add(s, t+1, (1 << c));
    }
    int ans = 0;
    for(int i = 0;i < 1e5+10;i++){
        ans = max((int)bitset<60>(Seg.getsum(i, i+1)).count(), ans);
    }
    cout<<ans<<endl;
}