WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 4923: [Lydsy1706月赛]K小值查询
BZOJ 4923: [Lydsy1706月赛]K小值查询

题目大意

给定一个序列,有两种操作:
1. 排序,查询第K小的数字是多少
2. 对于大于K的数字,都减少K

题解

我们维护一颗平衡树,那么第一种操作就是在平衡树上直接查询。第二个操作,相当于对于原序列,分成值域为[1, K),[K, 2K),[2K, \infty]三个区间,第一个区间不变,第二个区间减少K后与第一个区间合并,第三个区间减少K后接在第一个与第二个区间后面。因为数字只有减少操作,所以合并区间操作的复杂度是递减的,所以我们只需要暴力合并即可。

代码

#include <cstdio>
#include <cstring>
#include <queue>
#include <cassert>

using namespace std;

inline int read()
{
    char c;
    int res,flag=0;
    while((c=getchar())>'9'||c<'0') if(c=='-')flag=1;
    res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0';
    return flag?-res:res;
}

namespace Splay{ // 在1位置与n+2个位置插入空节点,操作时序号不变
    const int MAXN=2e5+50;
    #define ls(x) tree[x].ch[0]
    #define rs(x) tree[x].ch[1]
    #define fa(x) tree[x].fa
    #define mp(x, y) make_pair(x, y)
    #define PII pair<int, int>
    struct BTree{
        int ch[2], fa, siz, rev, cnt; // 子节点,父节点,子树大小,结点数量,翻转标记
        int val, add; // 维护区间最小值
    }tree[MAXN];
    queue<int> que; int numt; // 结点回收与分配
    queue<PII> nQue;
    int root; // 根节点
    int num[MAXN]; // 新建元素数组

    inline int newNode(int f){
        int x; if (!que.empty()) x=que.front(), que.pop(); else x=++numt;
        ls(x)=rs(x)=tree[x].siz=tree[x].rev=0; tree[x].cnt=1; fa(x)=f;
        return x;
    }
    inline void delNode(int x){ que.push(x); } // 删除结点


    void rev(int x){ // 翻转结点信息
        if (!x) return;
        swap(ls(x), rs(x)); tree[x].rev^=1;
        // ?维护翻转时的信息变化
    }
    void update(int x){ // 更新结点信息
        tree[x].siz=tree[ls(x)].siz+tree[rs(x)].siz+tree[x].cnt;
    }
    void clean(int x){ // 下推结点标记
        if (tree[x].rev) rev(ls(x)), rev(rs(x)), tree[x].rev=0;
        // ?维护标记
        if (tree[x].add){
            int tag=tree[x].add; tree[x].add=0;
            if (ls(x)) tree[ls(x)].val+=tag, tree[ls(x)].add+=tag;
            if (rs(x)) tree[rs(x)].val+=tag, tree[rs(x)].add+=tag;
        }
    }
    void init(){ // 初始化Splay
        ls(0)=rs(0)=fa(0)=tree[0].siz=tree[0].cnt=tree[0].rev=0;
        // 这里初始化零号结点其他信息
        while(!nQue.empty()) nQue.pop();
        while(!que.empty()) que.pop(); numt=0; root=newNode(0);  update(root);
    }
    inline void delSplay(int x){ if (!x) return; clean(x); delSplay(ls(x)), delSplay(rs(x)); nQue.push(mp(tree[x].val, tree[x].cnt)); delNode(x); } // 删除子树

    /** 建树三连
     *  Splay::init(); // 新建Splay
     *  for (int i=2; i<=n+1; i++) scanf("%d", &Splay::num[i]); // 实际元素从2~n+1,操作标号不改变
     *  Splay::root=Splay::build(1, n+2, 0);
     */

    inline int ident(int x){ return rs(fa(x))==x; } // 判断结点是其父亲的那个孩子
    int build(int l, int r, int f){ // 建立Splay
        if (l>r) return 0;
        int m=(l+r)/2, x=newNode(f);
        tree[x].val=num[m], tree[x].add=0;
        ls(x)=build(l, m-1, x);
        rs(x)=build(m+1, r, x);
        update(x);
        return x;
    }
    void rotate(int x, int &k){ // 将结点x旋转到结点k位置
        int y=fa(x), z=fa(y);
        int l=ident(x), r=l^1;
        if (y==k) k=x; else tree[z].ch[ident(y)]=x;
        fa(tree[x].ch[r])=y; fa(y)=x; fa(x)=z;
        tree[y].ch[l]=tree[x].ch[r]; tree[x].ch[r]=y;
        update(y); update(x);
    }

    void splay(int x, int &k){ // 将结点xSplay到结点k位置
        while(x!=k){
            int y=fa(x), z=fa(y);
            if(y!=k){ if (ls(y)==x ^ ls(z)==y) rotate(x, k); else rotate(y, k); }
            rotate(x, k);
        }
    }

    int find(int x, int k){ // 查找第k个元素编号
        clean(x);
        if (tree[ls(x)].siz+1<=k && k<=tree[ls(x)].siz+tree[x].cnt) return x;
        if (k<=tree[ls(x)].siz) return find(ls(x), k);
        return find(rs(x), k-tree[ls(x)].siz-tree[x].cnt);
    }

    /*平衡树操作*/
    void insert(int v, int c){ // 在Splay中插入C个元素,值为V的元素
        int x=root, f=0, p;
        while(true){
            clean(x);
            if (tree[x].val==v){
                tree[x].cnt+=c;
                update(x); if(f!=0) update(f);
                splay(x, root); break;
            }else{
                p=(v<tree[x].val?0:1);
                f=x, x=tree[x].ch[p];
                if (x==0){
                    x=tree[f].ch[p]=newNode(f);
                    tree[x].val=v; tree[x].cnt=c; tree[x].add=0;
                    update(x); update(f);
                    splay(x, root); break;
                }
            }
        }
    }
    /*平衡树操作*/
    int search(int x, int v){ // 查找第一个严格大于v的元素位置(因为加入了1、n+2结点,所以相当于在[1, n+2]中查找小于等于v的最后位置)
        clean(x);
        int ret=0;
        if (tree[x].val<=v) {
            ret+=tree[x].cnt;
            if (ls(x)) ret+=tree[ls(x)].siz;
            if (rs(x)) ret+=search(rs(x), v);
        }else{
            if (ls(x)) ret+=search(ls(x), v);
        }
        return ret;
    }

    int split(int k, int tot){ // 提取从第k个元素开始的连续tot个元素(提取到左孩子)
        int x=find(root, k), y=find(root,k+tot+1);
        splay(x, root); splay(y, rs(x));
        return ls(y);
    }

    void erase(int k, int tot){ // 删除从第k个元素开始的连续tot个元素
        int x=split(k, tot), y=fa(x);
        delSplay(x); ls(y)=0;
        update(y); update(fa(y));
    }

    int cut(int k, int tot){ // 剪切从第k个元素开始的连续tot个元素
        int x=split(k, tot), y=fa(x);
        fa(x)=0; ls(y)=0;
        update(y); update(fa(y));
        return x;
    }

    void join(int k, int z){ // 在第k个元素之后插入z为根的Splay(0为序列开头)
        int x=find(root, k+1), y=find(root, k+2); // 找到k+1与k+2个元素
        splay(x, root); splay(y, rs(x)); // 将x转到根,y转到x的右孩子,将y的左孩子空出
        ls(y)=z; fa(z)=y;
        update(y); update(x);
    }

    void reverse(int k, int tot){ // 反转从第k个元素开始的连续tot个元素(其他修改同理)
        int x=split(k, tot), y=fa(x);
        rev(x); // 修改过程
        update(y); update(fa(y));
    }

    void shift(int k, int tot, int D){ // [K, K+tot-1] 区间右移D
        D%=tot; if (D==0) return;
        join(k-1, cut(k+tot-D, D));
    }

    void add(int k, int tot, int D){ // [K, K+tot-1] 区间加D
        int x=split(k, tot), y=fa(x);
        tree[x].val+=D; tree[x].add+=D;
        update(y); update(fa(y));
    }
}


int main(){
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int n=read(), Q=read();
    Splay::init(); Splay::num[1]=0, Splay::num[2]=2e9+50; Splay::root=Splay::build(1, 2, 0);
    for (int i=1; i<=n; i++) Splay::insert(read(), 1);
    //Splay::print(Splay::root); printf("\n");
    for (int i=1; i<=Q; i++){
        int op=read(), k=read();
        if (op==1){
            assert(1<=k && k<=n);
            int x=Splay::find(Splay::root, k+1); //Splay::splay(x, Splay::root);
            printf("%d\n", Splay::tree[x].val);
        }
        if (op==2){
            assert(1<=k && k<=1e9);
            int p1=Splay::search(Splay::root, k), p2=Splay::search(Splay::root, k+k);
            if (p2<=n) Splay::add(p2, n-p2+1, -k);
            if (p2-p1>0){
                Splay::delSplay(Splay::cut(p1, p2-p1));
                while(!Splay::nQue.empty()){
                    int v=Splay::nQue.front().first, c=Splay::nQue.front().second;
                    Splay::nQue.pop(); Splay::insert(v-k, c); //printf("%d %d -> %d\n", op, k, v);
                }
            }
        }
        //Splay::print(Splay::root); printf("\n");
    }
    return 0;
}

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 4923: [Lydsy1706月赛]K小值查询
题目大意 给定一个序列,有两种操作: 1. 排序,查询第K小的数字是多少 2. 对于大于K的数字,都减少K 题解 我们维护一颗平衡树,那么第一种操作就是在平衡树上直接查询。第二个操作,…
扫描二维码继续阅读
2018-10-18
<--! http2https -->