P7530 题解

· · 题解

今天模拟赛遇到的题目。第一眼看上去就像数据结构，可是不会打。以为是分块计数然后算之类的（虽然实际上也能用分块维护）。赛后弄了半天才想通。

首先我们设 pre_i 为 b_i 在数组中上一次出现的位置。

接着我们从前往后枚举变量 r，即我们要选的区间右端点。这个时候我们需要做到 O(\log n) 来查询对于一个右端点的可行答案。

先考虑此时有哪些左端点可选。发现左端点只可能位于 [pre_i+1,i-1] 中。那么就考虑怎么选中间的领队 mid。

回过头来，我们来看看枚举变量 r 时每个元素如何影响答案。

首先，我们找到 pre_r，它不可以作为左端点更新答案了；同时，[pre_{pre_r}+1,pre_r-1] 因为在 r 出现了 b_r，这段区间中的 b_i 不可以再作为中间点了。

因此，我们可以使用线段树维护答案，对于每个节点维护其区间内可作为左端点的数字个数 lsum，可作为中间点的数字个数 midsum 以及对答案的贡献 sum。

枚举 r 时，按照上面的步骤处理 pre_r，然后更新最终答案 ans；接着，r 可作为左端点了，[pre_i+1,r-1] 也可作为中间点了。

具体实现可见代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
long long n,num[200010],where[200010],pre[200010];
struct node
{
    long long l_num,mid_num,sum,lazy;
}tree[800010];
void pushup(long long now)
{
    tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
    tree[now].l_num=tree[now<<1].l_num+tree[now<<1|1].l_num;
    tree[now].mid_num=tree[now<<1].mid_num+tree[now<<1|1].mid_num;
}
void pushdown(long long now)
{
    tree[now<<1].lazy+=tree[now].lazy;
    tree[now<<1].mid_num+=tree[now].lazy;
    tree[now<<1].sum+=tree[now].lazy*tree[now<<1].l_num;
    tree[now<<1|1].lazy+=tree[now].lazy;
    tree[now<<1|1].mid_num+=tree[now].lazy;
    tree[now<<1|1].sum+=tree[now].lazy*tree[now<<1|1].l_num;
    tree[now].lazy=0;
}
void update_l(long long now,long long l,long long r,long long x,long long k)
{
    if(r<x||l>x) return;
    if(l==r)
    {
        tree[now].l_num+=k;
        tree[now].sum=tree[now].l_num*tree[now].mid_num;
        return;
    }
    pushdown(now);
    long long mid=(l+r)>>1;
    if(x<=mid) update_l(now<<1,l,mid,x,k);
    else update_l(now<<1|1,mid+1,r,x,k);
    pushup(now);
}
void update_mid(long long now,long long l,long long r,long long x,long long y,long long k)
{
    if(r<x||l>y) return;
    if(x<=l&&r<=y)
    {
        tree[now].mid_num+=k;
        tree[now].lazy+=k;
        tree[now].sum+=tree[now].l_num*k;
        return;
    }
    pushdown(now);
    long long mid=(l+r)>>1;
    if(x<=mid) update_mid(now<<1,l,mid,x,y,k);
    if(y>mid) update_mid(now<<1|1,mid+1,r,x,y,k);
    pushup(now);
}
long long query(long long now,long long l,long long r,long long x,long long y)
{
    if(r<x||l>y) return 0;
    if(x<=l&&r<=y) return tree[now].sum;
    pushdown(now);
    long long mid=(l+r)>>1,res=0;
    if(x<=mid) res+=query(now<<1,l,mid,x,y);
    if(y>mid) res+=query(now<<1|1,mid+1,r,x,y);
    return res;
}
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        pre[i]=where[num[i]];
        where[num[i]]=i;
    }
    long long ans=0;
    for(long long i=1;i<=n;i++)
    {
        if(pre[i])
        {
            update_l(1,1,n,pre[i],-1);
            update_mid(1,1,n,pre[pre[i]]+1,pre[i]-1,-1);
        }
        ans+=query(1,1,n,pre[i]+1,i-1);
        update_l(1,1,n,i,1);
        update_mid(1,1,n,pre[i]+1,i-1,1);
    }
    printf("%lld\n",ans);
}