[十二省联考2019]异或粽子——可持久化trie树+堆

谁借莪１个温暖的怀抱￠ 2022-01-05 15:11 156阅读 0赞

# 题目链接： #

[\[十二省联考2019\]异或粽子][2019]

求前$k$大异或区间，可以发现$k$比较小，我们考虑找出每个区间。

为了快速得到一个区间的异或和，将原序列做前缀异或和。

对于每个点作为右端点时，我们维护出与他异或起来最大的左端点并将这组信息用结构体存起来插入堆中。

那么最大值就是堆顶那组(假设右端点为$r$)，但考虑到次大值可能出自同一个右端点，所以在弹出堆顶后还需要将以$r$为右端点的次大值插入堆中。

那么如何求出以$r$为右端点的最大值和次大值？

我们对序列每个数为一个版本建可持久化$trie$树，那么最大值就是对于$\[1,r\]$版本(第一个版本插入的数为$a\[0\]$)求与一个数异或的最大值。

至于次大值，可以记录求最大值时的版本区间(设为$\[l,r\]$)及最大值所在序列(或版本)的位置(设为$mid$)，在弹出最大值那组信息的同时插入$\[l,mid-1\]$和$\[mid+1,r\]$两个区间，分别对这两个区间求最大值即可。

因为需要求具体位置，所以在插入时需要在当前版本插入的一条链的叶子节点记录插入数在原数组的下标，当查询$\[l,r\]$时，返回$r$版本对应叶子节点记录的信息即可。因为每个版本只插入一个数，所以每个叶子结点记录的就是对应权值的最后一个位置，也就可以保证$r$版本对应叶子节点记录的信息一定在$\[l,r\]$之间。

那么要求出前$k$大，只需要每次取出堆顶然后将堆顶查询区间分为两部分再插入堆中，重复$k$次即可。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int cnt;
    int root[500010];
    int n,k;
    ll ans;
    struct miku
    {
        int ls,rs,size,id;
    }tr[20000010];
    ll a[500010],x;
    void updata(int &rt,int pre,int dep,ll val,int num)
    {
        rt=++cnt;
        tr[rt].size=tr[pre].size+1;
        tr[rt].ls=tr[pre].ls;
        tr[rt].rs=tr[pre].rs;
        if(dep==0)
        {
            tr[rt].id=num;
            return ;
        }
        if(val&(1<<(dep-1)))
        {
            updata(tr[rt].rs,tr[pre].rs,dep-1,val,num);
        }
        else
        {
            updata(tr[rt].ls,tr[pre].ls,dep-1,val,num);
        }
    }
    int query(int x,int y,int dep,ll val)
    {
        if(dep==0)
        {
            return tr[y].id;
        }
        if(val&(1<<(dep-1)))
        {
            if(tr[tr[y].ls].size-tr[tr[x].ls].size>0)
            {
                return query(tr[x].ls,tr[y].ls,dep-1,val);
            }
            else
            {
                return query(tr[x].rs,tr[y].rs,dep-1,val);
            }
        }
        else
        {
            if(tr[tr[y].rs].size-tr[tr[x].rs].size>0)
            {
                return query(tr[x].rs,tr[y].rs,dep-1,val);
            }
            else
            {
                return query(tr[x].ls,tr[y].ls,dep-1,val);
            }
        }
    }
    struct lty
    {
        int l,r,mid,rt;
        ll val;
        lty(){}
        lty(int L,int R,int RT)
        {
            l=L,r=R,rt=RT;
            mid=query(root[l-1],root[r],32,a[rt]);
            val=a[rt]^a[mid-1];
        }
        bool operator <(lty a)const
        {
            return val<a.val;
        }
    };
    priority_queue<lty>q;
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&x);
            a[i]=a[i-1]^x;
        }
        for(int i=1;i<=n;i++)
        {
            updata(root[i],root[i-1],32,a[i-1],i);
        }
        for(int i=1;i<=n;i++)
        {
            q.push(lty(1,i,i));
        }
        while(k--&&!q.empty())
        {
            lty now=q.top();
            q.pop();
            ans+=now.val;
            if(now.mid>now.l)
            {
                q.push(lty(now.l,now.mid-1,now.rt));
            }
            if(now.mid<now.r)
            {
                q.push(lty(now.mid+1,now.r,now.rt));
            }
        }
        printf("%lld",ans);
    }

还有一种解决方法是记录以$r$为右端点的区间已经取了前$k$大，每次取出堆顶将堆顶记录的$k$加一，查询第$k+1$大的异或区间再插入堆中。这样每组只需要存三个信息相对于上一种方法常数较小。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<vector>
    #include<bitset>
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int cnt;
    int root[500010];
    int n,k;
    ll ans;
    struct miku
    {
    	int ls,rs,size;
    }tr[20000010];
    ll a[500010],x;
    void updata(int &rt,int pre,int dep,ll val)
    {
    	rt=++cnt;
    	tr[rt].size=tr[pre].size+1;
    	tr[rt].ls=tr[pre].ls;
    	tr[rt].rs=tr[pre].rs;
    	if(dep==0)
    	{
    		return ;
    	}
    	if(val&(1<<(dep-1)))
    	{
    		updata(tr[rt].rs,tr[pre].rs,dep-1,val);
    	}
    	else
    	{
    		updata(tr[rt].ls,tr[pre].ls,dep-1,val);
    	}
    }
    ll query(int rt,int dep,ll val,int k)
    {
    	if(dep==0)
    	{
    		return 0ll;
    	}
    	if(val&(1<<(dep-1)))
    	{
    		int res=tr[tr[rt].ls].size;
    		if(res>=k)
    		{
    			return query(tr[rt].ls,dep-1,val,k)+(1ll<<(dep-1));
    		}
    		else
    		{
    			return query(tr[rt].rs,dep-1,val,k-res);
    		}
    	}
    	else
    	{
    		int res=tr[tr[rt].rs].size;
    		if(res>=k)
    		{
    			return query(tr[rt].rs,dep-1,val,k)+(1ll<<(dep-1));
    		}
    		else
    		{
    			return query(tr[rt].ls,dep-1,val,k-res);
    		}
    	}
    }
    struct lty
    {
    	int k,rt;
    	ll val;
    	lty(){}
    	lty(int K,int RT)
    	{
    		k=K,rt=RT;
    		val=query(root[rt],32,a[rt],k);
    	}
    	bool operator <(lty a)const
    	{
    		return val<a.val;
    	}
    };
    priority_queue<lty>q;
    int main()
    {
    	scanf("%d%d",&n,&k);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%lld",&x);
    		a[i]=a[i-1]^x;
    	}
    	for(int i=1;i<=n;i++)
    	{
    		updata(root[i],root[i-1],32,a[i-1]);
    	}
    	for(int i=1;i<=n;i++)
    	{
    		q.push(lty(1,i));
    	}
    	while(k--&&!q.empty())
    	{
    		lty now=q.top();
    		q.pop();
    		ans+=now.val;
    		q.push(lty(now.k+1,now.rt));
    	}
    	printf("%lld",ans);
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10672825.html

[2019]: https://www.luogu.org/problemnew/show/P5283