洛谷 P13864 [SWERC 2020] Figurines

读题是难点

题意

有 \(N+1\) 个集合 \(S(0),S(1),\cdots,S(N)\)，满足 \(S(0)\) 为空集，\(S(N)\) 为空集，\(\forall 1\le i\le N,S(i)\) 均为 \(S(i-1)\) 增加和删除某些元素后得到。
现有 \(N\) 次询问，每次询问给出 \(d_i\)，有一个长为 \(n+1\) 的序列 \(x\)，\(x_0=0\)，\(\forall 0\le i <N,x_{i+1}=x_i+\sum_{y\in S(d_i)}[y\ge x_i]\)，求 \(x_n\)。

思路

了解题意后，我们发现需要维护两个东西，单点修改，求某个版本中大于等于给定数的数量。
由于每个版本均是从上一个版本更改来的，所以对于某一个版本内的数，也就是更改序列的某个"前缀和"。

于是可以使用主席树，每次修改会对一条链新开节点，查询直接找到对应版本求区间和就行了。

注意题目中没有对修改次数限制，不要误以为最多只有两次操作。（但是感觉不限制的话，每次也有可能至多开一整棵树？）
注意下标从 \(0\) 开始。
剩下就是板子了。时间复杂度 \(O(n\log n)\)。

参考代码

// Problem: P13864 [SWERC 2020] Figurines
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P13864
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,cnt,root[MAXN];
struct node{
    int cnt,lson,rson,id;
}tree[MAXN*50];

void pushup(int id){
    tree[id].cnt=tree[tree[id].lson].cnt+tree[tree[id].rson].cnt;
}

void build(int id,int l,int r){
    if(l==r) return;
    int mid=(l+r)>>1;
    tree[id].lson=++cnt;
    build(tree[id].lson,l,mid);
    tree[id].rson=++cnt;
    build(tree[id].rson,mid+1,r);
}

void update(int old,int now,int l,int r,int pos,int val){
    // cout<<old<<' '<<now<<' '<<l<<' '<<r<<' '<<pos<<' '<<val<<endl;
    if(l==r){
        tree[now].cnt+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid){
        if(tree[tree[now].lson].id!=tree[now].id){
            tree[now].lson=++cnt;
            tree[cnt]=tree[tree[old].lson];
            tree[cnt].id=tree[now].id;
        }
        update(tree[old].lson,tree[now].lson,l,mid,pos,val);
    }
    else{
        if(tree[tree[now].rson].id!=tree[now].id){
            tree[now].rson=++cnt;
            tree[cnt]=tree[tree[old].rson];
            tree[cnt].id=tree[now].id;
        }
        update(tree[old].rson,tree[now].rson,mid+1,r,pos,val);
    }
    pushup(now);
}

int query(int id,int l,int r,int L,int R){
    // cout<<id<<' '<<l<<' '<<r<<' '<<L<<" "<<R<<' '<<tree[id].cnt<<endl;
    if(id==0||r<L||R<l) return 0;
    if(L<=l&&r<=R) return tree[id].cnt;
    int mid=(l+r)>>1,res=0;
    if(L<=mid) res+=query(tree[id].lson,l,mid,L,R);
    if(R>mid) res+=query(tree[id].rson,mid+1,r,L,R);
    return res;
}

int read(){
    char ch=getchar();
    int f=0,x=0;
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
    return x;
}

signed main(){
    n=read();
    root[0]=++cnt;
    build(root[0],0,n-1);
    for(int i=1;i<=n;i++){
        char ch='#';
        root[i]=++cnt;
        tree[root[i]]=tree[root[i-1]];
        tree[cnt].id=i;
        while(ch!='\n'){
            ch=getchar();
            // cout<<ch;
            if(ch=='\n') break;
            if(ch=='+'){
                ch=getchar();
                // cout<<ch;
                int val=0;
                while(ch>='0'&&ch<='9'){
                    val=val*10+ch-'0';
                    ch=getchar();
                    // cout<<ch;
                }
                update(root[i-1],root[i],0,n-1,val,1);
            }
            else{
                ch=getchar();
                // cout<<ch;
                int val=0;
                while(ch>='0'&&ch<='9'){
                    val=val*10+ch-'0';
                    ch=getchar();
                    // cout<<ch;
                }
                update(root[i-1],root[i],0,n-1,val,-1);
            }
        }
    }
    int y=0;
    // for(int i=0;i<=n;i++){
        // for(int j=0;j<n;j++) cout<<query(root[i],0,n-1,j,j)<<' ';
        // cout<<endl;
    // }
    for(int i=1;i<=n;i++){
        int p=read();
        // cout<<p<<' '<<query(root[p],0,n-1,y,n-1)<<' ';
        (y+=query(root[p],0,n-1,y,n-1))%=n;
        // cout<<y<<endl;
    }
    cout<<y;
    return 0;
}