| 记录编号 |
264148 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
[SDOI 2016 Round1] 生成魔咒 |
最终得分 |
100 |
| 用户昵称 |
 小一米 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.816 s |
| 提交时间 |
2016-05-27 20:06:23 |
内存使用 |
11.27 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define M 100003
#define LL long long
using namespace std;
int n,root;
int w[M],sa[M],rank[M],tmp[M],cnt[M],id[M],height[M],f[M][18];
LL ans;
struct Splay{int data,ch[2],fa,siz;}a[M];
struct disc{int data,id;}b[M];
bool cmp(disc x,disc y){return x.data<y.data;};
int in()
{
int t=0;char ch=getchar();
while (!isdigit(ch)) ch=getchar();
while (isdigit(ch)) t=(t<<1)+(t<<3)+ch-48,ch=getchar();
return t;
}
void SA(int len,int up)
{
int *rk=rank,*t=tmp,d=1,p=0;
for (int i=0;i<len;i++) cnt[rk[i]=w[i]]++;
for (int i=1;i<up;i++) cnt[i]+=cnt[i-1];
for (int i=len-1;i>=0;i--) sa[--cnt[rk[i]]]=i;
for (;;)
{
for (int i=len-d;i<len;i++) id[p++]=i;
for (int i=0;i<len;i++)
if (sa[i]>=d) id[p++]=sa[i]-d;
for (int i=0;i<up;i++) cnt[i]=0;
for (int i=0;i<len;i++) cnt[t[i]=rk[id[i]]]++;
for (int i=1;i<up;i++) cnt[i]+=cnt[i-1];
for (int i=len-1;i>=0;i--) sa[--cnt[t[i]]]=id[i];
swap(t,rk);
rk[sa[0]]=0;
p=1;
for (int i=0;i<len-1;i++)
if (sa[i]+d<len&&sa[i+1]+d<len&&t[sa[i]]==t[sa[i+1]]&&t[sa[i]+d]==t[sa[i+1]+d])
rk[sa[i+1]]=p-1;
else
rk[sa[i+1]]=p++;
if (p==len) return;
d<<=1;up=p;p=0;
}
}
void Height(int len)
{
for (int i=1;i<=len;i++) rank[sa[i]]=i;
int x,k=0;
for (int i=0;i<len;i++)
{
k=max(0,k-1);
x=sa[rank[i]-1];
while (w[x+k]==w[i+k]) k++;
height[rank[i]]=k;
}
}
int LCP(int a,int b)
{
if (a==b) return n-sa[a];
if (a>b) swap(a,b);
int t=log2(b-a);
return min(f[a+1][t],f[b+1-(1<<t)][t]);
}
void ct(int x){a[x].siz=a[a[x].ch[0]].siz+a[a[x].ch[1]].siz+1;}
void made(int id,int x){a[id].data=x;a[id].siz=1;}
void rorate(int x,bool mk)
{
int y=a[x].fa;
a[y].ch[!mk]=a[x].ch[mk];
a[a[x].ch[mk]].fa=y;
if (a[y].fa)
{
if (a[a[y].fa].ch[0]==y) a[a[y].fa].ch[0]=x;
else a[a[y].fa].ch[1]=x;
}
a[x].fa=a[y].fa;
a[y].fa=x;
a[x].ch[mk]=y;
ct(y);ct(x);
}
void splay(int x,int goal)
{
int y;
while (a[x].fa!=goal)
{
y=a[x].fa;
if (a[y].fa==goal)
{
if(a[y].ch[0]==x) rorate(x,1);
else rorate(x,0);
}
else if (a[a[y].fa].ch[0]==y)
{
if (a[y].ch[0]==x) rorate(y,1);
else rorate(x,0);
rorate(x,1);
}
else
{
if (a[y].ch[1]==x) rorate(y,0);
else rorate(x,1);
rorate(x,0);
}
}
if(!goal) root=x;
}
void insert(int id,int x)
{
made(id,x);
if (!root) {root=id;return;}
int now=root,f=1;
while (f)
{
a[now].siz++;
if (a[now].data<=x)
{
if (a[now].ch[1]) now=a[now].ch[1];
else f=0,a[now].ch[1]=id,a[id].fa=now;
}
else
{
if (a[now].ch[0]) now=a[now].ch[0];
else f=0,a[now].ch[0]=id,a[id].fa=now;
}
}
splay(id,0);
}
int find_next_max(int x)
{
int now=root,k=0;
while (now)
{
if (a[now].data>x)
k=(a[k].data>a[now].data||!k)?now:k,
now=a[now].ch[0];
else now=a[now].ch[1];
}
return k;
}
int find_next_min(int x)
{
int now=root,k=0;
while (now)
{
if (a[now].data<x)
k=(a[k].data<a[now].data||!k)?now:k,
now=a[now].ch[1];
else now=a[now].ch[0];
}
return k;
}
main()
{
freopen("menci_incantation.in","r",stdin);
freopen("menci_incantation.out","w",stdout);
n=in();
for (int i=0;i<n;i++) b[i].data=in(),b[i].id=i;
sort(b,b+n,cmp);
w[n-b[0].id-1]=1;
int p=2;
for (int i=1;i<n;i++)
if (b[i].data!=b[i-1].data) w[n-b[i].id-1]=p++;
else w[n-b[i].id-1]=p-1;
SA(n+1,p);
Height(n);
for (int i=1;i<=n;i++) f[i][0]=height[i];
for (int i=1;i<18;i++)
for (int j=1;j<=n-(1<<i-1);j++)
f[j][i]=min(f[j][i-1],f[j+(1<<i-1)][i-1]);
for (int i=0;i<n;i++)
{
ans+=i+1;
int x=find_next_min(rank[n-i-1]),y=find_next_max(rank[n-i-1]);
x=a[x].data;y=a[y].data;
if (y&&x>=1&&y<=n) ans+=LCP(x,y);
if(x>=1) ans-=LCP(x,rank[n-i-1]);
if (y&&y<=n) ans-=LCP(rank[n-i-1],y);
printf("%lld\n",ans);
insert(i+1,rank[n-i-1]);
}
}