OI题解 - 序列(sequence) [NOI Online Round2] | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 序列(sequence) [NOI Online Round2]

发表于 分类于 Valine：

还是自己没有继续推导下去的问题……推到一半就放弃了

但是做法也略复杂了，把别人的做法写一下

# 题面

给定一个长度为 $n$ 的正整数序列 $A_1,A_2,\dots,A_n$。定义一个函数 $f(l,r)$ 表示：序列中下标在 $[l,r]$ 范围内的子区间中，不同的整数个数。

换句话说，$f(l,r)$ 就是集合 $\{A_l,A_{l+1},\dots,A_r\}$ 的 大小，这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出：

由于答案可能很大，请输出答案对 $(10^9+7)$ 取模的结果。

数据规模：$1\le n\le10^6$，$A_i\in[1,10^9]$。

# 解析

由于我们只是要求计算不同的数的数量，所以数的具体值并没有影响。所以先离散化一下方便一些。

对于这种统计所有区间 的问题，有一个比较常见的方法——从右往左枚举左端点 $l$，用数据结构维护 $r\in[l,n]$ 的相关数据。这样 $l$ 每次向左移动一次，都只需要在数据结构中加入 $r=l-1$ 的这种情况，保证了复杂度。

然后假如不是算 $f^2(l,r)$ 的和，而是 $f(l,r)$ 的和，那就非常简单——用线段树维护 $r\in[l,n]$ 的 $f(l,r)$。

查询时直接查询 $[l,n]$ 区间和；考虑修改：当 l-- 时，需要更新线段树，于是还要动态维护 las[x] 表示 $x$ 上一次出现的位置（初值设为 $n+1$），于是 $A_l$ 会对 $[l,las_{A_l}]$ 这段区间产生 $1$ 的贡献（区间加）。因为对于 $r\in[l,las_{A_l}]$，$[l+1,r]$ 中原本没有 $A_l$ 这个数，现在加上 $A_l$ 使得区间变为 $[l,r]$。

所以就是简单的线段树区间加、区间求和。

如何处理平方？假设一个区间里的数为 $\{A_l,A_{l+1},\dots,A_r\}$，考虑给这些数加上 $d$ 过后平方和变成什么：

可见我们维护区间的平方和 $\sum A_i^2$、区间和 $\sum A_i$ 就可以更新了。

# 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6,MOD=1e9+7;

inline int Add(const int &a,const int &b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(const int &a,const int &b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(const int &a,const int &b){return 1ll*a*b%MOD;}
int QPow(int a,int b){
    int ret=0;
    while(b){
        if(b&1) ret=Mul(ret,a);
        a=Mul(a,a);b>>=1;
    }
    return ret;
}

int n;
int num[N+3],las[N+3];
vector<int> uni;

struct SEGTREE{
    int sqsum[N*2+3],sum[N*2+3],add[N*2+3];
    inline int Index(int lef,int rig){return (lef+rig)|(lef!=rig);}
    void PushUp(int lef,int rig){
        int mid=(lef+rig)>>1;
        sum[Index(lef,rig)]=Add(sum[Index(lef,mid)],sum[Index(mid+1,rig)]);
        sqsum[Index(lef,rig)]=Add(sqsum[Index(lef,mid)],sqsum[Index(mid+1,rig)]);
    }
    void Update(int lef,int rig,int del){
        int u=Index(lef,rig),len=rig-lef+1;
        sqsum[u]=Add(sqsum[u],Mul(Mul(2,del),sum[u]));
        sqsum[u]=Add(sqsum[u],Mul(Mul(del,del),len));
        add[u]=Add(add[u],del);
        sum[u]=Add(sum[u],Mul(len,del));
    }
    void PushDown(int lef,int rig){
        int mid=(lef+rig)>>1,u=Index(lef,rig);
        if(!add[u]) return;
        Update(lef,mid,add[u]);
        Update(mid+1,rig,add[u]);
        add[u]=0;
    }
    void Modify(int lef,int rig,int Le,int Ri){
        if(Le<=lef && rig<=Ri){
            Update(lef,rig,1);
            return;
        }
        PushDown(lef,rig);
        int mid=(lef+rig)>>1;
        if(Le<=mid) Modify(lef,mid,Le,Ri);
        if(Ri>mid) Modify(mid+1,rig,Le,Ri);
        PushUp(lef,rig);
    }
    int SumUp(int lef,int rig,int Le,int Ri){
        if(Le<=lef && rig<=Ri) return sqsum[Index(lef,rig)];
        PushDown(lef,rig);
        int mid=(lef+rig)>>1,ret=0;
        if(Le<=mid) ret=Add(ret,SumUp(lef,mid,Le,Ri));
        if(Ri>mid) ret=Add(ret,SumUp(mid+1,rig,Le,Ri));
        return ret;
    }
}Se;

int RI(){
    int a=0,c=getchar();
    while(c<'0' || '9'<c) c=getchar();
    while('0'<=c && c<='9'){
        a=(a<<1)+(a<<3)+c-'0';
        c=getchar();
    }
    return a;
}
int main(){
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=RI();
    for(int i=1;i<=n;i++)
        uni.push_back(num[i]=RI());
    sort(uni.begin(),uni.end());
    uni.erase(unique(uni.begin(),uni.end()),uni.end());
    for(int i=1;i<=n;i++)
        num[i]=lower_bound(uni.begin(),uni.end(),num[i])-uni.begin()+1;
    for(int i=1;i<=(int)uni.size();i++)
        las[i]=n+1;
    int ans=0;
    for(int i=n;i>=1;i--){
        int lef=i,rig=las[num[i]]-1;
        las[num[i]]=i;
        Se.Modify(1,n,lef,rig);
        int res=Se.SumUp(1,n,i,n);
        ans=Add(ans,res);
    }
    printf("%d\n",ans);
    return 0;
}

THE END

Thanks for reading!