Problem
Solution
首先考虑简化版问题： (sum sum f(l,r)) （去平方后统计）
-
固定右端点统计。
-
把对于 (f(l,r)) 的统计拆成每个位置对于对应的 (f(l,r)) 的贡献再进行求和。
一个位置对于对应的 (f(l,r)) 有贡献，当且仅当这个位置 (a_i) 在 ([l,r]) 之间是第一次出现。考虑一个位置 (i) 产生位置的区间有 ([l,r],l in [pre_i+1,i], r in [i,n])，其中 (pre_i) 表示上一次出现 (i) 这个位置上的数 (a_i) 的位置。
固定右端点统计：
假设我们已经统计以 (i-1) 为右端点的所有区间，即 (f(1,i-1),f(2,i-1),...,f(i-1,i-1))，且分别记为 (f_1,f_2,...,f_{i-1})。现在统计以 (i) 为右端点的区间，对于 (f(k,i),1 le k le i)，记做 (g_k)，可以发现对于 (pre_i < k le i)，有 (g_k = f_k+1)，而对于其他 (1 le k le pre_i)，有 (g_k=f_k)。最后 (ans += sum g_i)。可以用线段树维护区间和实现。
进一步的，我们求 (sum sum f^2(l,r))。同样用上述方法固定右端点统计，同样的 (f^2(k,i-1)) 记做 (f_k)，(f^2(k,i)) 记做 (g_k)。对于 (pre_i < k le i)，有 (g_k = (f_k+1)^2 = f^2_k + 2f_k + 1)。扩展到线段树上，我们要用维护一个平方和，同时要维护一个 sum 来辅助维护平方和。具体的， (sum (f_k+v)^2 = sum f^2_k + 2vsum f_k + sum v^2)。
综上，我们要枚举固定右端点，每次加入一个点线段树区间修改加区间查询，时间复杂度 (O(n log n))。
Code
Talk is cheap.Show me the code.
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
const int N = 1e6+7, mod = 1e9+7;
int n;
int a[N],pre[N],btmp[N];
struct SegmentTree {
int sum[N<<2], sqsum[N<<2], lazy[N<<2];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) {
sum[p] = (sum[ls(p)] + sum[rs(p)]) % mod;
sqsum[p] = (sqsum[ls(p)] + sqsum[rs(p)]) % mod;
}
inline void fl(int p,int l,int r,int k) {
lazy[p] += k;
sqsum[p] += (k*k*(r-l+1)%mod + 2*k*sum[p]%mod) % mod;
sum[p] += (k * (r-l+1)) % mod;
}
inline void push_down(int p,int l,int r) {
int mid = (l + r) >> 1;
fl(ls(p), l, mid, lazy[p]);
fl(rs(p), mid+1, r, lazy[p]);
lazy[p] = 0;
}
void update(int p,int l,int r,int nl,int nr,int k) {
if(nl<=l && r<=nr) {
fl(p, l, r, k); return ;
}
push_down(p,l,r);
int mid = (l + r) >> 1;
if(nl <= mid) update(ls(p), l, mid, nl, nr, k);
if(nr > mid) update(rs(p), mid+1, r, nl, nr, k);
push_up(p);
}
int AskSum() {
return sqsum[1];
}
}T;
signed main()
{
n = read();
for(int i=1;i<=n;++i) btmp[i] = a[i] = read();
sort(btmp+1, btmp+1+n);
int ntmp = unique(btmp+1, btmp+1+n) - btmp - 1;
for(int i=1;i<=n;++i) a[i] = lower_bound(btmp+1, btmp+1+ntmp, a[i]) - btmp;
int ans = 0;
for(int i=1;i<=n;++i) {
T.update(1,1,n,pre[a[i]]+1,i,1);
ans = (ans + T.AskSum()) % mod;
pre[a[i]] = i;
}
printf("%lld
",ans);
return 0;
}
/*
4
2 1 3 2
43
*/
Summary
-
对于每个点分别计算贡献的思想
-
固定端点枚举的思想
-
线段树维护平方和