# Bzoj5443 [ceoi2018]lottery

## 离线查询

Posted by yjjr's blog on September 21, 2018

# 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;
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;
}
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()
{
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;
}