[codeforces217E]Alien DNA

万修为
2023-12-01

题目大意

给你一个字符串和n个操作,每个操作用li,ri表示:把当前字符串[li,ri]区间取出,把取出的字符串重新1–r-l+1编号,然后编号为奇数的按顺序写下来,再把编号为偶数的按顺序写下来,把得到的新字符串加在区间后面。

例如:
s1s2s3s4s5s6 l=2 r=4 操作后的字符串变成s1s2s3s4s3s2s4s5s6

最后输出前k个字符。

k≤3000000 n≤5000

分析

正着做显然很难,可以考虑倒过来做。
只考虑前k个位置。首先对于最后一个操作,如果r≥k,那么复制出来的区间一定不会被输出,就可以跳过了。
如果r < k,可以很容易求出复制出区间[r+1,2r-l+1]与区间[1,k]的交集。然后就把字符复制过来。假设交集长度为x,问题变成剩下n-1个操作对剩下k-x个位置进行复制了。

查询位置

现在问题在于:如何快速得出一个位置在当前[1,k]区间中的位置(因为区间中一些位置可能被占用了)。由于现在是倒过来做的,已经确定的位置不会被修改。
很显然最多复制k次,那么每次找位置用线段树,可用的位置赋值为1,被占用的为0即可。
时间复杂度 O(klogk)
有人3000000的线段树卡过去了。但是有另一种方法:
区间是连续的,假如我已经知道x在区间对应的位置了,现在要求x+1的位置,可以用并查集来跑。
现在问题就是如何确定第一个位置。假设当前做到第i个操作,把第i+1——n个操作覆盖的区间存下来,然后按位置从左到右顺序枚举一遍即可(注意一个操作可能被分成几部分,那么把它与把它分开的区间合并)。
时间复杂度 O(n2+kαk)

#include <cstdio> 
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=3000005,maxm=5005;

int n,m,tot,f[maxn],fa[maxn],l[maxm],r[maxm],X[maxm],Y[maxm],a[maxm],len,seq[maxn];

char S[maxn],c;

int get(int x)
{
    int l=1;
    seq[1]=x;
    for (;f[seq[l]];l++) seq[l+1]=f[seq[l]];
    for (int i=1;i<l;i++) f[seq[i]]=seq[l];
    return seq[l];
}

int getp(int x)
{
    if (!tot) return x;
    int i=1,last;
    if (x<X[a[i]]) return x;
    x-=X[a[i]]-1;
    for (last=i++;i<=tot;i++) if (X[a[i]]>Y[a[last]])
    {
        if (x>X[a[i]]-Y[a[last]]-1)
        {
            x-=X[a[i]]-Y[a[last]]-1;
            last=i;
        }else return Y[a[last]]+x;
    }
    return Y[a[last]]+x;
}

int main()
{
    //freopen("father.in","r",stdin); freopen("father.out","w",stdout);
    scanf("%s%d%d",S+1,&m,&n);
    for (int i=0;i<n;i++) scanf("%d%d",&l[i],&r[i]);
    memset(f,0,sizeof(f));
    memset(fa,0,sizeof(fa));
    for (int i=n-1;i>=0;i--) if (r[i]<m)
    {
        int p=getp(r[i]+1);
        if (p<=m)
        {
            int k=l[i]+1;
            if (k>r[i]) k=l[i];
            int P=getp(k),lim=(r[i]<<1)-l[i]+1,j;
            X[i]=p;
            for (j=r[i]+1;j<=lim && p<=m;j++,p=get(p))
            {
                fa[p]=P;
                f[p]=p+1;
                k+=2;
                if (k<=r[i]) P=get(get(P+1)+1);else
                {
                    k=l[i];
                    P=getp(k);
                }
                Y[i]=p;
            }
            for (j=tot;j && X[a[j]]>X[i];j--) a[j+1]=a[j];
            a[j+1]=i; tot++;
        }
    }
    int cnt=0;
    for (int i=1;i<=m;i++)
    {
        fa[i]=(!fa[i])?++cnt:fa[fa[i]];
        printf("%c",S[fa[i]]);
    }
    printf("\n");
    //fclose(stdin); fclose(stdout);
    return 0;
}
 类似资料:

相关阅读

相关文章

相关问答