首页 > 其他分享 >P6309 题解

P6309 题解

时间:2024-10-09 21:46:04浏览次数:5  
标签:P6309 int 题解 ll ls 坐标 线段 关键点

很经典但是很好的题目。/qiang

标签:线段树。

  • 数轴上有一些关键点,不同的关键点可能在同一坐标。关键点的坐标均为整数。
  • 支持两种操作:
    1. 删去 / 添加一些关键点。
    2. 取一个点。使得它与 \([l, r]\) 范围内所有关键点的距离最小。求最小距离。
  • \(\text{关键点的坐标数}\le 3\times 10^5\),\(\text{所有坐标的绝对值}\le 10^9\)。

首先每个坐标上有多少个关键点是很好维护的。如果已经取了个点,如何计算答案?一个经典做法是把绝对值拆开。假设取的点坐标是 \(x\),左边有 \(a\) 个关键点,它们的坐标和为 \(S_a\);右边有 \(b\) 个关键点,坐标和为 \(S_b\)。则答案为 \((ax-S_a) + (S_b - bx)\)。用线段树维护 区间内关键点的个数坐标和 即可。

问题来到了如何找点 \(x\)。有一种比较感性的思考方式:随便取一个 \(x\),我们将 \(x\) 向左移 \(\Delta x\) 且不越过关键点,那么距离增加了 \(b\Delta x - a\Delta x = (b - a)\Delta x\)。如果 \(a > b\) 即左边的点较多时,\((b - a)\Delta x < 0\),则距离减少了。也就是说,当左边的点多时,向左移是优的;同理当右边的点较多时,向右移是优的。那么最终 \(x\) 会停在区间内坐标从小到大第 \(\frac{\text{点的个数}}{2}\) 个点的位置。求这个坐标可以线段树上二分。

用权值线段树维护即可。时间复杂度 \(O(n\log n)\)。我写的是动态开点线段树,获得了线段树写法的最优解。code:

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;
const int N = 300010, eps = 1e9, V = 1e9;
int cnt, ro;
struct Seg {
    int ls, rs;
    ll c, v;
} T[N * 4 * 32];
int n, m; ll a[N], b[N];
#define ls(k) (T[k].ls)
#define rs(k) (T[k].rs)

inline int read() {
	int x = 0, f = 1;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
	return x * f;
}
inline void write(ll x) {
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}

void pushup(int k) {
    T[k].c = T[ls(k)].c + T[rs(k)].c;
    T[k].v = T[ls(k)].v + T[rs(k)].v;
}
void update(ll l, ll r, int &k, ll x, ll c) {
    if(!k) k = ++cnt;
    if(l == r) {
        T[k].c += c;
        T[k].v = x * T[k].c;
        return;
    }
    ll mid = (l + r) / 2;
    if(x <= mid) update(l, mid, ls(k), x, c);
    else update(mid + 1, r, rs(k), x, c);
    pushup(k);
}
ll getc(ll l, ll r, int k, ll L, ll R) {
    if(!k) return 0;
    if(L <= l && r <= R) return T[k].c;
    ll mid = (l + r) / 2, res = 0;
    if(L <= mid) res += getc(l, mid, ls(k), L, R);
    if(mid < R) res += getc(mid + 1, r, rs(k), L, R);
    return res;
}
ll getv(ll l, ll r, int k, ll L, ll R) {
    if(!k) return 0;
    if(L <= l && r <= R) return T[k].v;
    ll mid = (l + r) / 2, res = 0;
    if(L <= mid) res += getv(l, mid, ls(k), L, R);
    if(mid < R) res += getv(mid + 1, r, rs(k), L, R);
    return res;
}
ll find(ll l, ll r, int k, ll c) {
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(c <= T[ls(k)].c) return find(l, mid, ls(k), c);
    else return find(mid + 1, r, rs(k), c - T[ls(k)].c);
}

int main() {
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read() + eps;
    for (int i = 1; i <= n; i++) {
        b[i] = read();
        update(0, 2e9, ro, a[i], b[i]);
    }
    while(m--) {
        int op = read();
        if(op == 2) {
            ll x = read(), y = read() + eps, z = read();
            update(0, 2e9, ro, a[x], -b[x]);
            a[x] = y, b[x] = z;
            update(0, 2e9, ro, a[x], b[x]);
        } else {
            ll l = read() + eps, r = read() + eps;
            ll mid = getc(0, 2e9, ro, 0, l - 1) + (getc(0, 2e9, ro, l, r) + 1) / 2;
            mid = find(0, 2e9, ro, mid);
            write(mid * getc(0, 2e9, ro, l, mid - 1) - getv(0, 2e9, ro, l, mid - 1) + getv(0, 2e9, ro, mid + 1, r) - mid * getc(0, 2e9, ro, mid + 1, r));
            puts("");
        }
    }
    return 0;
}

如有错误烦请您指出。

标签:P6309,int,题解,ll,ls,坐标,线段,关键点
From: https://www.cnblogs.com/Running-a-way/p/18455220

相关文章

  • 深度学习No module named ‘torchvision.transforms.functional_tensor‘问题解决
    问题在进行深度学习训练过程中出现ModuleNotFoundError:Nomodulenamed'torchvision.transforms.functional_tensor'报错,多方查阅资料后得到了解决方案。关于我的环境:CUDA==12.1torch==2.4.1GPU==4090D原先进行深度学习用的CUDA11.3,torch1.2.1,但是在训练时出现nvrtc......
  • AGC005 题解
    目录A-STringB-MinimumSumC-TreeRestoringA-STring用栈模拟一下即可,具体的,当栈顶出现形如ST时,将其弹出。#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llRead(){ intsig=1; llnum=0; charc=getchar(); while(!isdigit(c))......
  • 2024年江西省职业院校技能大赛高职组“数据库运行与管理“竞赛样题解析答案
    2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案文章目录2024年江西省职业院校技能大赛高职组"数据库运行与管理"竞赛样题解析答案模块A:数据库理论模块B:数据库设计与运维`任务一参考答案:``任务二参考答案:`模块C:数据库查询与分析`模块C参考答案:`......
  • [NOIP2006 提高组] 作业调度方案 题解
    题目描述我们现在要利用 m 台机器加工 n 个工件,每个工件都有 m 道工序,每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。每个工件的每个工序称为一个操作,我们用记号 j-k 表示一个操作,其中 j 为 1 到 n 中的某个数字,为工件号;k 为 ......
  • NewStar CTF 2024 week1 题解
    1.base题目给了以下内容:Thisisabasequestion!4C4A575851324332474E324547554B494A5A4446513653434E564D444154545A4B354D45454D434E4959345536544B474D5134513D3D3D3D观察给出的字符串发现,字符串由数字0-9以及字母A-F组成,于是推测这可能是一个base16编码,于是将其解码,......
  • 2023牛客OI赛前集训营-提高组(第三场) - 题解汇总
    空位与数(game)贪心即可,因为正正得正,负负也得正,所以将两个数组分别按照正负性分开,然后让正数里面大的配上大的,负数里面绝对值大的配上绝对值大的,这样可以让正积总和尽量大。剩下不足的(必须要一正一负相乘的)让绝对值大的配绝对值小的,这样可以让负积总和尽量小。#include<cstdio>#i......
  • webapi发布---问题解决
    一.127.0.0.1是回路地址,来检验本机TCP/IP协议栈,实际使用过程中服务端不在本机,是外部地址,要用IP地址测试。外部用户采用IP+端口号访问,如下图浏览器访问不了,400错误。解决方案:因为IIS7采用了更安全的web.config管理机制,默认情况下会锁住配置项不允许更改。以管理员身份运......
  • 题解:SP6517 JOCHEF - Farmer Sepp
    一眼简单悬线法,而且有多倍经验,感觉这题被遗忘了,那我就拿下这个水紫吧!我们用a数组表示能向上延伸能到达的最大距离,依次遍历每一行,如果该位置为F,他可以从上一行转移过来,将a数组增加一,如果该位置为C,意味着这个位置不能成矩形,将a数组变为0。接下来进行悬线法的标准操作,设l......
  • 使用宝塔快速搭建配置Openai api接口代理+502 Bad Gateway网关错误问题解决
    本教程提供了一种简便快捷的方法,无需复杂步骤,极易操作,实现零代码、零部署的快速接入。实现准备1.服务器,这里使用阿里香港轻量服务器)2.OpenAI官方的模型apikey3.使用第三方系统或插件进行测试关于第三方网站系统或插件:《SparkAI系统介绍文档-渐进式AIGC系统》开......
  • P10673 【MX-S1-T2】催化剂 题解
    要解决这个问题,我们需要高效地处理动态更新的糖果种类数量,并在每次询问时快速计算最小的愤怒值总和。以下是详细的解决方案和实现步骤:问题分析糖果的种类和数量:每个糖果有一个类型,代表不同的种类。我们需要跟踪每种类型的糖果数量,以便在分配时计算重复的糖果数量,从而确定愤......