您现在的位置是:首页 > 正文

BZOJ3600:没有人的算术

2024-04-01 01:01:24阅读 0

传送门
如果能给每个 \(pair\) 按照权值编号就好了
假设之前已经有了所有的权值的编号,现在考虑编号新的 \(pair\)
如果看过了陈立杰的论文的话,不难得到一个重量平衡树的做法
给树上每个子树一个实数权值区间 \([l,r]\),这个点权值为 \(mid=\frac{l+r}{2}\)
左子树 \([l,mid]\) 右子树 \([mid,r]\)
只需要选择一个树高 \(log\) 的树(treap/替罪羊树)使得满足精度要求即可

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn(5e5 + 5);
const double alpha(0.75);

int ls[maxn], rs[maxn], rt, tot, size[maxn], que[maxn], cnt, id[maxn], n, m;
double val[maxn];
pair <int, int> info[maxn];
int mx[maxn << 2];

inline int operator <(pair <int, int> a, pair <int, int> b) {
    return val[a.first] == val[b.first] ? val[a.second] < val[b.second] : val[a.first] < val[b.first];
}

void Dfs(int u) {
    if (!u) return;
    Dfs(ls[u]), que[++cnt] = u, Dfs(rs[u]);
}

int Build(int l, int r, double vl, double vr) {
    if (l > r) return 0;
    double midv;
    int mid, o;
    mid = (l + r) >> 1, o = que[mid], midv = (vl + vr) * 0.5;
    ls[o] = rs[o] = 0, val[o] = midv;
    ls[o] = Build(l, mid - 1, vl, midv);
    rs[o] = Build(mid + 1, r, midv, vr);
    size[o] = size[ls[o]] + size[rs[o]] + 1;
    return o;
}

int Rebuild(int x, double vl, double vr) {
    cnt = 0, Dfs(x);
    return Build(1, cnt, vl, vr);
}

int Insert(int &x, double vl, double vr, pair <int, int> v) {
    double midv;
    int ret;
    midv = (vl + vr) * 0.5;
    if (!x) {
        x = ++tot, val[x] = midv, info[x] = v, size[x] = 1;
        return x;
    }
    if (alpha * size[x] < max(size[ls[x]], size[rs[x]])) x = Rebuild(x, vl, vr);
    if (v == info[x]) return x;
    else if (v < info[x]) ret = Insert(ls[x], vl, midv, v);
    else ret = Insert(rs[x], midv, vr, v);
    size[x] = size[ls[x]] + size[rs[x]] + 1;
    return ret;
}

void Modify(int x, int l, int r, int p) {
    int mid;
    if (l == r) mx[x] = l;
    else {
        mid = (l + r) >> 1;
        p <= mid ? Modify(x << 1, l, mid, p) : Modify(x << 1 | 1, mid + 1, r, p);
        mx[x] = val[id[mx[x << 1]]] >= val[id[mx[x << 1 | 1]]] ? mx[x << 1] : mx[x << 1 | 1];
    }
}

int Query(int x, int l, int r, int ql, int qr) {
    int mid, ret, v;
    if (ql <= l && qr >= r) return mx[x];
    mid = (l + r) >> 1, ret = -1, v;
    if (ql <= mid) ret = Query(x << 1, l, mid, ql, qr);
    if (qr > mid) {
        v = Query(x << 1 | 1, mid + 1, r, ql, qr);
        ret = (ret == -1 || val[id[v]] > val[id[ret]]) ? v : ret;
    }
    return ret;
}

int main() {
    int i, l, r, k;
    char op;
    scanf("%d%d", &n, &m);
    val[0] = -1, Insert(rt, 0, 1, make_pair(0, 0));
    for (i = 1; i <= n; ++i) Modify(1, 1, n, i);
    for (i = 1; i <= m; ++i) {
        scanf(" %c%d%d", &op, &l, &r);
        if (op == 'C') {
            scanf("%d", &k);
            id[k] = Insert(rt, 0, 1, make_pair(id[l], id[r]));
            Modify(1, 1, n, k);
        }
        else printf("%d\n", Query(1, 1, n, l, r));
    }
    return 0;
}

转载于:https://www.cnblogs.com/cjoieryl/p/10260000.html

网站文章

  • java 从excel取数据,如何用JAVA读取EXCEL文件里面的数据(用java处理excle数据)

    java操作poi怎么更改excel中的数据修改要写入,也就是保存一。import java.io.FileInputStream;import java.io.FileNotFoundExcepti...

    2024-04-01 01:01:16
  • 人脸识别活体检测(张嘴摇头识别)

    人脸识别活体检测(张嘴摇头识别)

    最近项目在做了身份证银行卡识别之后,开始实现人脸识别和活体识别,其中人脸识别包括人脸入库、人脸查找、人脸1:N对比、人脸N:N对比,另外活体识别运用在安全登录功能。大家都熟知的支付宝使用face++ ...

    2024-04-01 01:01:11
  • c语言链表查,C语言: 链表查询

    c语言链表查,C语言: 链表查询

    满意答案shisanying2016.01.13采纳率:45%等级:10已帮助:725人struct human{char sex[5];char name[10];int age;struct human *next}首先如果已经建好链表的话,就会有一个头指针,假设是 head那么 我只写一部分代码了,相信你学到链表的话其他部分应该不会难倒你int i;char s[10]; //假设...

    2024-04-01 01:01:03
  • 正则表达式总结

    正则表达式//元字符. 换行符以外任意字符\w 字母/数字/下划线/汉字\s 任意空白符\d 数字\b 单词开始和结尾^ 字符串开始$ 字符串结束//字符转义使用\来取消字符的特殊意义//重复* 重复任意次+ 重复一次或多次? 重复零次或一次{n} ...

    2024-04-01 01:00:38
  • 使用双重循环根据用户输入的数字,输出等腰三角形

    public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println(&qu...

    2024-04-01 01:00:35
  • matlab 空间模态,matlab中使用VMD(变分模态分解)

    matlab 空间模态,matlab中使用VMD(变分模态分解)

    使用计算出的IMF绘制多分量信号的希尔伯特频谱。将频率范围限制为[0,40] Hz。分段信号的VMD生成一个由二次趋势,线性调频信号和余弦组成的分段复合信号,在t = 0.5时,两个恒定频率之间会发生急剧过渡 。x(t)= 6t2 + cos(4πt+10πt2)+ {cos(60πt),cos(100πt-10π),t≤0.5,t&gt; 0.5。信号以1 kHz采样1秒。绘制每个单独的分...

    2024-04-01 01:00:28
  • BUUCTF Reverse/特殊的 BASE64

    BUUCTF Reverse/特殊的 BASE64

    BUUCTF Reverse/特殊的 BASE64先看文件信息,没有加壳用IDA64位打开,看题目描述就知道这是base码表做了变换跟进查看base64加密有一个拷贝函数然后下面就是正常的加密了变换过的码表然后找个网站在线自定义base64编解码解出flagflag{Special_Base64_By_Lich}...

    2024-04-01 01:00:03
  • https://download.docker.com/linux/centos/2/x86_64/stable/repodata/repomd.xml: [Errno 14] HTTPS Error

    使用Red Hat7安装docker时报以下错误 https://download.docker.com/linux/centos/2/x86_64/stable/repodata/repomd.xm...

    2024-04-01 00:59:55
  • 设计模式学习笔记(五) - 观察者模式 Observer

    设计模式学习笔记(五) - 观察者模式 Observer

    设计模式学习笔记(五) - 观察者模式 Observer

    2024-04-01 00:59:49
  • 编程必备基础知识|计算机组成原理篇(02):计算机的分类

    编程必备基础知识|计算机组成原理篇(02):计算机的分类

    计算机基础方面的知识,对于一些非科班出身的同学来讲,一直是他们心中的痛,而对于科班出身的同学,很多同学在工作之后,也意识到自身所学知识的不足与欠缺,想回头补补基础知识。关于计算机基础的课程很多,内容繁杂,但无论是相关书籍还是大学课程,都有点脱离工作。特别地,计算机基础知识体系庞杂,想要从零学习或者复习都耗时耗力。有鉴于此,本系列文章将带你更快的补足编程必备基础知识,涵盖计算机领域三大基...

    2024-04-01 00:59:24