UOJ Logo kczno1的博客

博客

bzoj Kpm的MC密码 的dsu on the tree做法

2017-05-06 23:08:20 By kczno1

s是c的后缀,倒过来,s就是c的前缀。

之后建trie树,所有c就是s的子树。

所以问题就转化了求子树k大。

由于可以离线,所以可以把询问挂在节点上。

dfs一遍,用直接转移重儿子,暴力轻儿子的方法维护当前的权值线段树,时间O(nlog^2)。

有了权值线段树,询问时只用O(log)。

感觉会比主席树快,没试过。

加了fread,fwrite后拿了rank1

#include<bits/stdc++.h>

#define gc getchar()
int read()
{
    char ch;
    while((ch=gc)<'0');
    int x=ch-'0';
    while((ch=gc)>='0')x=x*10+ch-'0'; 
    return x;
}

const int N=100005,T=300005;
int dy[N],j;
int ch[T][26],tot=1;
int cnt[T],t[T],next[N];
int sz[T],dfn[T],out[T],q[N],son[T];
int k[N],ans[N];

int a[N*3],d;
void clear(int i)
{
    for(i+=d;i;i>>=1)--a[i];
}
void add(int i)
{
    for(i+=d;i;i>>=1)++a[i];
}
#define L (i<<1)
int qiu(int k)
{
    if(k>a[1]) return -1;
    int i=1;
    while(i<=d)
    if(k<=a[L])i=L;
    else { k-=a[L];i=L+1; }
    return i-d;
}

char s[T];int len;
int to(int &x)
{
    if(!x)x=++tot;
    return x;
}

void dfs(int x)
{
    dfn[x]=tot+1;
    int i,y;
    for(i=t[x];i;i=next[i]) q[++tot]=i;

    for(i=0;i<26;++i) 
    if(y=ch[x][i]) 
    {
        dfs(y);
        if(sz[y]>sz[son[x]]) son[x]=y;
    }

    sz[x]=(out[x]=tot)-dfn[x]+1;
}
void solve(int x)
{
    int i,y,c=son[x];
    if(sz[c])
    {
        for(i=0;i<26;++i)
        if((y=ch[x][i])!=c&&sz[y]) 
        {solve(y); 
         for(j=dfn[y];j<=out[y];++j) clear(q[j]);
        }
        solve(c);
        for(j=dfn[x];j<dfn[c];++j) add(q[j]);
        for(j=out[x];j>out[c];--j) add(q[j]);
    }
    else 
    for(j=dfn[x];j<=out[x];++j) add(q[j]);

    for(j=0;j<cnt[x];++j)
    {
        i=q[dfn[x]+j];
        ans[i]=qiu(k[i]);
    }
}

int main()
{

    int n=read(),i,now,x;
    for(i=1;i<=n;++i)
    {
        scanf("%s",s+1);len=strlen(s+1);
        now=1;
        for(j=len;j;--j) now=to(ch[now][s[j]-'a']);
        ++cnt[dy[i]=now];
        next[i]=t[now];t[now]=i;
    }
    for(i=1;i<=n;++i) k[i]=read();

    for(d=1;d<n;d*=2);d-=1;
    tot=0;
    dfs(1);
    solve(1);

    for(i=1;i<=n;++i) printf("%d\n",ans[i]);
}

评论

Alextokc
前排%

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。