题解 P4062 【[Code+#1]Yazid 的新生舞会】

Limit · 2020-07-05 19:23:36 · 题解

Update on 7.7

被两个 \log 的做法吊打呢,被 \sf \color{black}{e}\color{red}{xz\alpha ng} 的三 \log 做法吊打呢,自闭了/kk.

题目大意

给出一个序列,询问又多少子串 [l,r] 满足出现次数最多的数出现了大于 \lfloor\frac{r-l+1}{2}\rfloor 次(其实就是问又多少子串有绝对众数).

分析

好像有一种高大上的分治做法,但是我不会.

考虑 a_i\in[0,1] 怎么做,因为对于每个子串最多只会有一个绝对众数,所以考虑计算 0 和 1 分别为绝对众数时的答案,相加就好了.

如果一个子串拥有绝对众数,那么必定有一个数出现的次数大于其他所有数出现的次数之和,那么将 a_i=p 的位置为 1,a_i\not=p 的位置为 -1(p 为腰计算贡献的数),就是要计算有多少子串的和大于 0.考虑再前缀和一下,问题就变成了找顺序对(i<j\land sum_i<sum_j)个数,这个东西就可以用树状数组(权值线段树,平衡树等数据结构轻松解决),然后您发现 a_i\leq 7 的部分也写完了.

时间复杂度 \mathcal{O}(kn\log n)(其中 k 为序列中不同数个数).

但是对于最大的数据其中不同数的个数有 n 种,显然不能这样搞了,考虑去优化这个方法.

假设序列 a 为 [1,1,2,3,2,1,3].

先枚举到 1,将等于 1 的位置在序列 b 中改为 1,其他地方改为 -1.

那么 b 为 [1,1,-1,-1,-1,1,-1].

计算一下前缀和.

计算顺序对个数为 $5$. 再枚举到 $2\dots

不难发现在序列 b 中会有很多连续的 -1,而且这些连续的 -1 的段数最多为 2n-2(和 n 同阶),并且在 b 中为 1 的位置的数量恰好为 n.

而且这些连续的 -1 在前缀和中为一段公差为 -1 的等差数列,既然是一段连续的数加入,那么自然可以想到在权值线段树上打标记.

那么比较麻烦的是这段数计算贡献.

假设中间这段数的前缀和为 sum_l,sum_{l+1},\dots,sum_{r-1},sum_r,那么对于这段数的贡献为 \sum\limits_{i=l}^{r}\sum\limits_{j=0}^{l-1}(sum_j<sum_i),其中把这段数为公差为 -1 的等差数列这个结论带入就变成了 \sum\limits_{i=0}^{r-l}\sum\limits_{j=0}^{l-1}(sum_j<sum_l-i),假设用一个 s 数组来记录 sum_{i\in[0,l-1]} 中每个数出现的次数,那么这个公式就变成了 \sum\limits_{i=0}^{r-l}[(r-l-i)s_{sum_l-1-i}]+(r-l+1)\sum\limits_{i=-\infty}^{sum_r-1}s_i.那么只需要在权值线段树上维护一个 \sum\limits_{i=l}^{r}(r-i+1)s_i,就可以很方便的计算了.

时间复杂度 \mathcal{O}(n\log n).

代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int MAXN=5e5+5;
int n,m;
inline int Read()
{
    int x(0),f(1);
    char c(getchar());
    while(c<'0'||'9'<c)
    {
        if(c=='-')
        {
            f=-1;
        }
        c=getchar();
    }
    while('0'<=c&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return f*x;
}
vector<int>place[MAXN];
struct LazyTag
{
    bool clean;//因为不可能每次都暴力清空整颗线段树,所以需要一个清空标记
    int add;
    inline void Clean()
    {
        clean=0;
        add=0;
    }
}for_make;
inline LazyTag MakeTag(int opt,int add=0)
{
    for_make.Clean();
    if(opt==0)
    {
        for_make.clean=1;
    }
    if(opt==1)
    {
        for_make.add=add;
    }
    return for_make;
}
struct SegmentTree
{
    int len;
    long long sum,sum_;//权值线段树上维护权值和以及取的数量从 len 依次减一的和
    LazyTag tag;
}sgt[MAXN*8];
#define LSON (now<<1)
#define RSON (now<<1|1)
#define MIDDLE ((left+right)>>1)
#define LEFT LSON,left,MIDDLE
#define RIGHT RSON,MIDDLE+1,right
#define NOW now_left,now_right
inline void PushUp(int now)
{
    sgt[now].sum=sgt[LSON].sum+sgt[RSON].sum;
    sgt[now].sum_=sgt[LSON].sum_+sgt[LSON].sum*sgt[RSON].len+sgt[RSON].sum_;//计算 sum_ 建议自己推一下式子
}
void Build(int now=1,int left=1,int right=n*2+10)
{
    sgt[now].len=right-left+1;
    if(left==right)
    {
        return;
    }
    Build(LEFT);
    Build(RIGHT);
}
inline void Down(LazyTag tag,int now)
{
    if(tag.clean)
    {
        sgt[now].sum=sgt[now].sum_=0;
        sgt[now].tag.Clean();//需要把懒标记也清空
        sgt[now].tag.clean=1;
    }
    if(tag.add)
    {
        sgt[now].tag.add+=tag.add;
        sgt[now].sum+=1ll*sgt[now].len*tag.add;
        sgt[now].sum_+=1ll*(sgt[now].len+1)*sgt[now].len/2*tag.add;//直接用等差数列求和公式即可
    }
}
inline void PushDown(int now)
{
    Down(sgt[now].tag,LSON);
    Down(sgt[now].tag,RSON);
    sgt[now].tag.Clean();
}
inline void CleanTree()
{
    Down(MakeTag(0),1);
}
void UpdataAdd(int now_left,int now_right,int add,int now=1,int left=1,int right=n*2+10)
{
    if(now_left<=left&&right<=now_right)
    {
        Down(MakeTag(1,add),now);
        return;
    }
    PushDown(now);
    if(now_left<=MIDDLE)
    {
        UpdataAdd(NOW,add,LEFT);
    }
    if(MIDDLE+1<=now_right)
    {
        UpdataAdd(NOW,add,RIGHT);
    }
    PushUp(now);
}
long long QuerySum(int now_left,int now_right,int now=1,int left=1,int right=n*2+10)
{
    if(now_left<=left&&right<=now_right)
    {
        return sgt[now].sum;
    }
    PushDown(now);
    long long result=0;
    if(now_left<=MIDDLE)
    {
        result=QuerySum(NOW,LEFT);
    }
    if(MIDDLE+1<=now_right)
    {
        result+=QuerySum(NOW,RIGHT);
    }
    return result;
}
long long QuerySum_(int now_left,int now_right,int now=1,int left=1,int right=n*2+10)
{
    if(now_left<=left&&right<=now_right)
    {

        return sgt[now].sum_+sgt[now].sum*(now_right-right);//在计算 sum_ 的时候需要适当加上一些 sum,建议自己画图推式子
    }
    PushDown(now);
    long long result=0;
    if(now_left<=MIDDLE)
    {
        result=QuerySum_(NOW,LEFT);
    }
    if(MIDDLE+1<=now_right)
    {
        result+=QuerySum_(NOW,RIGHT);
    }
    return result;
}
#undef LSON
#undef RSON
#undef MIDDLE
#undef LEFT
#undef RIGHT
#undef NOW
int main()
{
    int opt;
    scanf("%d%d",&n,&opt);
    REP(i,0,n-1)
    {
        place[i].push_back(0);
    }
    REP(i,1,n)
    {
        place[Read()].push_back(i);
    }
    REP(i,0,n-1)
    {
        place[i].push_back(n+1);
    }
    Build();
    int add_num=n+3;//建议在线段树中不要使用负下标,如果要使用在计算 middle 不能直接使用 (left+right)>>1,而是应该一直向下取整,即 left=-5,right=-2 时 middle 应该为 -4,而不是 -3
    long long answer=0;
    REP(i,0,n-1)
    {
        CleanTree();//清空权值线段树
        UpdataAdd(add_num+0,add_num+0,1);//不要忘记把 0 放入权值线段树
        int now=0;
        REP(j,1,place[i].size()-1)
        {
            if(place[i][j-1]+1!=place[i][j])
            {
                answer+=QuerySum_(add_num+now-(place[i][j]-place[i][j-1]-1),add_num+now-2)+1ll*(place[i][j]-place[i][j-1]-1)*QuerySum(1,add_num+now-(place[i][j]-place[i][j-1]-1)-1);//按上面给出的计算等差数列贡献的方法计算
                UpdataAdd(add_num+now-(place[i][j]-place[i][j-1]-1),add_num+now-1,1);//将这一整段数都放入权值线段树
                now-=(place[i][j]-place[i][j-1]-1);
            }
            if(place[i][j]!=n+1)
            {
                //在等于枚举的数的位置就直接计算贡献
                now++;
                answer+=QuerySum(1,add_num+now-1);
                UpdataAdd(add_num+now,add_num+now,1);
            }
        }
    }
    printf("%lld\n",answer);
    return 0;
}