P11390 题解

· · 题解

这道题还挺有意思，需要一步一步分析下来，最后才能发现正解算法。那我们可以来看点部分分想想正解是怎么来的。

子任务一

一个暴力就可以解决的问题。

具体的，我们枚举每一个区间，开一个 cnt 数组，记录每一个数字出现的次数。然后，我们记录恰好出现一次，两次，三次，四次的数字个数，一边扩大区间，一边统计即可。

for(int l=1;l<=n;l++){
    fill(cnt+1,cnt+n+1,0);
    cnt1=cnt2=cnt3=cnt4=0;
    for(int r=l,x;r<=n;r++){
        x=cnt[a[r]];
        if(x==0)cnt1++;
        else if(x==1)cnt1--,cnt2++;
        else if(x==2)cnt2--,cnt3++;
        else if(x==3)cnt3--,cnt4++;
        else if(x==4)cnt4--;
        cnt[a[r]]++;
        if(k>=1&&!cnt1)continue;
        if(k>=2&&!cnt2)continue;
        if(k>=3&&!cnt3)continue;
        if(k>=4&&!cnt4)continue;
        ans++;
    }
}

子任务二

我们可以凭借敏锐的直觉感受到合法区间的长度应该是 \frac {k\times (k+1)}{2}，为什么呢？我们知道一共只有 k 种数，而满足条件的话，区间中每一种数出现的次数显然不能相同，且分别是 1 到 k 次，然后相加即可。

那这部分可以使用一个双指针来解决。

//这部分的代码着实有点抽象了，有种复沓的美
len=k*(1+k)/2;
for(int i=1,x;i<=len;i++){
    x=cnt[a[i]];
    if(x==0)cnt1++;
    else if(x==1)cnt1--,cnt2++;
    else if(x==2)cnt2--,cnt3++;
    else if(x==3)cnt3--,cnt4++;
    else if(x==4)cnt4--;
    cnt[a[i]]++;
}
if(k==1&&cnt1)ans++;
else if(k==2&&cnt1&&cnt2)ans++;
else if(k==3&&cnt1&&cnt2&&cnt3)ans++;
else if(k==4&&cnt1&&cnt2&&cnt3&&cnt4)ans++;
for(int r=len+1,x;r<=n;r++){
    x=cnt[a[r-len]];
    if(x==1)cnt1--;
    else if(x==2)cnt2--,cnt1++;
    else if(x==3)cnt3--,cnt2++;
    else if(x==4)cnt4--,cnt3++;
    else if(x==5)cnt4++;
    cnt[a[r-len]]--;
    x=cnt[a[r]];
    if(x==0)cnt1++;
    else if(x==1)cnt1--,cnt2++;
    else if(x==2)cnt2--,cnt3++;
    else if(x==3)cnt3--,cnt4++;
    else if(x==4)cnt4--;
    cnt[a[r]]++;
    if(k==1&&cnt1)ans++;
    else if(k==2&&cnt1&&cnt2)ans++;
    else if(k==3&&cnt1&&cnt2&&cnt3)ans++;
    else if(k==4&&cnt1&&cnt2&&cnt3&&cnt4)ans++;
}
write(ans),Nxt;

子任务三

这是最核心的一个子任务，因为它直接提示了我们正解的做法。

我们考虑 k=1 的特殊情况，记录 f_i 表示 i 到当前右端点的区间中，有多少个恰好出现一次的数字。

那这就变成了一个区间加的问题了，具体的，我们记 pre_i 表示 a_i 这个值上一次出现的位置，那么对于 [pre_i+1,i] 的这一段区间，a_i 这个数显然从原来没有贡献到现在有贡献，区间加一，对于 [pre_{pre_i}+1,pre_i] 这一段区间，a_i 从有贡献到没有贡献，区间减一，那以 i 为右端点的合法区间就是 [1,i] 中有多少个不为 0 的位置。

这显然可以使用一个线段树进行优化。

/*线段树代码*/
struct Node{
    int mi,cnt;
    Node friend operator +(Node a,Node b){
        Node res;
        res.mi=min(a.mi,b.mi);
        res.cnt=0;
        if(res.mi==a.mi)res.cnt+=a.cnt;
        if(res.mi==b.mi)res.cnt+=b.cnt;
        return res;
    }
    Node operator +(const int &a)const{
        return {mi+a,cnt};
    }
};
struct Segment_tree{
    Node c[N<<2];
    int tag[N<<2];
    #define ls p<<1
    #define rs p<<1|1
    #define mid (l+r>>1)
    void pushup(int p){c[p]=c[ls]+c[rs];}
    void Tag(int p,int v){
        c[p]=c[p]+v;
        tag[p]+=v;
    }
    void pushdown(int p){
        if(!tag[p])return ;
        Tag(ls,tag[p]);
        Tag(rs,tag[p]);
        tag[p]=0;
    }
    void build(int p,int l,int r){
        if(l==r)return void(c[p]={0,1});
        build(ls,l,mid),build(rs,mid+1,r);
        pushup(p);
    }
    void change(int p,int l,int r,int L,int R,int v){
        if(L<=l&&r<=R)return Tag(p,v);
        pushdown(p);
        if(mid>=L)change(ls,l,mid,L,R,v);
        if(mid<R)change(rs,mid+1,r,L,R,v);
        pushup(p);
    }
    int query(){
        if(c[1].mi==0)return n-c[1].cnt;
        return n;
    }
}
/*主函数*/
for(int i=1;i<=n;i++){
    pre[i]=las[a[i]];
    las[a[i]]=i;
}
Set.build(1,1,n);
for(int i=1;i<=n;i++){
    Set.change(1,1,n,pre[i]+1,i,1);
    if(pre[i])Set.change(1,1,n,pre[pre[i]]+1,pre[i],-1);
    ans+=Set.query();
    //查询 1~n 中有多少个不为 0 的节点，和查询 1~i 中有多少个不为 0 的节点是等价的，因为 i+1~n 显然为 0
}
write(ans);

4.正解

我们回忆一下子任务三的求解过程，可以分为两步。第一步，区间修改；第二步，求有多少个不为 0 的位置。

看着着实有点眼熟。

这不是求矩形面积并的过程吗？

我们将右端点视作矩形的宽，左端点视作矩形的长，就可以很明显的发现这个结论。

我们沿着这个思路想下去，会发现这样一件事：最后的答案其实就是求区间中拥有恰好出现一次，两次，三次，四次的合法区间各自的矩形面积并求交的答案。

但是求交着实不太好求，所以我们做一点容斥，把交搞成多个并相减的形式即可。

/*线段树的代码和上面是一样的，这里就不放了*/
for(int st=1,tp;st<(1<<k);st++){
    Set.build(1,1,n);
    tp=(cnt[st]&1)?1:-1;//容斥原理，奇加偶减，cnt[st] 表示 st 在二进制下有几个 1
    for(int i=1,now;i<=n;i++){
        now=i;
        for(int j=0;j<k;j++){
            if(st&(1<<j)){
                Set.change(1,1,n,pre[now]+1,now,1);
                if(pre[pre[now]]<pre[now])Set.change(1,1,n,pre[pre[now]]+1,pre[now],-1);
            }
            now=pre[now];
            if(!now)break;
        }
        ans+=tp*(Set.query());
    }
}