比赛的时候一直往离线+数据结构上想 sigh,不过最后正解中也的确带有 "离线处理"
---------------------------------------------------------------------------------------------------------------------------------
首先我们可以很明显地发现 区间个数是$nq$级别的 所以莫队什么的还不如直接暴力
然后 我们还可以估计得出最后的答案是可以爆$int$的 所以直接去对每个位置算贡献也是不可行的
但是算贡献的这种思路并没有错 因为我们多想想就会发现 把一些边界情况处理了后
每个位置的贡献实际上就是一个连续的区间 (从长度为$L1$的字串到长度为$L2$的子串)
然后这里区间的话 由于每个长度的我们都需要求出来 (递推地求) 所以并不需要什么数据结构 直接前缀和就好了
---------------------------------------------------------------------------------------------------------------------------------
我使用的递推公式为
$f[i]=f[i-1]-cnt[i-1]+(n-i+1)-sum[i]$
$f[i]$即为长度为$i$的子串的答案
$cnt[i]$为最后一个子串的贡献(长度+1后 最后一个子串由于右端点无法向右扩展 就不合法了)
$(n-i+1)$就是之前的长度+1还合法的子串在理想情况下的贡献
$sum[i]$则是由于某些数可能在一个子串中出现多次 所以贡献要减掉
求$sum$可以根据每个数左边最近的一个相同的数的位置预处理出来
(从某处开始有+1的贡献 到某处结束时再有-1的贡献 其实也就是对整个区间有贡献)
---------------------------------------------------------------------------------------------------------------------------------
由于多处压了空间($f$数组以及$cnt$数组) 代码可能并不方便看
#include <bits/stdc++.h> using namespace std; const int N=1000010; struct que { int num,ask; long long ans; }ques[10010]; bool cmp1(const que &aa,const que &bb) { return aa.ask<bb.ask; } bool cmp2(const que &aa,const que &bb) { return aa.num<bb.num; } int num[N],la[N],sum[N]; bool used[N]; int n,q; int main() { int cnt,lacnt; while(scanf("%d",&n),n) { for(int i=1;i<=n;++i) sum[i]=0; for(int i=1;i<=n;++i) { scanf("%d",&num[i]); if(la[num[i]]) { ++sum[i-la[num[i]]+1]; --sum[i+1]; } la[num[i]]=i; } cnt=0; scanf("%d",&q); for(int i=1;i<=q;++i) { ques[i].num=i; scanf("%d",&ques[i].ask); ques[i].ans=0; } sort(ques+1,ques+1+q,cmp1); long long f,laf=0; int itail=1; while(ques[itail].ask==0&&itail<=q) ++itail; for(int i=1;i<=n;++i) { lacnt=cnt; if(!used[num[n-i+1]]) { used[num[n-i+1]]=true; cnt=lacnt+1; } else cnt=lacnt; sum[i+1]+=sum[i]; f=laf-lacnt+(n-i+1)-sum[i]; while(itail<=q&&ques[itail].ask==i) { ques[itail].ans=f; ++itail; } if(itail>q) break; laf=f; } sort(ques+1,ques+1+q,cmp2); for(int i=1;i<=q;++i) printf("%lld ",ques[i].ans); for(int i=1;i<=n;++i) { la[num[i]]=0; used[num[i]]=false; } } return 0; }
还有一个java版本的 不过一开始MLE 压了空间后还TLE
import java.io.*; import java.math.*; import java.util.*; import java.text.*; public class Main { final static int N=1000010; static class que { int num,ask; long ans; } static class cmp1 implements Comparator <que> { public int compare(que aa,que bb) { return aa.ask-bb.ask; } } static class cmp2 implements Comparator <que> { public int compare(que aa,que bb) { return aa.num-bb.num; } } public static void main(String args[]) { Scanner cin=new Scanner(new BufferedInputStream(System.in)); int num[]=new int[N]; int la[]=new int[N]; int sum[]=new int[N]; boolean used[]=new boolean[N]; que[] ques=new que[10010]; for(int i=1;i<=10000;++i) ques[i]=new que(); int n,q,cnt,lacnt; n=cin.nextInt(); while(n!=0) { for(int i=1;i<=n;++i) sum[i]=0; for(int i=1;i<=n;++i) { num[i]=cin.nextInt(); if(la[num[i]]!=0) { ++sum[i-la[num[i]]+1]; --sum[i+1]; } la[num[i]]=i; } cnt=0; q=cin.nextInt(); for(int i=1;i<=q;++i) { ques[i].num=i; ques[i].ask=cin.nextInt(); ques[i].ans=0; } Arrays.sort(ques,1,q,new cmp1()); long f,laf=0; int itail=1; while(ques[itail].ask==0&&itail<=q) ++itail; for(int i=1;i<=n;++i) { lacnt=cnt; if(!used[num[n-i+1]]) { used[num[n-i+1]]=true; cnt=lacnt+1; } else cnt=lacnt; sum[i+1]+=sum[i]; f=laf-lacnt+(n-i+1)-sum[i]; while(itail<=q&&ques[itail].ask==i) { ques[itail].ans=f; ++itail; } if(itail>q) break; laf=f; } Arrays.sort(ques,1,q,new cmp2()); for(int i=1;i<=q;++i) System.out.println(ques[i].ans); for(int i=1;i<=n;++i) { la[num[i]]=0; used[num[i]]=false; } n=cin.nextInt(); } } }