AtCoder ABC #346 (ユニークビジョンプログラミングコンテスト2024 春) : G - Alone

結構手間取ってしまった。
https://atcoder.jp/contests/abc346/tasks/abc346_g

問題

整数列Aが与えられる。
連続部分列のうち、1回しか現れない値を含むものは何通りか。

解法

区間[L,R]に対し、Lを固定したときに条件を満たすRの範囲を考える。
A[i]=A[j]=xとなる、L以上最小のiと2番目のjを考える。
そうするとRが[i,j)の範囲を取るとき条件を満たす。
xを総当たりすることを考えると、複数の区間の和集合の大きさを高速に求められれば良い。

これは、遅延伝搬SegTreeで、ノードに対応する区間のうち、1つ以上の区間でおおわれている長さを管理するようにすればよい。
Lを小さい順に走査すると、A[L]=A[i]=A[j]=xとなっているとき、Rの取りえる範囲は[L,i)だったが、LをL+1に遷移するときにRの取りえる範囲が[i,j)にずれるので、それをSegTree上で加減算していく。

int N;
int A[202020];
vector<int> P[202020];

template<class V,int NV> class SegTree_Cover {
public:
	vector<V> val,cover;
	SegTree_Cover(){val.resize(NV*2); cover.resize(NV*2);};

	int getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 0;
		if(x<=l && r<=y) {
			if(cover[k]) return r-l;
			return val[k];
		}
		return getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1);
	}

	int update(int x,int y,V v,int l=0,int r=NV,int k=1) {
		if(x<=l && r<=y) {
			cover[k]+=v;
		}
		else if(max(x,l)<min(r,y)) {
			val[k]=update(x,y,v,l,(l+r)/2,k*2)+update(x,y,v,(l+r)/2,r,k*2+1);
		}
		if(cover[k]>0) return r-l;
		return val[k];
	}
};
SegTree_Cover<ll,1<<20> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		P[A[i]].push_back(i);
	}
	FOR(i,N) {
		P[i].push_back(N);
		P[i].push_back(N);
		st.update(P[i][0],P[i][1],1);
	}
	
	ll ret=0;
	FOR(i,N) {
		ret+=st.getval(0,N);
		x=A[i];
		y=lower_bound(ALL(P[x]),i)-P[x].begin();
		st.update(P[x][y],P[x][y+1],-1);
		st.update(P[x][y+1],P[x][y+2],1);
	}
	cout<<ret<<endl;
	
}

まとめ

区間の和集合の総長を取るの、典型っぽく見えるけど手元に整備されてなかった…。