XCPC Notes

Appearance

发布时间：2024-03-11

思想 ​

  • 适用范围：拓扑序不会发生改变的，如trie，线段树
  • 对于一棵树来讲，要建立一个新的路径
    • 若新节点在原来的版本中已经有了，则把原来版本的这个点复制过来；
    • 原来版本有的点但不在该路径上的点，就不需要新加一个点，直接将指针指向原来版本的点即可

trie树 ​

P4735 最大异或和 ​

题意：
给定一个非负数的序列长度为N,有M个操作

  • A x添加x到序列末尾,长度加1
  • Q l r x从[l,r]选择一个数p,使得 ap⊕ap+1⊕...⊕an⊕xa_p \oplus a_{p+1} \oplus...\oplus a_n \oplus x最大

思路：

  • 假定已经选择了一个p,则用前缀异或和可以优化成 Sp−1⊕Sn⊕xS_{p-1} \oplus S_n \oplus x
  • 很明显S[n]^x为定值，此时只需看S[p-1]
  • 再考虑一个问题：求最大异或对时，我们是将每个值都插入到01trie中，然后对于每一位每次寻找相反的路径
  • 假设没有左边界，我们只需用S[n]^x去找最大值即可
  • 考虑有左边界，我们可以对每棵树记录当前子树中的最大节点的标号，如果有最大标号>=l说明可以继续走，否则不能走
  • 注意：trie的一般写法不需要使用深搜，但是此题需要从子节点更新父节点，因此插入需要写深搜
cpp
const int N=600010,M=25*N;//每次新建一条路经(对应一个新的值)就会产生最多25个节点
int tr[M][2],max_id[M],idx,n,m,root[N],s[N];
void insert(int p,int q,int k,int i){//上一个版本，当前版本，二进制的第k位,在数组的第i位
    if(k<0){//边界
        max_id[q]=i;
        return;
    }
    int v=s[i]>>k&1;//当前位
    if(p)tr[q][v^1]=tr[p][v^1];
    tr[q][v]=++idx;
    insert(tr[p][v],tr[q][v],k-1,i);
    max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);
}
int find(int p,int val,int l){
    for(int i=23;i>=0;i--){
        int v=val>>i&1;
        if(max_id[tr[p][v^1]]>=l)p=tr[p][v^1];
        else p=tr[p][v];
    }
    return val^s[max_id[p]];
}
void solve(){   
    cin>>n>>m;
    root[0]=++idx;
    max_id[0]=-1;
    insert(0,root[0],23,0);
    for(int i=1,x;i<=n;i++){
        cin>>x;
        s[i]=s[i-1]^x;
        root[i]=++idx;
        insert(root[i-1],root[i],23,i);
    }
    while(m--){
        char op;
        int l,r,x;
        cin>>op;
        if(op=='A'){
            cin>>x;
            n++;
            s[n]=s[n-1]^x;
            root[n]=++idx;
            insert(root[n-1],root[n],23,n);
        }
        else{
            cin>>l>>r>>x;
            cout<<find(root[r-1],s[n]^x,l-1)<<"\n";
        }
    }
}

主席树(可持久化线段树) ​

  • 节点的l,r不再存边界而是用来存编号，查询和更改时边界作为参数下传
  • 由于线段树是一段的，每次修改的那一段在原版本都必定存在，因此可以直接将信息复制过来，只需要将要修改的点所在的区间(l,r其中一个)赋值一个新节点即可(即l,r总是一个变一个不变)
  • 因此每次修改只会增加logn个节点
  • 缺点：由于有多个版本，懒标记很难下传

MKTHNUM - K-th Number ​

给定一个序列，每次操作询问l,r内的第k大数

  • 离散化按值建树
  • 从左到右插入一个新值，建新版本
  • 每次询问[l,r]可以发现利用前缀和的思想,当前值域中，[l,r]的数量为版本r的数量-版本l-1的数量，因此可以两个版本同时下传计算
cpp
struct Node{
    int l,r,cnt;
} t[N<<5];
int idx;
vector<int> nums;
int find(int x){
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
void pushup(int p){
    t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;
}
int build(int l,int r){
    int p=++idx;
    if(l==r)return p;
    int mid=l+r>>1;
    t[p].l=build(l,mid),t[p].r=build(mid+1,r);
    pushup(p);
    return p;
}
int insert(int p,int l,int r,int x){
    int q=++idx;
    t[q]=t[p];
    if(l==r){
        t[q].cnt++;
        return q;
    }
    int mid=l+r>>1;
    if(x<=mid)t[q].l=insert(t[p].l,l,mid,x);
    else t[q].r=insert(t[p].r,mid+1,r,x);
    pushup(q);
    return q;
}
int query(int p,int q,int l,int r,int k){
    if(l==r)return l;
    int mid=l+r>>1;
    int cnt=t[t[q].l].cnt-t[t[p].l].cnt;
    if(k<=cnt)return query(t[p].l,t[q].l,l,mid,k);
    return query(t[p].r,t[q].r,mid+1,r,k-cnt);
}
int n,m,a[N],root[N];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    root[0]=build(0,nums.size()-1);
    for(int i=1;i<=n;i++){
        root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<nums[query(root[l-1],root[r],0,nums.size()-1,k)]<<"\n";
    }
}

Wenwei Lin · 2022 — 2025