题解：P11807 [PA 2017] 抄作业

一道可持久化线段树加哈希题。

题意

有

m

个长度为

n

序列，给定第一个序列，之后的每一个序列都有上一个序列修改一位得来。最后将它们按字典序排列。

思路

首先想怎么比较两个排列。想到二分哈希，如果左半边的哈希值相等，就把范围缩小到右半边，反之。这其实就是一个线段树，每一个节点存一段区间内的哈希值。

把每一个序列都存下来显然不现实，而题目给出的又是单点修改，于是我们可以用可持久化线段树维护每一个序列。

然后你发现这题做完了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
//这里使用了双哈希，一个模1e9+7，一个自然溢出
unsigned long long n,m,p=1000000007,a[maxn],cnt,h[maxn],k=131,k1[maxn],k2[maxn],ans[maxn];
struct xxx
{
    unsigned long long s1,s2,ls,rs;
}t[maxn*23];//空间要开这么大(20-1+4=23)(血的教训)
void up(int num,int l,int r)
{
    t[num].s1=(t[t[num].ls].s1*k1[r-(l+r)/2]%p+t[t[num].rs].s1)%p;
    t[num].s2=t[t[num].ls].s2*k2[r-(l+r)/2]+t[t[num].rs].s2;
}
void build(int num,int l,int r)
{
    if(l==r)
    {
        t[num].s1=a[l];
        t[num].s2=a[l];
        return;
    }
    t[num].ls=++cnt;
    t[num].rs=++cnt;
    build(t[num].ls,l,(l+r)/2);
    build(t[num].rs,(l+r)/2+1,r);
    up(num,l,r);
}
void update(int num,int numm,int l,int r,int x)
{
    if(l==r)
    {
        t[num].s1=a[l];
        t[num].s2=a[l];
        return;
    }
    if(x<=(l+r)/2)
    {
        t[num].ls=++cnt;
        t[num].rs=t[numm].rs;
        update(t[num].ls,t[numm].ls,l,(l+r)/2,x);
    }
    else
    {
        t[num].ls=t[numm].ls;
        t[num].rs=++cnt;
        update(t[num].rs,t[numm].rs,(l+r)/2+1,r,x);
    }
    up(num,l,r);
}
bool query(int num,int numm,int l,int r)
{
    if(l==r)return t[num].s1<t[numm].s1;
    if(t[t[num].ls].s1==t[t[numm].ls].s1&&t[t[num].ls].s2==t[t[numm].ls].s2)
    return query(t[num].rs,t[numm].rs,(l+r)/2+1,r);
    return query(t[num].ls,t[numm].ls,l,(l+r)/2);
}
bool cmp(int x,int y)
{
    //相等就以编号为第二关键字排序
    if(t[h[x]].s1==t[h[y]].s1&&t[h[x]].s2==t[h[y]].s2)return x<y;
    return query(h[x],h[y],1,n);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    k1[0]=1;
    k2[0]=1;
    for(int i=1;i<=n;i++)
    {
        k1[i]=k1[i-1]*k%p;
        k2[i]=k2[i-1]*k;
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    h[1]=++cnt;
    build(h[1],1,n);
    for(int i=2;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x]=y;
        h[i]=++cnt;
        update(h[i],h[i-1],1,n,x);
    }
    for(int i=1;i<=m;i++)ans[i]=i;
    sort(ans+1,ans+m+1,cmp);//用一个sort就行了
    for(int i=1;i<=m;i++)cout<<ans[i]<<" ";
}

题解：P11807 [PA 2017] 抄作业

文章操作

题意

思路

代码

相关推荐

评论

题解：P11807 [PA 2017] 抄作业