【JZOJ5428】【NOIP2017提高A组集训10.27】查询

题目

给出一个长度为n的序列a[]

给出q组询问，每组询问形如\(<x,y>\)，求a序列的所有区间中，数字x的出现次数与数字y的出现次数相同的区间有多少个。

分析

我们可以维护一个前缀和sum，遇到x时加1，遇到y减1。

那么对于区间[l,r]，如果sum[r]-sum[l-1]=0，则这个区间合法。

我们可以用桶来求出\(<x,y>\)的合法区间个数。

于是我们\(O(N^3)\)预处理每一个\(<x,y>\)；

但是这显然会超时。

因为只有有x和y时位置才是有用的，

我们可以记录x和y所在的位置，这样就可以讲其中很多没用的位置压缩掉。

这样就是\(O(N^2)\)的时间复杂度

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
const int maxlongint=2147483647;
const int mo=1e9+7;
const int N=8005;
using namespace std;
map <int,int> g;
int tot,a[N],tub[N*2],n,m,d[N],ans[N][N],num,q[N][N/7],re[N];
int prt[20];
void read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=(q<<1)+(q<<3)+ch-'0';n=q*w;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
for(;x;x/=10) prt[++prt[0]]=x%10;
if(!prt[0]) prt[++prt[0]]=0;
for (;prt[0];putchar('0'+prt[prt[0]--]));
}
void pre()
{
ans[0][0]=n*(n+1)/2;
for(int i=1;i<=tot;i++)
{
int num=0;
for(int j=1;j<=n;j++)
if(a[j]==i) d[++num]=j;
d[num+1]=n+1;
for(int j=0,dt;j<=num;j++) dt=d[j+1]-d[j]-1,ans[i][0]+=dt*(dt+1)/2;
ans[0][i]=ans[i][0];
}
for(int i=1;i<=tot;i++)
{
ans[i][i]=n*(n+1)/2;
for(int j=i+1,sum;j<=tot;j++)
{
if(i==1 && j==19)
{
printf("");
}
sum=0;
int p=0,p1=0,mx;
if(q[i][p+1]>q[j][p1+1]) mx=q[j][++p1],sum--;
else mx=q[i][++p],sum++;
tub[n]=mx,ans[i][j]+=mx*(mx-1)/2;
while(p<q[i][0] || p1<q[j][0])
{
if(q[i][p+1]>q[j][p1+1])
{
p1++;
ans[i][j]+=(q[j][p1]-mx-1)*(q[j][p1]-mx)/2+(q[j][p1]-mx)*tub[n+sum];
tub[n+sum]+=q[j][p1]-mx;
sum--;
mx=q[j][p1];
}
else
{
p++;
ans[i][j]+=(q[i][p]-mx-1)*(q[i][p]-mx)/2+(q[i][p]-mx)*tub[n+sum];
tub[n+sum]+=q[i][p]-mx;
sum++;
mx=q[i][p];
}
}
ans[i][j]+=(n-mx+1)*tub[sum+n]+(n-mx+1)*(n-mx)/2;
ans[j][i]=ans[i][j];
p=0,p1=0,mx=0;
for(int k=-q[j][0];k<=q[i][0];k++) tub[k+n]=0;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(!g[a[i]]) g[a[i]]=++tot;
re[g[a[i]]]=a[i];
a[i]=g[a[i]];
q[a[i]][++q[a[i]][0]]=i;
}
for(int i=1;i<=tot;i++) q[i][q[i][0]+1]=n+1;
pre();
for(int x,y;m--;)
{
read(x),read(y);
x=g[x],y=g[y];
if(ans[x][y]==14576)
{
printf("");
}
printf("%d\n",ans[x][y]);
}
}