CodeForces-1354 D Multiset重み線分ツリー/ツリー配列+二分

作り方1：線分ツリー

const int maxn=1e6+7;
const int INF=1e9;
const ll INFF=1e18;
int a[maxn],tree[maxn<<2],n,q,x,k;
void pu(int rt){tree[rt]=tree[rt<<1]+tree[rt<<1|1];}
void build(int rt,int l,int r)
{
    if (l==r)
    {
        tree[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pu(rt);
}
void update(int p,int rt,int l,int r)
{
    if (l==r)
    {
        tree[rt]++;a[l]++;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid)update(p,lson);
    else update(p,rson);
    pu(rt);
}
void solve(int rk,int rt,int l,int r)
{
    if (l==r)
    {
        tree[rt]--;a[l]--;
        return;
    }
    int mid=(l+r)>>1;
    if (rk<=tree[rt<<1])solve(rk,lson);// ， 
    else solve(rk-tree[rt<<1],rson);
    // ， （ ）
    pu(rt);
}
int main()
{
    scanf("%d%d",&n,&q);
    rep(i,1,n)scanf("%d",&x),a[x]++;
    build(1,1,n);
    while(q--)
    {
        scanf("%d",&k);
        if (k>0)update(k,1,1,n);
        else if (k<0)solve(-k,1,1,n);
    }
    if (!tree[1])W(0);
    else
    {
        rep(i,1,n)
            if (a[i]){W(i);return 0;}
    }
    return 0;
}

作り方2:ツリー配列

const int maxn=1e6+7;
const int INF=1e9;
const ll INFF=1e18;
int n,q,x,k,c[maxn];
int ask(int x){int ans=0;for (;x;x-=x&-x)ans+=c[x];return ans;}
void add(int x,int y){for (;x<=n;x+=x&-x)c[x]+=y;}
int main()
{
    scanf("%d%d",&n,&q);
    rep(i,1,n)scanf("%d",&x),add(x,1);
    while(q--)
    {
        scanf("%d",&k);
        if (k>0)add(k,1);
        else if (k<0)// -k 
        {
            int l=1,r=n;
            while(l<r)
            {
                int mid=(l+r)>>1;
                if (ask(mid)>=-k)r=mid;
                else l=mid+1;
            }
            add(l,-1);
        }
    }
    if (!ask(n))W(0);
    else
    {
        rep(i,1,n)
            if (ask(i)){W(i);break;}
    }
    return 0;
}