之前也想到了利用前缀数组，记录每一位的0~i的值，但是这样效率并不高。
题解的方法是每出现一次这个数字，记录一下下标，然后通过求区间的交，这样优化就不会超时了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<queue> #include<map> #include<cmath> #include<set> #include<stack> #define ll long long #define pb push_back #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) #define cls(name,x) memset(name,x,sizeof(name))//0或-1 #define fs first #define sc second #define mp make_pair #define L(x) (1<<x) using namespace std; const int inf=1e9+10; const ll llinf=1e16+10; const int maxn=8e3+10; const int maxm=2e5+10; const int mod=1e9+7; int n,q; int ans[maxn][maxn]; vector<int> v[maxn]; map<int,int> mapp; int main() { //freopen("in.txt","r",stdin); cls(ans,-1); scanf("%d %d",&n,&q); for(int i=1;i<=n;i++) v[i].pb(0); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); if(mapp[t]==0) mapp[t]=i; v[mapp[t]].pb(i); } map<int,int> c; while(q--) { int x,y; scanf("%d %d",&x,&y); if(ans[mapp[x]][mapp[y]]!=-1) { printf("%d ",ans[mapp[x]][mapp[y]]); continue; } if(x==y||(mapp[x]==0&&mapp[y]==0)) { ans[mapp[x]][mapp[y]]=n*(n+1)/2; } else if(mapp[x]==0||mapp[y]==0) { int t=(mapp[x]!=0?mapp[x]:mapp[y]); int sum=0,len; for(int i=1;i<v[t].size();i++) { int len=v[t][i]-v[t][i-1]-1; sum+=len*(len+1)/2; } len=n-v[t][v[t].size()-1]; sum+=len*(len+1)/2; ans[mapp[x]][mapp[y]]=sum; } else { c.clear(); int sum=0; int t1=mapp[x],t2=mapp[y]; /*for(int i=0;i<v[t1].size();i++) printf("%d ",v[t1][i]); printf(" "); for(int i=0;i<v[t2].size();i++) printf("%d ",v[t2][i]); printf(" ");*/ int xl,xr,idx1=0; int yl,yr,idx2=0; while(idx1<v[t1].size()&&idx2<v[t2].size()) { xl=v[t1][idx1]; if(idx1+1>=v[t1].size()) xr=n; else xr=v[t1][idx1+1]-1; yl=v[t2][idx2]; if(idx2+1>=v[t2].size()) yr=n; else yr=v[t2][idx2+1]-1; //printf("[%d %d:%d] [%d %d:%d] ",xl,xr,idx1,yl,yr,idx2); int len=(min(xr,yr)-max(xl,yl)+1); sum+=c[idx1-idx2]*len+len*(len-1)/2; c[idx1-idx2]+=len; if(xr<yr) idx1++; else if(xr>yr) idx2++; else {idx1++;idx2++;} } ans[mapp[x]][mapp[y]]=sum; } printf("%d ",ans[mapp[x]][mapp[y]]); } return 0; }