AGC038 B - Sorting a Segment (700)

B - Sorting a Segment

概要

0からN-1のN個の整数の順列Pと整数Kが与えられる。この順列を用いて下記の操作を行った後にできる数列の種類数を答えよ。

• 順列Pの連続するK項を昇順に並べ替える

制約

2 ≦ N ≦ 2 * 10 ^ 5

方針

昇順にするK項の最初の各項について、操作を行った結果が同じ数列になるものを同じグループとするようにUnion-Find木に登録していき、最終的にグループ数（異なる親の数）を答えればよい。

同じグループになるのは次の2種類の場合がある。
①i番目から昇順にする場合とi+1番目から昇順にする場合について
両者が同じグループになる場合、前者はi番目の項が変化してはならず、かつ後者はi+K番目（最後）の項が変化してはならない。
逆にこの条件を満たす場合、両者は同じグループになる。
これはmultisetで昇順にする対象を保持しておき、前者はp[i]番目とmsの最小の項が同じであればよく、後者はp[i+K]とmsの最大の項が同じであればよい。msの最小の項はms.begin()で取得、msの最大の項はitr = ms.end(); itr--;で取得した。

②元の数列から変化しない場合
i番目からi+K-1番目までが昇順で並ぶ場合は、元の数列から変化しない。
これを確認するためには、(i, i+1), (i+1, i+2), ..., (i+K-2, i+K-1)の各ペアについて、p[j]

解答

Submission #7653031 - AtCoder Grand Contest 038

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
// union-find tree with size(struct)
struct UnionFind {
    vector<int> par; // 親ノード
    vector<int> rank; // ランク
	vector<int> size; // 連結成分のサイズ
 
    UnionFind(int n = 1) {
        init(n);
    }
 
    void init(int n = 1) {
        par.resize(n);
		rank.resize(n);
		size.resize(n);
        for (int i = 0; i < n; ++i){
			par[i] = i;
			rank[i] = 0;
			size[i] = 1;
		}
    }
 
    int find(int x) {
        if (par[x] == x)  return x;
 
        int r = find(par[x]);
        return par[x] = r;
    }
 
    bool issame(int x, int y) {
        return find(x) == find(y);
    }
 
    bool unite(int x, int y) {
	    x = find(x);
		y = find(y);
	    if (x == y) return false;
 
	    if (rank[x] < rank[y]) swap(x, y);
	    if (rank[x] == rank[y]) ++rank[x];
	    par[y] = x;
		size[x] += size[y];
	    return true;
    }
 
	int getSize(int x){
		return size[find(x)];
	}
 
	int getRank(int x){
		return rank[find(x)];
	}
};
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n, k;
	cin >> n >> k;
 
	vector<int> p(n);
	rep(i, n) cin >> p[i];
 
	UnionFind uf(n-k+1);
 
	multiset<int> ms;
	rep(i, k) ms.insert(p[i]);
 
	for(int i = 0; i < n - k; i++){
		bool ok = *ms.begin() == p[i];
		ms.erase(p[i]);
		ms.insert(p[i + k]);
 
		auto itr = ms.end();
		itr--;
		if(ok && (*itr == p[i + k])){
            // cout << "unite:" << i << "," << i+1 << endl;
			uf.unite(i, i + 1);
		}
	}
 
	vector<int> a(n-1, 0);
	rep(i, n-1){
		if(p[i] < p[i+1]) a[i]++;
	}
 
	vector<int> b(n-k+1, 0);
	rep(i, k - 1){
		b[0] += a[i];
	}
 
	vector<int> v;
	if(b[0] == k - 1) v.push_back(0);
 
	for(int i = 1; i < n - k + 1; i++){
		b[i] = b[i-1] - a[i-1] + a[i+k-2];
		if(b[i] == k - 1) v.push_back(i);
	}
 
    // cout << "a:";
    // rep(i, n-1) cout << a[i] << (i == n-2 ? "\n" : " ");
    //
    // cout << "b:";
    // rep(i, n-k+1) cout << b[i] << (i == n-k ? "\n" : " ");
 
	int m = v.size();
 
    // if(m > 0) {
    //     cout << "initial order:";
    //     rep(i, m) cout << v[i] << (i == m - 1 ? "\n" : " ");
    // }
 
	rep(i, m-1){
		if(!uf.issame(v[0], v[i+1])){
			uf.unite(v[0], v[i+1]);
		}
	}
 
	set<int> st;
	rep(i, n-k+1){
		if(st.count(uf.find(i)) == 0){
			st.insert(i);
		}
	}
 
	cout << st.size() << endl;
}