Weight line segment tree + line segment tree split/merge + CF1659D

CF1659D Reverse Sort Sum

如果一个01数组A进行n次排序,第i次sort前i个,can be formed in the processn个序列,Add the correspondences of these sequences to form a new sequenceC.

现在给定C,Find the original sequence that meets the requirementsA

The context of the topic is rather special,There is a more ingenious construction method,Each location was analyzed1Contribution to before and after.

重要的一点是：如果这个位置是0,但是对应的cThe array has a value at this position,Then a conclusion should be drawn,next positionC[i]-1All positions are1.

#include <iostream>
#define endl '\n'
using namespace std;
const int N=2e5+100;
int a[N],b[N];
int main()
{
    
    int t;
    for(cin>>t;t;t--)
    {
    
        int n,p=0;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
            b[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
    
            if(p<i)
            {
    
                if(a[i])
                    b[i]=1;
                else
                    b[i]=0;
            }
            if(b[i]==1)
            {
    
                for(++p;p<=a[i];++p)
                    b[p]=1;
                b[p]=0;
            }
            else
            {
    
                for(++p;p<=a[i]+i-1;++p)
                    b[p]=1;
                b[p]=0;
            }
        }
        for(int i=1;i<=n;i++)
            cout<<b[i]<<" ";
        cout<<endl;
    }
    return 0;
}

P5494 【模板】线段树分裂

The understanding of the split operation is really not very thorough,Still need to ponder,Other aspects are common operations such as：动态开点,nA line segment tree or something,There are also some operations on the weight segment tree.

#include <bits/stdc++.h>
#define int long long
#define ls lson[rt]
#define rs rson[rt]
#define mid ((l+r)>>1)
#define endl '\n'
#define fastio cout.tie(0);cin.tie(0);ios::sync_with_stdio(0)
using namespace std;
const int N = 2e5+100;
int gra[N<<5],tree[N<<5],lson[N<<5],rson[N<<5],cnt,tot,root[N<<5],a[N],seq=1,n,m;
int new_node()
{
    
    return cnt?gra[cnt--]:++tot;
}
void del_node(int p)
{
    
    gra[++cnt]=p;
    tree[p]=0;lson[p]=0;rson[p]=0;
    return ;
}
void fix(int &rt,int l,int r,int num,int x)
{
    
    if(!rt)
        rt=new_node();
    tree[rt]+=x;
    if(l==r)
        return ;
    if(num<=mid)
        fix(ls,l,mid,num,x);
    else
        fix(rs,mid+1,r,num,x);
}
int query_num(int rt,int l,int r,int nl,int nr)
{
    
    if(l>nr||r<nl)
        return 0;
    if(nl<=l&&r<=nr)
        return tree[rt];
    return query_num(ls,l,mid,nl,nr)+query_num(rs,mid+1,r,nl,nr);
}
int query_kth(int rt,int l,int r,int num)
{
    
    if(l==r)
        return l;
    if(tree[ls]>=num)
        return query_kth(ls,l,mid,num);
    else
        return query_kth(rs,mid+1,r,num-tree[ls]);
}
int merge(int x,int y)
{
    
    if(!x||!y)
        return x+y;
    tree[x]+=tree[y];
    lson[x]=merge(lson[x],lson[y]);
    rson[x]=merge(rson[x],rson[y]);
    del_node(y);
    return x;
}
void split(int x,int &y,int k)
{
    
    if(x==0)
        return;
    y=new_node();
    int v=tree[lson[x]];
    if(k>v)
        split(rson[x],rson[y],k-v);
    else
        swap(rson[x],rson[y]);
    if(k<v)
        split(lson[x],lson[y],k);
    tree[y]=tree[x]-k;
    tree[x]=k;
    return ;
}
signed main()
{
    
    //fastio;
    cin>>n>>m;
    for(int i=1,temp;i<=n;i++)
    {
    
        cin>>temp;
        fix(root[1],1,n,i,temp);
    }
    for(int i=1,op,p,k,x,q,y,t;i<=m;i++)
    {
    
        cin>>op;
        if(op==0)
        {
    
            cin>>p>>x>>y;
            int k1=query_num(root[p],1,n,1,y);
            int k2=query_num(root[p],1,n,x,y);
            int temp=0;
            split(root[p],root[++seq],k1-k2);
            split(root[seq],temp,k2);
            root[p]=merge(root[p],temp);
        }
        if(op==1)
        {
    
            cin>>p>>t;
            root[p]=merge(root[p],root[t]);
        }
        if(op==2)
        {
    
            cin>>p>>x>>q;
            fix(root[p],1,n,q,x);
        }
        if(op==3)
        {
    
            cin>>p>>x>>y;
            cout<<query_num(root[p],1,n,x,y)<<endl;
        }
        if(op==4)
        {
    
            cin>>p>>k;
            if(tree[root[p]]<k)
            {
    
                cout<<-1<<endl;
                continue;
            }
            cout<<query_kth(root[p],1,n,k)<<endl;
        }
    }
	return 0;
}
/* 5 12 0 0 0 0 0 2 1 1 1 2 1 1 2 2 1 1 3 3 1 1 3 4 1 2 2 1 1 4 2 1 1 5 0 1 2 4 2 2 1 4 3 2 2 4 1 1 2 4 1 3 */

P3369 【模板】普通平衡树

权值线段树,What I understand is resettable segment trees.An unordered array is given,An ordered segment tree is constructed after several insertion operations,Each node represents how many values ​​this interval has,The leaf nodes represent the number of occurrences of each value.

常见的操作有：
离散化,动态开点,查询区间第k小/大,The number of query intervals,增加/删除x个点/数.

#include<bits/stdc++.h>
#define ls lson[rt]
#define rs rson[rt]
#define mid ((l+r)>>1)
using namespace std;
const int N = 1e7+100;
int m;
int lson[N<<2],rson[N<<2],tree[N<<2],cnt,root;
void up(int rt)
{
    
    tree[rt]=tree[ls]+tree[rs];
}
void fix(int &rt,int l,int r,int p,int v)
{
    
    if(!rt)
    {
    
        rt=++cnt;
    }
    if(l==r)
    {
    
        tree[rt]+=v;
        return ;
    }
    if(p<=mid)
        fix(ls,l,mid,p,v);
    if(p>mid)
        fix(rs,mid+1,r,p,v);
    up(rt);
}
int query_num(int rt,int l,int r,int pl,int pr)
{
    
    int ans=0;
    if(pl<=l&&r<=pr)
        return tree[rt];
    if(pl<=mid)
    ans+=query_num(ls,l,mid,pl,pr);
    if(pr>mid)
    ans+=query_num(rs,mid+1,r,pl,pr);
    return ans;
}
int query_kth(int rt,int l,int r,int k)
{
    
    if(l==r)
        return l;
    int s=tree[ls];
    if(k<=s)
    return query_kth(ls,l,mid,k);
    else
    return query_kth(rs,mid+1,r,k-s);
}
map<int,int> ma;
int main()
{
    
    scanf("%d",&m);
    while(m--)
    {
    
        int opt,x;scanf("%d%d",&opt,&x);
        if(opt==1)
        {
    
            fix(root,1,N*2,x+N,1);//The absolute value given in the title is less than or equal to1e7So here we need to move the negative value field to the positive number
            ma[x]++;
        }
        if(opt==2)
        {
    
            fix(root,1,N*2,x+N,-1);
            ma[x]--;
            if(ma[x]==0)
                ma.erase(x);
        }
        if(opt==3)
        {
    
            printf("%d\n",query_num(root,1,N*2,1,x+N-1)+1);
        }
        if(opt==4)
        {
    
            printf("%d\n",query_kth(root,1,N*2,x)-N);
        }
        if(opt==5)
            printf("%d\n",(--ma.lower_bound(x))->first);
        if(opt==6)
            printf("%d\n",(ma.upper_bound(x))->first);
    }
    return 0;
}