首页 > 其他分享 >【模板】分裂合并 WBLT(自用)

【模板】分裂合并 WBLT(自用)

时间:2024-05-29 16:58:42浏览次数:21  
标签:rt mg ch return int 自用 pushdown WBLT 模板

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <int N>
struct wblt {
  int ch[N << 1][2], tsh[N << 1], tot = 0, cnt = 0, siz[N << 1], val[N << 1];
  int newnode(int v) {
    int p = cnt ? tsh[cnt--] : ++tot;
    ch[p][0] = ch[p][1] = 0, siz[p] = 1, val[p] = v, maintain(p);
    return p;
  }
  bool isleaf(int p) { return !ch[p][0]; }
  void maintain(int p) { 
    if (isleaf(p)) return ;
    val[p] = val[ch[p][1]], siz[p] = siz[ch[p][0]] + siz[ch[p][1]];
  }
  int mg(int p, int q) {
    if (!p || !q) return p + q;
    int lim = 0.292 * (siz[p] + siz[q]);
    if (min(siz[p], siz[q]) >= lim) {
       int t = newnode(val[p]);
       ch[t][0] = p, ch[t][1] = q;
       return maintain(t), t;
    }
    if (siz[p] >= siz[q]) {
// pushdown(p);
      auto [x, y] = ch[tsh[++cnt] = p];
      if (siz[x] >= lim) return mg(x, mg(y, q));
// pushdown(y);
      auto [y0, y1] = ch[tsh[++cnt] = y];
      return mg(mg(x, y0), mg(y1, q));
    } else {
// pushdown(q);
      auto [x, y] = ch[tsh[++cnt] = q];
      if (siz[y] >= lim) return mg(mg(p, x), y);
      auto [x0, x1] = ch[tsh[++cnt] = x];
// pushdown(x);
      return mg(mg(p, x0), mg(x1, y));
    }
  }
  void sp(int p, int k, int& x, int& y) {
    if (!k) return x = 0, y = p, void();
    if (isleaf(p)) return x = p, y = 0, assert(k == 1);
// pushdown(p);
    if (k <= siz[ch[p][0]]) sp(ch[p][0], k, x, y), y = mg(y, ch[p][1]);
    else sp(ch[p][1], k - siz[ch[p][0]], x, y), x = mg(ch[p][0], x);
    tsh[++cnt] = p;
  }
  void spv(int p, int v, int& x, int& y) {
    if (val[p] <= v) return x = p, y = 0, void();
    if (isleaf(p)) return x = 0, y = p, void();
// pushdown(p);
    if (v < val[ch[p][0]]) spv(ch[p][0], v, x, y), y = mg(y, ch[p][1]);
    else spv(ch[p][1], v, x, y), x = mg(ch[p][0], x);
    tsh[++cnt] = p;
  }
  int getkth(int p, int k) {
    while (!isleaf(p)) {
// pushdown(p);
      if (k <= siz[ch[p][0]]) p = ch[p][0];
      else k -= siz[ch[p][0]], p = ch[p][1];
    }
    return val[p];
  }
  void dfs(int p, int &lst) {
    if (!isleaf(p)) dfs(ch[p][0], lst), dfs(ch[p][1], lst);
    else assert(exchange(lst, val[p]) <= val[p]);
  }
};
wblt<100010> t;
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  int m, rt = 0;
  cin >> m;
  while (m--) {
    int op, v, x, y, z;
    cin >> op >> v;
    switch (op) {
      case 1:
        t.spv(rt, v, x, y);
        rt = t.mg(x, t.mg(t.newnode(v), y));
        break;
      case 2:
        t.spv(rt, v - 1, x, y);
        if (y && t.getkth(y, 1) == v) t.sp(y, 1, z, y);
        rt = t.mg(x, y);
        break;
      case 3:
        t.spv(rt, v - 1, x, y);
        cout << t.siz[x] + 1 << endl;
        rt = t.mg(x, y);
        break;
      case 4:
        cout << t.getkth(rt, v) << endl;
        break;
      case 5:
        t.spv(rt, v - 1, x, y);
        cout << t.val[x] << endl;
        rt = t.mg(x, y);
        break;
      case 6:
        t.spv(rt, v, x, y);
        cout << t.getkth(y, 1) << endl;
        rt = t.mg(x, y);
        break;
    }
#ifdef LOCAL
    int lst = -1e9;
    t.dfs(rt, lst);
#endif
  }
  return 0;
}

标签:rt,mg,ch,return,int,自用,pushdown,WBLT,模板
From: https://www.cnblogs.com/caijianhong/p/18220620/template-fhqwblt

相关文章

  • c++ 设计模板
     ========一、设计模式的分类总体来说设计模式分为三大类创建型模式,共五种:工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。结构型模式,共七种:适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。行为型模式,共十一种:策略模式、模板......
  • 解决Odoo Email模板中的时间与实际时间相差8小时的问题
     要解决OdooEmail模板中的时间与实际时间相差8小时的问题,最好的方法是先在服务器端处理时间,然后在模板中调用处理后的时间。在你的截图中,直接在模板中使用了`datetime.datetime.now()`,这会导致时区问题。以下是详细步骤:###1.在模型中添加一个方法来处理时区转换在你的模......
  • SUMER UI3.0组件库,基于Uni-app前端框架!一端开发,多端运行!本组件库可快速二次开发各种类
    sumer-ui介绍基于uView微信小程序UI组件库,兼容vue3。本插件是SUMER组件库,只提供组件库源码下载(不包含模板源码),本组件库可快速二次开发各种类别各行业模板,包括:商城、视频、直播、聊天、支付、新闻、社区、地图、导航、出行、社区、博客、新闻、游戏、影视、订票、广告等,......
  • 揭秘华为如此多成功项目的产品关键——Charter模板
    很多推行IPD(集成产品开发)体系的公司在正式研发产品前,需要开发Charter,以确保产品研发方向的正确。Charter,即项目任务书或商业计划书。Charter的呈现标志着产品规划阶段的完成,能为产品开发的投资评估和决策提供关键依据。在IPD体系中,Charter的核心逻辑主要体现在两点:一是产品值不值......
  • 第七十五节 Java设计模式 - 模板方法模式
    Java设计模式-模板方法模式在模板模式中,父抽象类公开几个抽象方法供子类实现。在父抽象类中有另一个方法或几个方法使用抽象方法来实现业务逻辑。抽象方法通常用于父类所需的每个步骤。例如,为了使用新的软件,我们需要下载,安装,配置和运行。如果我们要使用模板模式来编码逻......
  • Floyd算法的简单使用方法(模板)
    今天我们老师讲了Floyd算法,使用想着总结一下,方便后面进行复习,使用如果在接下来的文章中有哪里写的不对,或者表达不恰当,欢迎提出,谢谢!关于这个算法,我的理解是应用链接矩阵来进行存储值,通过比较来更新值,最后得出最短路径等问题的答案;使用模板:第一步就是使用宏定义来定义一个偏大......
  • 7-4 并查集【模板】
    给出一个并查集,请完成合并和查询操作。输入格式:第一行包含两个整数N、M,表示共有N个元素和M个操作。接下来M行,每行包含三个整数Zi​、Xi​、Yi​。当Zi​=1时,将Xi​与Yi​所在的集合合并。当Zi​=2时,输出Xi​与Yi​是否在同一集合内,是的话输出Y;否则的话输出N。输出格式:......
  • springboot3+Thymeleaf 模板一直找不到的原因。
    1<build>2<resources>3<resource>4<directory>src/main/java</directory>5<includes>6<include>**/*.yml</include>7......
  • 记一次攻防演练中的若依(thymeleaf 模板注入)getshell
    记一次攻防演练中幸运的从若依弱口令到后台getshell的过程和分析。0x01漏洞发现首先,我会先把目标的二级域名拿去使用搜索引擎来搜索收集到包含这个目标二级域名的三级域名或者四级域名的网站。这样子可以快速的定位到你所要测试的漏洞资产。1、推荐三个比较实用的搜索引擎:奇......
  • 微信小程序基础 --模板语法(4)
    模板语法1、wxml视图结构1.1概述开发文档:https://developers.weixin.qq.com/miniprogram/dev/framework/quickstart/code.html#WXML-%E6%A8%A1%E6%9D%BF从事过网页编程的人知道,网页编程采用的是HTML+CSS+JS这样的组合,其中HTML是用来描述当前这个页面的结构,CS......