题目链接
题解
一定只有我这种智障会用这么奇怪的方法做这道题。。
由题我们知道最后剩余的一定是一个区间，而且区间内的颜色不存在于区间外
所以我们的目的就是为了找到这样的区间的数量
区间由左右端点确定，我们枚举右端点，尝试维护左端点数量
当我们从右向左枚举到(r)，(r)右边的颜色已经在区间外，一定不能被包含入区间，所以我们记录每个位置上一个同色位置(pre[i])，指针(r)每越过一个位置，就在(pre[i])处打一个标记，表示这个位置不能被包含。之后我们每次找到(r)左边第一个标记的位置，再往左一定不合法，这样我们就得到了我们的初始区间，记为([l,r])。这个操作可以使用线段树维护
考虑这个区间还会有什么不满足的地方
就是区间内的颜色不能出现在区间外
对于一个在(r)左侧的位置(i)，颜色为(c)，记颜色(c)最左边的位置为(p)，那么([p + 1,i])都不能被选择，因为选择其中任意一个位置，都会使颜色(c)被分割
如何维护？
另开一个线段树区间(set)为(1)即可，一个位置可能被多个区间叠加，但只能贡献(1)
由于区间(set)操作不能被撤回，所以我们更新顺序只能从左到右，但我们是从右到左枚举的，怎么办？
那就强行从左到右更新，并保存每一个版本的线段树——永久化标记主席树
这样我们就做完了这道题
复杂度(O(nlogn))
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 300005,maxm = 8000005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int ls[maxm],rs[maxm],Sum[maxm],tag[maxm],rt[maxn],cnt;
void Upd(int u){
Sum[u] = Sum[ls[u]] + Sum[rs[u]];
}
void Set(int& u,int pre,int l,int r,int L,int R){
u = ++cnt; ls[u] = ls[pre]; rs[u] = rs[pre]; tag[u] = Sum[u] = 0;
tag[u] = tag[pre];
if (tag[u]){
Sum[u] = r - l + 1;
return;
}
if (l >= L && r <= R){
tag[u] = 1; Sum[u] = r - l + 1;
return;
}
int mid = l + r >> 1;
if (mid >= L) Set(ls[u],ls[pre],l,mid,L,R);
if (mid < R) Set(rs[u],rs[pre],mid + 1,r,L,R);
Upd(u);
}
int Query(int u,int l,int r,int L,int R){
if (tag[u]) return R - L + 1;
if (l >= L && r <= R) return Sum[u];
int mid = l + r >> 1;
if (mid >= R) return Query(ls[u],l,mid,L,R);
if (mid < L) return Query(rs[u],mid + 1,r,L,R);
return Query(ls[u],l,mid,L,mid) + Query(rs[u],mid + 1,r,mid + 1,R);
}
int sum[maxn << 2],mp[maxn << 2];
void upd(int u,int l,int r){
sum[u] = sum[u << 1] + sum[u << 1 | 1];
int mid = l + r >> 1;
if (mp[u << 1 | 1] == 0) mp[u] = 0;
else if (mp[u << 1] == 0) mp[u] = mp[u << 1 | 1];
else if (mp[u << 1 | 1] == mid + 1) mp[u] = mp[u << 1];
else mp[u] = mp[u << 1 | 1];
}
void modify(int u,int l,int r,int pos){
if (l == r) {sum[u] = 1; mp[u] = 0; return;}
int mid = l + r >> 1;
if (mid >= pos) modify(u << 1,l,mid,pos);
else modify(u << 1 | 1,mid + 1,r,pos);
upd(u,l,r);
}
int query(int u,int l,int r,int L,int R){
if (!sum[u]) return l;
if (l >= L && r <= R) return mp[u];
int mid = l + r >> 1;
if (mid >= R) return query(u << 1,l,mid,L,R);
if (mid < L) return query(u << 1 | 1,mid + 1,r,L,R);
int t1 = query(u << 1,l,mid,L,R),t2 = query(u << 1 | 1,mid + 1,r,L,R);
if (t2 == 0) return 0;
else if (t1 == 0) return t2;
else if (t2 == mid + 1) return t1;
else return t2;
}
void build(int u,int l,int r){
sum[u] = 0;
if (l == r){
mp[u] = l;
return;
}
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
upd(u,l,r);
}
int last[maxn],pre[maxn],F[maxn];
int n,A[maxn];
int main(){
int T = read();
while (T--){
n = read(); REP(i,n) A[i] = read();
cnt = 0; build(1,1,n);
for (int i = 1; i <= n; i++) last[i] = 0;
for (int i = 1; i <= n; i++){
if (!last[A[i]]) F[A[i]] = i;
pre[i] = last[A[i]];
last[A[i]] = i;
rt[i] = rt[i - 1];
if (F[A[i]] < i) Set(rt[i],rt[i - 1],1,n,F[A[i]] + 1,i);
}
LL ans = 0;
for (int i = n; i; i--){
int l = query(1,1,n,1,i),r = i;
if (pre[i]) modify(1,1,n,pre[i]);
if (!l) continue;
int t = Query(rt[i],1,n,l,r);
ans += (r - l + 1) - t;
}
printf("%lld
",ans);
}
return 0;
}