思路

我们不难发现，当区间中没有重复的点很好求，但如果中间部分产生重复的点，他们所产生的贡献会减少。

正着推不好推，那就反着来。

我们可以考虑计算当区间长度确定时，每个区间内每个元素是否出现过。

我们可以发现，当我们把区间内的相同元素单独拎出来（下文称为 \(i\)），如果存在一个区间在他们中间，那这个区间的内肯定不包含 \(i\) 这个元素，所以，我们只需把这几个不包含 \(i\) 元素的区间的长度减一就可以了。

但如果所有的区间长度都去减，时间复杂度会很高，这提醒我们可以考虑差分来记录，后面再做一次后缀和即可统计当前位置会比下一个位置减少的数量。

为什么会是这样？

我们可以考虑统计一遍过后，当前位置 \(k\) 仅代表第 \(k\) 位的位置会相较于第 \(k+1\) 位所统计的值大多少。
如果想要统计答案，再进行一次后缀和即可。

Code

#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {using namespace std;inline ll read() {char x=getchar();ll ans=0,f=1;while(x<'0'||x>'9') {if(x=='-') {f*=(-1);}x=getchar();}while(x>='0'&&x<='9') {ans*=10;ans+=(x-'0');x=getchar();}return ans*f;}inline void print(ll x) {if(x<0) {putchar('-');x=-x;}if(x>=10) {print(x/10);putchar(x%10+'0');}else {putchar(x+'0');}}
}
using namespace io;
const ll N=2e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll n,a[N],b[N],ans[N],cnt,vis[N],lt[N],num[N];
bool bis[N];
inline void solve() {n=read();for(ll i=1;i<=n;i++) {b[i]=a[i]=read();}sort(b+1,b+1+n);ll m=unique(b+1,b+1+n)-b-1;for(ll i=1;i<=n;i++) {a[i]=lower_bound(b+1,b+1+m,a[i])-b;}for(ll i=1;i<=n;i++) {lt[i]=vis[a[i]];vis[a[i]]=i;ans[i-lt[i]-1]++;if(!bis[a[i]]) {num[++cnt]=a[i];bis[a[i]]=1;}}for(ll i=1;i<=cnt;i++) {ans[n-vis[num[i]]]++;}for(ll i=n;i>=1;i--) {ans[i]+=ans[i+1];}for(ll i=n;i>=1;i--) {ans[i]+=ans[i+1];}for(ll i=1;i<=n;i++) {print(cnt*(n-i+1)-ans[i]);putchar(' ');}
}
praise_long_long main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);ll T=1;
//	T=read();while(T--) {solve();}return 0;
}
/**/

P9785 [ROIR 2020] 对常规的斗争 (Day1) 题解

思路

Code