• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【题解】[ZJOI2013] K大数查询

开发技术 开发技术 4小时前 1次浏览

题目描述

(Luogu P3332)

给定一个含有(n)个数的序列(a_1,a_2 dots a_n),需要支持两种操作:

1 l r c 表示将 (c) 加入到编号在 ([l,r]) 内的集合中
2 l r c 表示查询编号在 ([l,r]) 内的集合的并集中,第 (c) 大的数是多少。

输入格式

第一行两个正整数 (n,m) ,表示序列长度与操作个数;
第二行 (n) 个整数,表示 (a_1,a_2 dots a_n)
接下来 (m) 行,每行表示一个操作,都为上述两种中的一个。

输出格式

对于每个 (2) 操作,输出一行一个整数表示答案。

数据范围

(
begin{aligned}
&1 le n, m le 5times 10^4\
&1le l,r le n\
&1 操作中 |c|le n\
&2 操作中 1le c<2^{63}
end{aligned}
)

解题思路

你看,它有一个序列,所以可以用线段树维护;你又看,每个元素都是一堆数,所以可以用权值线段树维护;综上所述,这题可以用线段树套权值树。

(前置知识1 & 前置知识2)

但是后来我看题解,里面基本上都是用权值树套线段树或者整体二分(但是由于这题两人合作调了7+hour,所以发一个题解纪念一下。
不管怎么说,讲一讲区间套权值的做法:

【题解】[ZJOI2013] K大数查询

算法流程

首先,内层权值线段树是每个节点都开一个,记录的是该位置上的每个数出现了多少次。外层线段树直接建就行了。

  • 对于操作1,直接在外层树上区间修改,把需要修改的内层树都在位置 (c)(+1)。需要注意的是,这里需要用到标记永久化,所以每个节点需要开两颗树,分别记录该区间的 (val)(tag)
    写法和普通线段树一样,就是把所有更改操作换成内层树的modify。

    详情见上图和文末代码。

  • 对于操作2,首先在外层树上跑一下,找出所有涉及到的区间,把这些区间里的树的根拎出来。再把可能影响到这些区间的所有tag树也拎出来。由于每个树的范围是相同的(值域),所以我们可以带着这些树一起进行线段树上二分,进行常规的权值树操作。

    但是有一个小问题:时间复杂度。对于每一个区间,会影响到它的tag有 (log n) 个,而这样的区间我们会找到 (log n) 个,又由于一次线段树上二分操作复杂度本身是 (O(log n)),所以这样做的总复杂度是 (O(nlog^3n))。在5e4的数据范围以及我人菜自带的大常数下,这个有一点危。你想,Floyd在 (n=100) 时复杂度都爆炸了,更别 (n=5e4) 时的 (O(nlog^3n)) 了(

    如何优化?我们发现,虽然节点很多,但是有大量的tag会被重新计算,所以我们可以在预处理时顺便记录一下每个tag会被加多少次。因为涉及到的tag数量是 (log) 的,我们的时间复杂度可以降到 (O(nlog^2n)),对数据友好。

    详情见文末代码。

代码

奉上我面向对象写法的带指针的常数巨大的但是能AC的代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,maxx;
set<int> num;
map<int,int> no;
map<int,int> on;

template<typename T,bool has_tag>
class SegmentTree // 线段树的基类
{
 protected:
    template<typename T_,bool htg>
    struct _Node
    {
        T_ val,tag;
        _Node *lc,*rc;
        _Node(): val(),tag()
            { lc=rc=NULL; }
    };
    template<typename T_>
    struct _Node<T_,false> // 对不用tag的进行特化,节省空间
    {
        T_ val;
        _Node *lc,*rc;
        _Node(): val()
            { lc=rc=NULL; }
    };
    typedef _Node<T,has_tag> Node;
    typedef _Node<T,has_tag> *pNode;
    pNode rt; // 根
    int sizn; // 线段树维护的区间大小
 public:
    SegmentTree(int s=0): rt(NULL)
        { sizn=s; }
    inline void setSize(int s)
        { sizn=s; }
};

class WeightTree: public SegmentTree<LL,false> // 内层权值线段树
{
 protected:
    inline void pushup(pNode &i) // 向上更新
    {
        i->val=0;
        if(i->lc) i->val+=i->lc->val;
        if(i->rc) i->val+=i->rc->val;
    }
 private:
    void __modify(pNode &i,int p,int x,int l,int r) // 单点修改
    {
        if(!i)    i=new Node;
        if(l!=r)
        {
            int mid=(l+r)>>1;
            if(p<=mid)  __modify(i->lc,p,x,l,mid);
            else    __modify(i->rc,p,x,mid+1,r);
        }
        i->val+=x;
    }
    LL __query(pNode &i,int lq,int rq,int l,int r) // 区间查询
    {
        if(!i)    return 0;
        if(l>=lq && r<=rq)
            return i->val;
        int mid=(l+r)>>1; LL sum=0;
        if(lq<=mid) sum+=__query(i->lc,lq,rq,l,mid);
        if(rq>mid)  sum+=__query(i->rc,lq,rq,mid+1,r);
        return sum;
    }
 public:
    WeightTree(int s=0): SegmentTree(s){}
    inline void modify(int p,LL x) // 类的外围接口
        { __modify(rt,p,x,1,sizn); }
    inline LL query(int l,int r)
        { return __query(rt,l,r,1,sizn); }
    friend class FuckingTree;
};

class FuckingTree: public SegmentTree<WeightTree,true>
{
 protected:
    int sizv;
    typedef vector<WeightTree::pNode> ZT; // 用于存根
    typedef vector<pair<WeightTree::pNode,int>> YT; // 用于存tag和累加的数量
    inline void newNode(pNode &i) // 新建节点并初始化其val和tag
    {
        i=new Node();
        i->val.setSize(sizv);
        i->tag.setSize(sizv);
    }
    inline void addTag(pNode &i,int len,int p) // 加tag,len是区间长度
    {
        if(!i)  newNode(i);
        i->tag.modify(p,1);
        i->val.modify(p,len);
    }
 private:
    void __modify(pNode &i,int lq,int rq,int p,int l,int r) // 区间修改:将区间[l,r]上的所有树在p位置上+1
    {
        if(!i)  newNode(i);
        if(l>=lq && r<=rq) // 区间被完全包含,直接加tag
            addTag(i,r-l+1,p);
        else
        { // 标记永久化,不需要pushdown
            int mid=(l+r)>>1;
            if(lq<=mid) __modify(i->lc,lq,rq,p,l,mid);
            if(rq>mid)  __modify(i->rc,lq,rq,p,mid+1,r);
            i->val.modify(p,min(rq,r)-max(lq,l)+1); /* 不需要用左右儿子更新,那样会异常地慢。
                                                       这里直接将val在p上加上1*len([l,r]∩[lq,rq]),也就是min(rq,q)-max(lq,l) */
        }
    }
    void __query(ZT &ts,YT &tg,pNode &i,int lq,int rq,int l,int r) // ts存的是值的树,tg存的是tag的树
    {
        if(!i)    return;
        if(l>=lq && r<=rq)
            ts.push_back(i->val.rt); // 完全包含,直接塞进去
        else
        {
            int mid=(l+r)>>1;
            if(lq<=mid) __query(ts,tg,i->lc,lq,rq,l,mid);
            if(rq>mid)  __query(ts,tg,i->rc,lq,rq,mid+1,r);
            tg.push_back(make_pair(i->tag.rt,min(rq,r)-max(lq,l)+1)); // 这里tag被累加的次数就是len([l,r]∩[lq,rq])
        }
    }
    int __askValue(ZT &ts,YT &tg,LL x,int l,int r) // 线段树上二分查第k大
    {
        if(l==r)    return l;
        int mid=(l+r)>>1;
        LL sum=0;
        for(auto &i: ts)
            if(i && i->rc) sum+=i->rc->val; // 因为是第k大,所以从右儿子找
        for(auto &i: tg)
            if(i.first && i.first->rc)
                sum+=i.first->rc->val*i.second; // 需要乘上该tag出现的次数
        if(sum>=x) // >mid的数字数量>=x,说明答案在右子树
        {
            for(auto &i: ts)    if(i)i=i->rc;
            for(auto &i: tg)    if(i.first)i.first=i.first->rc; // 全部跳到右儿子
            return __askValue(ts,tg,x,mid+1,r);
        }
        else // 否则,答案在左子树
        {
            for(auto &i: ts)    if(i)i=i->lc;
            for(auto &i: tg)    if(i.first)i.first=i.first->lc; // 全部跳到左儿子
            return __askValue(ts,tg,x-sum,l,mid);
        }
    }
 public:
    FuckingTree(int sn,int sv): SegmentTree()
        { sizn=sn,sizv=sv; }
    inline void modify(int l,int r,int p) // 外围接口
        { __modify(rt,l,r,p,1,sizn); }
    inline int askValue(int lq,int rq,LL x)
    {
        ZT ts;YT tg;
        __query(ts,tg,rt,lq,rq,1,sizn); // 先初始化找出ts和tg
        return __askValue(ts,tg,x,1,sizv);
    }
};

struct Question // 询问离线
{
    int opt,l,r;
    LL c;
}q[50005];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%lld",&q[i].opt,&q[i].l,&q[i].r,&q[i].c);
        if(q[i].opt==1) num.insert(q[i].c); // 用set离散化,因为set自带排序去重
    }
    for(auto &i: num)
        no[i]=++maxx,on[maxx]=i; // 'no' for 'number to order', 'on' for 'order to number'
    FuckingTree t(n,maxx);
    for(int i=1;i<=m;i++) // 。。。这里应该足够显然吧
        if(q[i].opt==1)
            t.modify(q[i].l,q[i].r,no[q[i].c]);
        else
            printf("%dn",on[t.askValue(q[i].l,q[i].r,q[i].c)]);
    return 0;
}

后记

这个代码常数巨大。我觉得应该不是指针写法的问题,因为指针和数组本质是一样的。主要问题还是在类内的接口太多,函数调用太多。至于码长,倒不是大问题。


程序员灯塔
转载请注明原文链接:【题解】[ZJOI2013] K大数查询
喜欢 (0)