ARC 045 B - ドキドキデート大作戦高橋君

問題

問題概要

N人の人がM個の教室を掃除する. 一人が掃除する連続区間の教室が与えられる. ひとつの教室につき一人以上が掃除をしていればいい. どの区間を掃除する人はさぼることができるか. さぼる人は 同時に1人として考える.

解法

まずimos法を利用して, i番目の教室の掃除を割り当てられている人が何人いるかを求める.
あとは, 教室の掃除が何人に割り当てられているかをもつsegtreeを作り, 一人の人が掃除する区間の最小値が1より大きければ, その人が掃除をしなくてもその区間をだれかが掃除することになりその人はサボれることになる.
値が更新がないので, SparseTableでも解くことができる.

ミス

なし.

コード

高速化したsegtree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, INF); //(1) 初期値を最大に
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        for (dat[k += n] = val; k > 0; k >>= 1){ // kを含む区間のインデックスを下から順に列挙
            dat[k>>1] = min(dat[k], dat[k ^ 1]); // (2) 区間の最大値で更新
        }
    }
    T query(int l, int r){
        T ret = INF; //(3) 最小値に関係ない値
        for (l += n, r += n; l < r; l >>= 1, r >>= 1){
            if(l & 1) ret = min(ret, dat[l++]); //(4) 区間の最小値で更新
            if(r & 1) ret = min(ret, dat[--r]); //(4) 区間の最小値で更新
        }
        return ret;
    }
};

int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    segtree<int> seg(n);
    rep(i, n){
        seg.update(i, imos[i]);
    }
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

蟻本segtree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, INF); //(1) 初期値を最大に
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1; //葉の節点
        dat[k] = val;
        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]); // (2) 区間の最小値で更新
        }
    }
    T query(int a, int b, int k, int l, int r){ //[a, b)の最大値を求める
        if(r <= a || b <= l) return INF; //(3) 最小値に関係ない値で更新
        if(a <= l && r <= b) return dat[k];
        else{
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr); //(4) 区間の最小値で更新
        }
    }
    T query(int a, int b){
        return query(a, b, 0, 0, n);
    }
};


int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    segtree<int> seg(n);
    rep(i, n){
        seg.update(i, imos[i]);
    }
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

SparseTable

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int n, m;
int s[300010], t[300010];
int imos[300010];

template <class T> //T : table[][]の中身の型
class SparseTable{
public:
    int N, M; //table[N][M]
    // table[i][k] := [i, i + 2^k)の最小値
    vector<vector<T>> table;
    template<class S> SparseTable(int n, S &val): N(n){ // O(nlogn)
        M = 32 - __builtin_clz(N); // M - 1 <= logN < M
        table.resize(N, vector<T>(M));
        for (int i = 0; i < N; ++i){ // [i, i + 1)までの区間の最小値
            table[i][0] = val[i];
        }
        for (int k = 0; k < M - 1; ++k){ // [i, i + 2^(k+1))の区間を計算
            for (int i = 0; i + (1<< k) < N; ++i){
                // iから2^(k+1)の長さの区間の最小値を2^kの長さの区間の最小値を利用して求める
                table[i][k + 1] = min(table[i][k], table[i + (1 << k)][k]); // (1)最小値
            }
        }
    }
    T query(int l, int r){ // O(1) [l, r) の間の最小値
        int k = 31 - __builtin_clz(r - l); //区間の長さの半分以上の値 （k<= r - l < k + 1)
        return min(table[l][k], table[r - (1 << k)][k]); // (2) 最小値
    }
};

int main(void){
    cin >> n >> m;
    rep(i, m){
        cin >> s[i] >> t[i];
        s[i]--; t[i]--;
    }

    rep(i, m){
        imos[s[i]]++;
        imos[t[i] + 1]--;
    }
    rep(i, n){
        imos[i + 1] += imos[i];
    }
    SparseTable<int> seg(n, imos);
    vector<int> ans;
    rep(i, m){
        if(seg.query(s[i], t[i] + 1) >= 2) ans.pb(i + 1);
    }
    printf("%d\n", (int)ans.size());
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}