luogu P6477 [NOI Online #2 提高组]子序列问题 |线段树

题目描述

给定一个长度为 \(n\) 的正整数序列 \(A_1\)?, \(A_2\)?, \(\cdots\), \(A_n\)。定义一个函数 \(f(l,r)\) 表示：序列中下标在 \([l,r]\) 范围内的子区间中，不同的整数个数。换句话说，\(f(l,r)\) 就是集合 \(\{A_l,A_{l+1},\cdots,A_r\}\) 的大小，这里的集合是不可重集，即集合中的元素互不相等。

现在，请你求出 \(\sum_{l=1}^n\sum_{r=l}^n (f(l,r))^2\)。由于答案可能很大，请输出答案对 109+710^9 +7109+7 取模的结果。

输入格式

第一行一个正整数 \(n\)，表示序列的长度。

第二行 \(n\) 个正整数，相邻两个正整数用空格隔开，表示序列 \(A_1\), \(A_2\), \(\cdots\), \(A_n\)?。

输出格式

仅一行一个非负整数，表示答案对 \(10^9+7\) 取模的结果。

线段树里存f(l,r),注意下不要爆精度就好了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define int long long
const int N=1e6+5,mod=1e9+7;
inline int read(){
    int x=0; char ch=getchar();
    while(ch<‘0‘||ch>‘9‘)ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48); ch=getchar();}
    return x;
}
int n,a[N],b[N];
#define ls p<<1
#define rs p<<1|1
#define mid ((l(p)+r(p))>>1)
struct Seg{
	int l,r,sum,add;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define sum(x) tree[x].sum
	#define add(x) tree[x].add
	#define len(x) (r(x)-l(x)+1)
}tree[N<<2];
void build(int p,int l,int r){
	l(p)=l,r(p)=r;
	if(l==r)return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
inline void pushdown(int p){
	sum(ls)+=add(p)*len(ls);
	sum(rs)+=add(p)*len(rs);
	sum(ls)%=mod;
	sum(rs)%=mod;
	add(ls)+=add(p);
	add(rs)+=add(p);
	add(ls)%=mod;
	add(rs)%=mod;
	add(p)=0;
}
void update(int p,int l,int r,int d){
	if(l(p)==r(p)){
		sum(p)=(sum(p)+len(p)*d)%mod;
		add(p)=(add(p)+d)%mod;
		return;
	}
	if(add(p))pushdown(p);
	if(l<=mid)update(ls,l,r,d);
	if(r>mid)update(rs,l,r,d);
	sum(p)=(sum(ls)+sum(rs))%mod;
}
int query(int p,int l,int r){
	if(l<=l(p)&&r(p)<=r)return sum(p);
	if(add(p))pushdown(p);
	int ans=0;
	if(l<=mid)ans+=query(ls,l,r);
	if(r>mid)ans=(ans+query(rs,l,r))%mod;
	return ans;	
}
int last[N];
signed main(){
	//freopen("sequence.in","r",stdin);
	//freopen("sequence.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)a[i]=b[i]=read();
	sort(b+1,b+1+n);
	int len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	build(1,1,n);
	ll op=0,ans=0;
	for(int l=n;l>=1;l--){
		if(last[a[l]]){
			op=(op+2*query(1,l,last[a[l]]-1)+(last[a[l]]-l))%mod;
			update(1,l,last[a[l]]-1,1);
		}
		else {
			op=(op+2*query(1,l,n)+(n-l+1))%mod;
			update(1,l,n,1);
		}
		last[a[l]]=l;
		ans=(ans+op)%mod;
	}
	cout<<ans<<endl;
}

luogu P6477 [NOI Online #2 提高组]子序列问题 |线段树

原文：https://www.cnblogs.com/naruto-mzx/p/12784245.html