P10863 [HBCPC2024] Enchanted 题解

Akiyama_mzk · 2024-08-12 15:05:10 · 题解

戳

题意

给定一个值域为 [1,30] 的序列，合并操作定义是使用两个相同的元素（设为 x）合并出一个值为 x+1 的元素，代价为 2^{x+1}，维护以下四种操作。

• 操作 1：求出区间 [l,r] 内的元素通过合并能得到的最大元素。

• 操作 2：将区间 [l,r] 之间的元素合并，直至任意元素互不相同，然后再加入一个值为 k 的元素，继续合并直至任意元素互不相同，求出加新元素后所有合并的代价之和。

• 操作 3：将第 x 个数的值改为 val。

• 操作 4：回到第 t 次操作。

算法

注意到 [1,30] 的值域，想到使用二进制维护合并，合并操作就像二进制加法内的进位，少了两个相同的元素，多出另一个元素。

因此，区间合并后的最大的元素就是区间和的最大二进制位，其他操作也可以照样用二进制维护。

对于操作 4 的回退和操作 3 的修改操作，我们使用可持久化线段树来维护。

但什么是可持久化？

下面内容请会可持久化线段树的大佬跳过。

我们需要先了解 P3919 【模板】可持久化线段树 1（可持久化数组）。

题面为在某个历史版本上修改某一个位置上的值，并访问某个历史版本上的某一位置的值。

可持久化线段树的基本思想就是只对进行修改的结点进行复制，以减少空间的消耗，让我们不必复制每个版本所有节点。

易得，每次添加的节点数为 \log(n) 个，可持久化线段树有很多根，对于每一个根都可以构成一棵完整的线段树。

所以我们知道，可持久化线段树只会对部分节点进行复制，我们每一次想询问一个版本的线段树，就可以在那个版本的根构成的线段树中询问。

我们直接开一块内存池存新节点。编号为此时总节点数个数 +1。开结构体存节点编号。根要另外开个数组存。

注意，可持久化线段树不能用 x\times 2，x\times 2+1 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。

代码如下。

int n,m,dfn;
int root[1000001],a[1000001];
struct president_tree{
    struct node{
        int lson,rson,val;
    }t[25000001];
    void build(int &x,int l,int r){
        x=++dfn;
        if(l==r){
            t[x].val=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(t[x].lson,l,mid);
        build(t[x].rson,mid+1,r);
    }
    void update(int idx,int &id,int l,int r,int x,int d){
        id=++dfn;
        t[id]=t[idx];
        if(l==r){
            t[id].val=d;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            update(t[idx].lson,t[id].lson,l,mid,x,d);   
        }
        else{
            update(t[idx].rson,t[id].rson,mid+1,r,x,d);
        }
    }
    int query(int x,int l,int r,int pos){
        if(l==r){
            return t[x].val;
        }
        int mid=(l+r)>>1;
        if(pos<=mid){
            return query(t[x].lson,l,mid,pos);
        }
        else{
            return query(t[x].rson,mid+1,r,pos);
        }
    }
}tree;

代码与评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline long long read(){
    long long x=0;
    short f=1;
    char c=getchar();
    while(c>57||c<48){
        if(c==45) f=-1;
        c=getchar();
    }
    while(c<58&&c>47){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(long long x){
    if(x<0ll) putchar(45),x=~x+1;
    if(x>9ll) write(x/10);
    putchar(x%10|48);
}
int n,m,dfn,a,p,q;
int root[4000001],cost[4000001];
struct president_tree{
    struct node{
        int lson,rson,val;
    }t[64000001];
    #define lson(x) t[x].lson
    #define rson(x) t[x].rson
    void push_up(int x){
        t[x].val=t[lson(x)].val+t[rson(x)].val;
    } 
    void build(int &x,int l,int r){
        x=++dfn;
        if(l==r){
            t[x].val=cost[l];
            return;
        }
        int mid=(l+r)>>1;
        build(t[x].lson,l,mid);
        build(t[x].rson,mid+1,r);
        push_up(x);
        return;
    }
    void update(int idx,int &id,int l,int r,int x,int d){
        id=++dfn;
        t[id]=t[idx];
        if(l==r){
            t[id].val=d;
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            update(t[idx].lson,t[id].lson,l,mid,x,d);   
        }
        else{
            update(t[idx].rson,t[id].rson,mid+1,r,x,d);
        }
        push_up(id);
    }
    int query(int x,int l,int r,int ll,int rr){
        if(ll<=l&&r<=rr){
            return t[x].val;
        }
        int mid=(l+r)>>1;
        int res=0;
        if(ll<=mid){
            res+=query(t[x].lson,l,mid,ll,rr);
        }
        if(rr>=mid+1){
            res+=query(t[x].rson,mid+1,r,ll,rr);
        }
        return res;
    }
}tree;
const int mod=1e9+7;
int cal(){
    a=(7ll*a+13)%19260817;
    return (a+19260817)%19260817;
}
signed main(){
    n=read();
    m=read();
    a=read();
    p=read();
    q=read();
    for(int i=1;i<=n;i++){
        cost[i]=cal()%q+1;
        cost[i]=(1ll<<cost[i]);
    }
    tree.build(root[0],1,n);
    for(int i=1;i<=m;i++){
        root[i]=root[i-1];
        int op=cal()%p+1;
        if(op==1){
            int l=cal()%n+1;
            int r=cal()%n+1;
            if(r<l){
                swap(l,r);
            }
            long long ans=tree.query(root[i],1,n,l,r);
            write(__lg(ans));
            printf("\n");
        }
        if(op==2){
            int l=cal()%n+1;
            int r=cal()%n+1;
            if(r<l){
                swap(l,r);
            }
            int k=cal()%q+1;
            int res=tree.query(root[i],1,n,l,r);
            int ans=0;
            for(int j=0;res;j++){
                if(j>=k){
                    if(res&1){
                        ans+=(1ll<<(j+1))%mod;
                        ans%=mod;
                    }
                    else{
                        break;
                    }
                }
                res>>=1;
            }
            write(ans);
            printf("\n");
        }
        if(op==3){
            int pos=cal()%n+1;
            int k=cal()%q+1;
            k=1ll<<k;
            tree.update(root[i-1],root[i],1,n,pos,k);
        }
        if(op==4){
            int loc=cal()%i;
            root[i]=root[loc];
        }
    }
    return 0;
}

record