yukicoder : No.1526 Sum of Mex 2

色々解き方がありそう。
https://yukicoder.me/problems/no/1526

問題

整数列Aが与えられる。
連続した部分列全通りに対し、mexの値の総和を求めよ。

解法

区間[L,R]を考える際、左端Lを固定したときのことを考える。
ある値vに着目し、Lに最寄りのA[x]=vとなるxが区間内にあるとする。
この時、Rがx未満の場合、区間内にvが登場しないので、mex値がv+1になりえない。

これらの条件を合わせると、「右端がこの手前の場合、mex値がこの値以上になりえない」という範囲がたくさんできる。
この範囲の和を取ると、取りえないmex値の総和が取れる。
この範囲の和は、いわゆる1点を共有する長方形の和集合なので、mapを1個使えばJOI Fishのテクで数え上げることができる。

なお、Lをずらしていくと、A[L]=A[x]=vとなる最寄りのxに対し、「右端がx未満の場合、mex値がv+1以上になりえない」と範囲が1個追加されていくだけなので、全体でO(NlogN)で解ける。

int N;
int A[202020];
set<int> S[202020];

class AreaRect {
	map<ll,ll> M;
public:
	ll sum;
	AreaRect() {
		M[0]=1LL<<60;
		M[1LL<<60]=0;
		sum=0;
	}
	void add(ll x,ll y) {
		auto k=M.lower_bound(x);
		if(k->second>=y) return;
		while(prev(M.lower_bound(x))->second<=y) {
			auto p=*prev(M.lower_bound(x));
			M.erase(p.first);
			sum-=(p.first-prev(M.lower_bound(p.first))->first)*(p.second-M.lower_bound(p.first)->second);
		}
		sum += (x-prev(M.lower_bound(x))->first)*(y-M.lower_bound(x)->second);
		M[x]=y;
	}
};
AreaRect ar;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[A[i]].insert(i+1);
		S[i+1].insert(N+1);
	}
	for(i=1;i<=N;i++) {
		x=*S[i].begin();
		ar.add(N+1-i,x);
	}
	ll ret=1LL*N*(N+1)/2;
	FOR(i,N) {
		ret+=1LL*N*(N+1)-ar.sum;
		S[A[i]].erase(S[A[i]].begin());
		x=*S[A[i]].begin();
		ar.add(N+1-A[i],x);
		
	}
		
	cout<<ret<<endl;
}

まとめ

もっとシンプルに解けるといいんだけどな。