[BZOJ5011][JXOI2017]颜色

5011: [Jx2017]颜色
Time Limit: 30 Sec Memory Limit: 512 MB
Submit: 84 Solved: 46
[Submit][Status][Discuss]
Description

可怜有一个长度为n的正整数序列Ai，其中相同的正整数代表着相同的颜色。

现在可怜觉得这个序列太长了，于是她决定选择一些颜色把这些颜色的所有位置都删去。

删除颜色i可以定义为把所有满足Aj=i的位置j都从序列中删去。

然而有些时候删去之后，整个序列变成了好几段，可怜不喜欢这样，于是她想要知道有多

少种删去颜色的方案使得最后剩下来的序列非空且连续。

例如颜色序列{1,2,3,4,5}，删除颜色3后序列变成了{1,2}和{4,5}两段，不满足条件。

而删除颜色1后序列变成了{2,3,4,5}，满足条件。

两个方案不同当且仅当至少存在一个颜色i只在其中一个方案中被删去。

。

Input

第一行输入一个整数T表示数据组数。

每组数据第一行输入一个整数n表示数列长度。

第二行输入n个整数描述颜色序列。

1 ≤ T, ∑ n ≤ 3 × 10^5, 1 ≤ Ai ≤ n

Output

对于每组数据输出一个整数表示答案

Sample Input

1
5
1 3 2 4 3

Sample Output

6
//满足条件的删颜色方案有 {1}, {1, 3}, {1, 2, 3}, {1, 3, 4}, {2, 3, 4}, ∅

HINT

为试题的完整性，下面给出Jxoi2017题面及前两题数据www.lydsy.com/JudgeOnline/upload/jxoi2017.rar

Source

By 佚名上传

[Submit][Status][Discuss]

一道不会做的线段树模板题。

https://www.luogu.org/problemnew/solution/P4065

首先发现每个删除方案和结果区间一一对应，所以只要统计合法区间总数即可。

枚举区间右端点i，这时不合法的左端点区间有且仅有：

1.$[1,j]quad Max_{c_j}>i$

2.$(Min_{c_j},Max_{c_j}]quad Max_{c_j}leqslant i$

这样我们先将所有[1,i]全部+1，然后每次撤销不再禁用的点，加上新增的禁用点，然后查询[1,i]内所有不禁用的点即可。

问题是，上哪找支持区间+1，区间-1，查询区间内0的个数的数据结构呢？线段树看上去是无法完成的。

那么我们用栈代替这个过程，这样就只需要支持区间标记和查询区间内标记的数的个数即可，于是这题就变成了线段树模板题。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define ls (x<<1)
 4 #define rs ((x<<1)|1)
 5 #define lson ls,L,mid
 6 #define rson rs,mid+1,R
 7 #define rep(i,l,r) for (int i=l; i<=r; i++)
 8 typedef long long ll;
 9 using namespace std;
10 
11 const int N=300100,inf=0x3f3f3f3f;
12 ll res;
13 int n,T,top,mn[N],mx[N],cnt,c[N],v[N<<2],cov[N<<2];
14 struct P{ int c,pos; }stk[N];
15 
16 void push(int x,int L,int R){
17     if (!cov[x]) return;
18     int mid=(L+R)>>1;
19     v[ls]=mid-L+1; v[rs]=R-mid;
20     cov[ls]=1; cov[rs]=1; 
21 }
22 
23 void add(int x,int L,int R,int l,int r){
24     if (L==l && r==R) { v[x]=r-l+1; cov[x]=1; return; }
25     int mid=(L+R)>>1; push(x,L,R);
26     if (r<=mid) add(lson,l,r);
27     else if (l>mid) add(rson,l,r);
28         else add(lson,l,mid),add(rson,mid+1,r);
29     v[x]=v[ls]+v[rs];
30 }
31 
32 int que(int x,int L,int R,int l,int r){
33     if (L==l && r==R) return v[x];
34     int mid=(L+R)>>1; push(x,L,R);
35     if (r<=mid) return que(lson,l,r);
36     else if (l>mid) return que(rson,l,r);
37         else return que(lson,l,mid)+que(rson,mid+1,r);
38 }
39 
40 int main(){
41     freopen("bzoj5011.in","r",stdin);
42     freopen("bzoj5011.out","w",stdout);
43     for (scanf("%d",&T); T--; ){
44         scanf("%d",&n); res=0; top=0;
45         rep(i,1,n) scanf("%d",&c[i]);
46         rep(i,1,n) mn[i]=inf,mx[i]=0;
47         rep(i,1,n<<2) cov[i]=0,v[i]=0;
48         rep(i,1,n) mn[c[i]]=min(mn[c[i]],i),mx[c[i]]=max(mx[c[i]],i);
49         rep(i,1,n){
50             if (i==mx[c[i]] && mx[c[i]]!=mn[c[i]]) add(1,1,n,mn[c[i]]+1,mx[c[i]]);
51             else stk[++top]=(P){c[i],i};
52             while (top && mx[stk[top].c]<=i) top--;
53             int l=((!top)?0:stk[top].pos);
54             if (i!=l) res+=i-l-que(1,1,n,l+1,i);
55         }
56         printf("%lld
",res);
57     }
58     return 0;
59 }