題目
給出一個長度為n的序列a[]
給出q組詢問，每組詢問形如 <x,y> <script type="math/tex" id="MathJax-Element-13"> </script>，求a序列的所有區間中，數字x的出現次數與數字y的出現次數相同的區間有多少個。
資料範圍
1<=n<=8000,1<=q<=500000， 1<=x,y,a[i]<=109
題解
很容易想到，每次詢問的時候， O(n) 掃一遍，有一臨時變量t,碰到x,t加一，碰到y,t減一，看前面有多少個t等于現在的t，按照這個計算答案。
然而這樣做有個缺點：每一次都要 O(n) 掃一遍，其中有很多段t一樣的，其實可以不用跑這些沒有用的位置。
将x和y出現的位置找出來，排個序，然後做一遍。
總時間複雜度 O(n2) 。
蒟蒻有個問題，怎麼計算答案。
我們知道相鄰兩個位置之間的t是一樣的，是以隻要計算t=w（w為一個數）時的t的個數，即可得到答案。
代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 8010
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
struct note{
int to,next;
};note edge[N*10];
struct note1{
int d,w;
};note1 qu[N*2];
int a[N],a1[N],b[N];
int o[N],head[N],q1[N],q2[N];
int ans[N][N];
int i,j,k,l,r,l1,r1,n,q,sum,wz,last;
int cnt[N*2],bz[N*2],cn,CNT,c1,c2,tot;
int read(){
int res=,fh=;char ch;
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')fh=-,ch=getchar();
while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
return res*fh;
}
void write(int x){
if(x>)write(x/);
P(x%10+'0');
}
int calc(int n){return n*(n+)/;}
int calc1(int n){return n*(n-)/;}
void lb(int x,int y){edge[++tot].to=y;edge[tot].next=head[x];head[x]=tot;}
bool cmp(note1 x,note1 y){return x.d<y.d;}
int main(){
freopen("query.in","r",stdin);
freopen("query.out","w",stdout);
n=read(),q=read();
fo(i,,n)a[i]=read(),b[i]=a[i];
memcpy(a1,a,sizeof(a1));sort(b+,b+n+);cn=unique(b+,b+n+)-b-;
fo(i,,n){
a1[i]=lower_bound(b+,b+cn+,a1[i])-b;
o[a1[i]]=a[i];
}
fd(i,n,)lb(a1[i],i);
fo(i,,cn-)
fo(j,i+,cn){
c1=;
for(k=head[i];k;k=edge[k].next)
qu[++c1].d=edge[k].to,qu[c1].w=;
for(k=head[j];k;k=edge[k].next)
qu[++c1].d=edge[k].to,qu[c1].w=;
sort(qu+,qu+c1+,cmp);
CNT++;
bz[]=CNT;cnt[]=qu[].d;
qu[c1+].d=n+;
wz=;
ans[i][j]=calc1(qu[].d);
fo(k,,c1){
if(qu[k].w==)wz++;else wz--;
if(CNT!=bz[wz]){
bz[wz]=CNT;
cnt[wz]=;
}
ans[i][j]+=calc1(qu[k+].d-qu[k].d)+cnt[wz]*(qu[k+].d-qu[k].d);
cnt[wz]+=qu[k+].d-qu[k].d;
}
ans[j][i]=ans[i][j];
}
fo(i,,q){
l=read(),r=read();
l1=lower_bound(b+,b+cn+,l)-b;
r1=lower_bound(b+,b+cn+,r)-b;
if(o[l1]!=l)l=l1=;if(o[r1]!=r)r=r1=;
if((!l&&!r) ||(l1==r1)){
write(calc(n));P('\n');
continue;
}
if((!l&&r) || (!r&&l)){
sum=last=;
if(r)l1=r1;
for(k=head[l1];k;k=edge[k].next){
sum+=calc(edge[k].to--last);
last=edge[k].to;
}
sum+=calc(n-last);
write(sum);P('\n');
continue;
}
write(ans[l1][r1]);
P('\n');
}
return ;
}