AtCoder Beginner Contest 346 G

# G - Alone (atcoder.jp)

ABC 346 这一场来说相对比较简单，F是一个细节比较多的二分，G也算是一个比较板子的题。

简单说一下 G 题的思路。

其实比较容易想到用两个数组维护第 i 个数 \(a_i\) 在第 i 位之前出现的位置，以及第 i 个数在第 i 位之后出现的位置。那么当前位的能够满足的区间就为 \((i - last_i) * (next_i - i)\)

但是每一位都这样算会有重复，我们考虑一下如何去重。

对于第一组样例：

5
2 2 1 2 1

我们发现相乘的本质实际上与分布原理有一定关系，于是把对应的区间画出来。

可以得到上图，我们再联系一下，从两个不同区间选两个数的方案数等于两个不同区间元素个数乘积，画图即矩形的面积。

会发现所有矩形的并的面积即是答案，不难想到扫描线算法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 5e5+5;
ll X[MAXN], n, ans, a[MAXN];
ll l[MAXN];
ll last[MAXN], nxt[MAXN];
struct line{
	ll x1, x2, y;
	ll tag;
}L[MAXN];
bool operator < (line xx, line yy){
	return xx.y < yy.y;
}
struct node{
	ll l, r;
	int cnt, len;
}tr[MAXN << 3];
void build(ll x, ll l, ll r){
	tr[x] = {l, r, 0, 0};
	if(l == r) return;
	ll mid = l + r >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
}
void pushup(ll x){
	ll l = tr[x].l, r = tr[x].r;
	if(tr[x].cnt) tr[x].len = X[r + 1] - X[l];
	else tr[x].len = tr[x << 1].len + tr[x << 1 | 1].len;
}
void modify(ll x, ll l, ll r, ll w){
	if(tr[x].r < l || r < tr[x].l) return;
	if(l <= tr[x].l && tr[x].r <= r){
		tr[x].cnt += w;
		pushup(x);
		return;
	}
	modify(x << 1, l, r, w);
	modify(x << 1 | 1, l, r, w);
	pushup(x);
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		last[i] = l[a[i]];
		nxt[l[a[i]]] = i;
		nxt[i] = n + 1;
		l[a[i]] = i;
	}
	for(int i = 1; i <= n; i ++){
		L[i] = {last[i], i, i, 1};
		L[n + i] = {last[i], i, nxt[i], -1};
		X[i] = last[i];
		X[n + i] = i;
	}
	n <<= 1;
	sort(L + 1, L + n + 1);
	sort(X + 1, X + n + 1);
	int len = unique(X + 1, X + n + 1) - (X + 1);//去重 因为从 1开始所以减 x+1
	build(1, 1, len - 1);
	unordered_map<ll, ll> mp;
	for(int i = 1; i <= len; i ++){
		mp[X[i]] = i;
	}
	for(int i = 1; i < n; i ++){
		modify(1, mp[L[i].x1], mp[L[i].x2] - 1, L[i].tag);
		ans += tr[1].len * (L[i + 1].y - L[i].y);
//		cout << L[i].y << endl;
	}
	cout << ans << endl;
	return 0;
}