[AtCoder Regular 177 D] Earthquakes

https://atcoder.jp/contests/arc177/tasks/arc177_d

 

Ob 1) 서로 쓰러뜨릴 수 있는 관계라는 것은 그 사이에 있는 모든 도미노 사이사이 간격이 H 이하라는 것

Ob 2) 간격이 H 이하인 도미노들은 각각 묶어서 생각해도 된다. 서로 다른 그룹에 속한 도미노는 영향을 줄 수 없음

 

Todo 1) 그룹끼리 일단 묶어놓기

 

Ob 3) 예제 설명의 수형도를 잘 관찰하자. 수형도가 중도에 끊기지 않는 완전 이진 트리 형태가 되도록 변형시킨다면, 동일한 시나리오가 몇 번 중복되었는지가 그 시나리오가 발생할 확률을 나타낸다. 즉, '무의미한 무너뜨림'을 전부 중복으로 세어주도록 하자.

 

Ob 4) 아무튼 한 그룹에 대해서 잘 세어주는 것은 관찰한 사실을 바탕으로 monotone stack을 관리하면 구해줄 수 있게 된다.

 

Motive 1) 서로 다른 그룹 간에 영향을 주는 것을 어떻게 처리하지? -> Range update Point query를 지원하는 세그트리를 이용하면 된다.

 

화이팅!

 

코드

const ll N = 2e5+3;
ll n, h;
ll x[N];
RUPQ<mint,N> ans;
ll IS[N], DS[N], LF[N], RF[N];

void solve(vi &G) {
    ll m = siz(G);
    sort(all(G), [](ll i, ll j){ return x[i] < x[j]; });
    
    stack<ll> stk;
    rep(i,0,m-1) {
        while (!empty(stk)&&stk.top()>G[i]) stk.pop();
        IS[G[i]] = siz(stk), stk.push(G[i]);
        if (i>0)
            LF[G[i]] = G[i-1]>G[i];
    }
    while(!empty(stk))stk.pop();
    per(i,0,m-1) {
        while (!empty(stk)&&stk.top()>G[i]) stk.pop();
        DS[G[i]] = siz(stk), stk.push(G[i]);
        if (i<m-1)
            RF[G[i]] = G[i]<G[i+1];
    }
    
    sort(all(G));
    mint S = 0;
    rep(i,0,m-1) {
        ll dc = 0;
        if (LF[G[i]]&&RF[G[i]]) dc=0;
        else if (LF[G[i]]^RF[G[i]]) dc=1;
        else dc=2;
        mint A = pw(2,m-1 - IS[G[i]] - DS[G[i]]) * dc;
        if (i==0)
            ans.update(0, G[i]-1, 0);
        ans.update(G[i]+1, (i+1<m?G[i+1]:n+1)-1, S+=A);
        ans.update(G[i], G[i], A);
    }
}

disjoint_set<N> ds;
vi grps[N];
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> h;
    if (n==1) {
        cout << 2;
        return 0;
    }
    {
        map<ll,ll> v;
        rep(i,1,n) cin >> x[i], v[x[i]] = i;
        
        for (auto it = begin(v); next(it)!=end(v); ++it) {
            if (next(it)->fi - it->fi <= h) {
                ds.merge(it->se, next(it)->se);
            }
        }
    }
    rep(i,1,n) {
        grps[ds.find(i)].push_back(i);
    }
    
    ans.set(n+2, 1, [](mint x, mint y){ return x*y; });
    
    for (auto &g : grps) if (!empty(g)) {
        solve(g);
    }
    
    rep(i,1,n) {
        cout << ans.query(i) << ' ';
    }
}