BZOJ5443 [Ceoi2018]Lottery

标签：离线标记，递推

题目

题目传送门

题意简述：定义两个序列每个位置上不同的值的个数为$k$相似。现在有一个长度为$n$的序列，可以将它划分为$n?L+1$个长度为$L$的子串，$Q$组询问，求每个子串与多少个其它的子串为$\le k_i$相似的

题解

离线存储询问+普通转移+前缀和

code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define rep(i,a,b) for(int i=a;i<=b;i++) #define dep(i,a,b) for(int i=a;i>=b;i--) #define ll long long #define mem(x,num) memset(x,num,sizeof x) #define reg(x) for(int i=last[x];i;i=e[i].next) using namespace std; inline ll read(){
     ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } //**********head by yjjr********** const int maxn=1e4+6; int n,l,q,a[maxn],k[105]; short b[maxn],c[maxn],p[105],ans[105][maxn]; inline bool cmp(int x,int y){
     return k[x]<k[y];}int main() {
     n=read(),l=read();rep(i,1,n)a[i]=read();q=read();rep(i,1,q)k[i]=read(),p[i]=i;sort(p+1,p+1+q,cmp);dep(i,q,1)c[k[p[i]]]=i,k[p[i]]=i;c[l+1]=q+1;dep(i,l,0)if(!c[i])c[i]=c[i+1];rep(d,1,n-1){
     rep(i,1,n)b[i]=0;for(int i=1,j=d+1;j<=n;i++,j++)if(a[i]!=a[j])b[max(1,i-l+1)]++,b[i+1]--;rep(i,1,n-l+1-d)b[i]+=b[i-1],ans[c[b[i]]][i]++,ans[c[b[i]]][i+d]++;}rep(i,1,q)rep(j,1,n-l+1)ans[i][j]+=ans[i-1][j];rep(i,1,q){
     rep(j,1,n-l+1)printf("%d ",ans[k[i]][j]);puts("");}return 0; }