( ext{Solution})
简要的口胡
线段树维护合法左端点数量
正序枚举 (i)，将其视为右端点，去除不合法的左端点，统计贡献
再将其视为中间点，由它产生的左端点在线段树上区间加
注意到一个重复出现的 (b) 值，上一个相同位置的贡献不能再要
于是把这个点废掉
考场上又打了棵线段树，统计答案的线段树只需去掉被废掉的点即可
直接跑了 (949ms)，两只 ( ext{log}) 踩线过（后时限开到 (2s)，不算踩线了，可仍然垫底）
( ext{Code})
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
#define re register
#define LL long long
using namespace std;
const int N = 2e5 + 5;
int n, b[N], l1[N], l2[N];
LL ans;
int sum[N << 2], tag[N << 2], del[N << 2];
inline void remove(int p, int l, int r, int x)
{
if (x < l || x > r) return;
if (l == r) return void(del[p] = 1);
int mid = (l + r) >> 1;
if (x <= mid) remove(ls, l, mid, x);
else remove(rs, mid + 1, r, x);
del[p] = del[ls] + del[rs];
}
inline int count(int p, int l, int r, int x, int y)
{
if (x > y || y < l || x > r) return 0;
if (x <= l && r <= y) return del[p];
int mid = (l + r) >> 1, res = 0;
if (x <= mid) res = count(ls, l, mid, x, y);
if (y > mid) res += count(rs, mid + 1, r, x, y);
return res;
}
inline void pushdown(int p, int l, int r)
{
if (!tag[p]) return;
int mid = (l + r) >> 1;
sum[ls] += (mid - l + 1 - count(1, 1, n, l, mid)) * tag[p], tag[ls] += tag[p];
sum[rs] += (r - mid - count(1, 1, n, mid + 1, r)) * tag[p], tag[rs] += tag[p];
tag[p] = 0;
}
void update(int p, int l, int r, int x, int y, int v)
{
if (x > y || y < l || x > r) return;
if (x <= l && r <= y)
{
sum[p] += v * (r - l + 1 - count(1, 1, n, l, r)), tag[p] += v;
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) update(ls, l, mid, x, y, v);
if (y > mid) update(rs, mid + 1, r, x, y, v);
sum[p] = sum[ls] + sum[rs];
}
int query(int p, int l, int r, int x, int y)
{
if (x > y || y < l || x > r) return 0;
if (x <= l && r <= y) return sum[p];
pushdown(p, l, r);
int mid = (l + r) >> 1, res = 0;
if (x <= mid) res = query(ls, l, mid, x, y);
if (y > mid) res += query(rs, mid + 1, r, x, y);
return res;
}
int main()
{
scanf("%d", &n);
for(re int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(re int i = 1; i <= n; i++)
{
update(1, 1, n, l2[b[i]] + 1, l1[b[i]] - 1, -1);
update(1, 1, n, l1[b[i]], l1[b[i]], -query(1, 1, n, l1[b[i]], l1[b[i]]));
remove(1, 1, n, l1[b[i]]), ans += query(1, 1, n, l1[b[i]] + 1, i - 2);
update(1, 1, n, l1[b[i]] + 1, i - 1, 1), l2[b[i]] = l1[b[i]], l1[b[i]] = i;
}
printf("%lld
", ans);
}
其实只需将第二个线段树改为树状数组，尽管还是两只 ( ext{log})，但快了很多
( ext{Code})
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
#define re register
#define LL long long
using namespace std;
const int N = 2e5 + 5;
int n, b[N], l1[N], l2[N], c[N];
LL ans;
int sum[N << 2], tag[N << 2], del[N << 2];
inline int lowbit(int x){return x & (-x);}
inline void remove(int x, int v)
{
if (!x) return;
for(; x <= n; x += lowbit(x)) c[x] += v;
}
inline int querysum(int x)
{
if (!x) return 0;
int res = 0;
for(; x; x -= lowbit(x)) res += c[x];
return res;
}
inline int count(int x, int y){return querysum(y) - querysum(x - 1);}
inline void pushdown(int p, int l, int r)
{
if (!tag[p]) return;
int mid = (l + r) >> 1;
sum[ls] += (mid - l + 1 - count(l, mid)) * tag[p], tag[ls] += tag[p];
sum[rs] += (r - mid - count(mid + 1, r)) * tag[p], tag[rs] += tag[p];
tag[p] = 0;
}
void update(int p, int l, int r, int x, int y, int v)
{
if (x > y || y < l || x > r) return;
if (x <= l && r <= y)
{
sum[p] += v * (r - l + 1 - count(l, r)), tag[p] += v;
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) update(ls, l, mid, x, y, v);
if (y > mid) update(rs, mid + 1, r, x, y, v);
sum[p] = sum[ls] + sum[rs];
}
int query(int p, int l, int r, int x, int y)
{
if (x > y || y < l || x > r) return 0;
if (x <= l && r <= y) return sum[p];
pushdown(p, l, r);
int mid = (l + r) >> 1, res = 0;
if (x <= mid) res = query(ls, l, mid, x, y);
if (y > mid) res += query(rs, mid + 1, r, x, y);
return res;
}
int main()
{
scanf("%d", &n);
for(re int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(re int i = 1; i <= n; i++)
{
update(1, 1, n, l2[b[i]] + 1, l1[b[i]] - 1, -1);
update(1, 1, n, l1[b[i]], l1[b[i]], -query(1, 1, n, l1[b[i]], l1[b[i]]));
remove(l1[b[i]], 1), ans += query(1, 1, n, l1[b[i]] + 1, i - 2);
update(1, 1, n, l1[b[i]] + 1, i - 1, 1), l2[b[i]] = l1[b[i]], l1[b[i]] = i;
}
printf("%lld
", ans);
}
其实要在线段树上废掉一个点，只要将这个线段树带上系数，把这一位系数改成 (0) 即可
(Code)
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
#define re register
#define LL long long
using namespace std;
const int N = 2e5 + 5;
int n, b[N], l1[N], l2[N];
LL ans;
int sum[N << 2], tag[N << 2], c[N << 2];
inline void pushdown(int p, int l, int r)
{
if (!tag[p]) return;
int mid = (l + r) >> 1;
sum[ls] += c[ls] * tag[p], tag[ls] += tag[p];
sum[rs] += c[rs] * tag[p], tag[rs] += tag[p];
tag[p] = 0;
}
inline void change(int p, int l, int r, int x, int v)
{
if (x < l || x > r) return;
if (l == r)
{
c[p] = v, sum[p] = v * tag[p];
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) change(ls, l, mid, x, v);
else change(rs, mid + 1, r, x, v);
sum[p] = sum[ls] + sum[rs], c[p] = c[ls] + c[rs];
}
void update(int p, int l, int r, int x, int y, int v)
{
if (x > y || y < l || x > r) return;
if (x <= l && r <= y)
{
sum[p] += v * c[p], tag[p] += v;
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) update(ls, l, mid, x, y, v);
if (y > mid) update(rs, mid + 1, r, x, y, v);
sum[p] = sum[ls] + sum[rs], c[p] = c[ls] + c[rs];
}
int query(int p, int l, int r, int x, int y)
{
if (x > y || y < l || x > r) return 0;
if (x <= l && r <= y) return sum[p];
pushdown(p, l, r);
int mid = (l + r) >> 1, res = 0;
if (x <= mid) res = query(ls, l, mid, x, y);
if (y > mid) res += query(rs, mid + 1, r, x, y);
return res;
}
int main()
{
scanf("%d", &n);
for(re int i = 1; i <= n; i++) scanf("%d", &b[i]);
for(re int i = 1; i <= n; i++)
{
update(1, 1, n, l2[b[i]] + 1, l1[b[i]] - 1, -1), change(1, 1, n, l1[b[i]], 0);
ans += query(1, 1, n, l1[b[i]] + 1, i - 2);
update(1, 1, n, l1[b[i]] + 1, i - 1, 1), change(1, 1, n, i, 1);
l2[b[i]] = l1[b[i]], l1[b[i]] = i;
}
printf("%lld
", ans);
}