首页 > 其他分享 >线段树二分——nc2.4多校_G.新春漫步

线段树二分——nc2.4多校_G.新春漫步

时间:2024-02-04 22:33:58浏览次数:29  
标签:rt idx int 多校 nc2.4 mid lt 新春 define

目录

问题概述

原题参考G.新春漫步
坐标轴上有n个点,初始时每个位置上都有一个坚固程度为a1的障碍物,接下来有m次操作
1.将位置p上的障碍物的坚固程度减去x,若减去x后坚固程度小于等于0,则该障碍物消失
2.询问一个人从p的位置向右走,最多能走到什么位置(停在遇到的第一个障碍物的位置)

思路分析

赛时看到这个题我还是比较惊喜的,首先操作一就是属于单点修改,操作二是啥,简单分析一下嘛,从p位置开始走,直到第一个障碍物停止,那么期间走过的位置的坚固值不全都是0嘛,那么不就是查询最长的区间和为0的区间嘛,那这就是区间查询的操作嘛,这个又可以用二分进行简化,但是二分简化之后要进行一次特判;因为使用二分的话区间查询最小区间是2,不能判断当前位置是否是0,大致倒是很类似最近LCA的第二次跳点的做法

参考代码

#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
#define pll pair<long long, long long>
#define pii pair<int, int>
#define vi vector<int>
#define vl vector<long long>
#define ll long long
#define ull unsigned long long
const ll INF = 9187201950435737471;
const int inf = 2139062143;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1.0);
const int N = 1e6+7;
ll n, m, a[N];
ll getL(int idx) {return idx<<1;}
ll getR(int idx) {return idx<<1|1;}
ll sum(ll a, ll b) {return a+b;}
struct node {
    ll nSum;
} t[N*4];
inline ll read() {
    //使用快读记得别关流 会tle的
    ll res = 0, mark = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') mark = -1;
        ch = getchar(); 
    }
    while(ch >= '0' && ch <= '9') {
        res = (res<<1) + (res<<3) + (ch^48);
        ch = getchar();
    }
    return res * mark;
}
inline void write(int x) {
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}
void update(int idx) {
    t[idx].nSum = sum(t[getL(idx)].nSum, t[getR(idx)].nSum);
}
void build(int idx, int lt, int rt) {
    if(lt == rt) t[idx].nSum = a[lt];
    else {
        int mid = (lt+rt) >> 1;
        build(getL(idx), lt, mid);
        build(getR(idx), mid+1, rt);
        update(idx);
    }
}
void change(int idx, int lt, int rt, int cidx, int add) {
    if(lt == rt) {
        t[idx].nSum += add;
        if(t[idx].nSum < 0) t[idx].nSum = 0;
    }
    else {
        int mid = (lt+rt) >> 1;
        if(cidx <= mid) change(getL(idx), lt, mid, cidx, add);
        else change(getR(idx), mid+1, rt, cidx, add);
        update(idx);
    }
}
ll query(int idx, int lt, int rt, int ql, int qr) {
    ll ans = 0;
    if(lt == ql && rt == qr) ans += t[idx].nSum;
    else {
        ll mid = (lt+rt) >> 1;
        if(qr <= mid) ans += query(getL(idx), lt, mid, ql, qr);
        else if(ql > mid) ans += query(getR(idx), mid+1, rt, ql, qr);
        else ans += sum(query(getL(idx), lt, mid, ql, mid), query(getR(idx), mid+1, rt, mid+1, qr));
    }
    return ans;
}
void solve() {
    n = read(), m = read();
    for(int i=1; i<=n; i++) a[i] = read();
    build(1, 1, n);
    while(m --) {
        int op, p, q;
        op = read(), p = read();
        if(op == 1) {
            q = read();
            change(1, 1, n, p, -q);
        }
        else {
            int lt = p, ans = p;
            for(int i=20; i>=0; i--) {
                if(lt+(1ll<<i) > n) continue;
                if(!query(1, 1, n, lt, lt+(1ll<<i))) {
                    lt = lt+(1ll<<i);
                    ans = lt;
                }
            }
            if(!query(1, 1, n, ans, ans) && ans < n) ans ++;
            write(ans);
            putchar('\n');
        }
    }
}

int main() {
#ifdef xrl
    freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
#endif
    //FAST_IO;
    int t = 1;
    //cin >> t;
    while(t --) solve();
#ifdef xrl
    cout << "Time used = " << (double)(clock() * 1.0 / CLOCKS_PER_SEC) << "s";
#endif
    return 0;
}

做题反思

说实话,赛时的第一发不是线段树,而是树状数组,但是由于对树状数组的理解不是很深,导致修改的时候出现了问题,就是我没有记录原数组,不得而知该次操作是否对树状数组生效,当然,这是赛后想出来的了;赛时还是用线段树写的,经此一役,我再也不会因为线段树的空间复杂度嫌弃线段树了,毕竟它都没嫌弃我蠢,emmm
第二,以后我遇到大量样例输入,请使用较快的输入输出这句话时,我尼玛一定要用快读快写,今日是从关流的cin->scanf->quickread,诶,就是喜欢超时,怎么了!!!

标签:rt,idx,int,多校,nc2.4,mid,lt,新春,define
From: https://www.cnblogs.com/notalking569/p/18007131

相关文章

  • 缩小数据范围——nc2.4多校_A.新春游戏之数学系列
    目录问题概述思路分析参考代码做题反思问题概述原题参考A.新春游戏之数学系列大致就是给出一个数组,要求求出一个公式的值,有几个数据范围值得注意一下,一是数组的长度为[0,1e6],二是数组元素的和不超过5e7思路分析赛时第一眼准备去分析公式看看有没有可以优化的,用前缀拆分优化......
  • 拼手速!9999个鹅厂红包封面带你龙码精神过新春
    过去的一年是波涛起伏的一年大模型的爆发催化了产业的迭代技术与应用的内卷却让程序员渐生迷茫未来的一年仍是充满期待的一年只因再先进的超算,也无法定义人类的边界总有人在砥砺前行,追寻缝隙中透出的那一丝光明社区是一群志同道合伙伴的聚集地我们在这分享宏大叙事里的微小......
  • 武汉星起航:新年伊始,国产游戏行业迎来新春华章
    2024年的脚步渐近,随着12月份新批国产网络游戏版号数量过百,中国游戏行业再次迎来一轮繁荣的浪潮。这一系列积极信号不仅释放出支持网络游戏行业健康发展的强烈信号,也为游戏从业者们带来了新的发展机遇。在企业端,游戏版号的大幅增长不仅证明了监管部门对游戏行业的支持态度,也为创业者......
  • 20231213-sdfz多校集训-DS
    非lxl的DS不会线性代数,只能来写DS了。20231226-没有逻辑,直接放例题。P1527矩阵乘法-整体二分P1527[国家集训队]矩阵乘法给你一个\(n\timesn\)的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第\(k\)小数。\(1\leqn\leq500\),\(1\leqq\leq6\times......
  • 牛客2022多校DAY10-K You are given a tree
    「牛客2022多校DAY10-K」Youaregivenatree...简要题意给一棵带点权和边权的树,找到至多\(k\)个点权不同的点,使得它们之间路径覆盖的边权和最大。\(n\le5000,k\le5\)。Solution考虑颜色数量不大的时候怎么暴力。显然可以直接状压DP,压一下当前选择的颜色集合为\(S\),......
  • 20231212-sdfz 多校集训-杂题选讲
    杂题选讲20231212《批题乱讲》[ARC132E]Paw-期望+计数AT_arc132_e[ARC132E]Paw长为\(n\)的字符串,每个地方可能是<>.每次随机一个.的地方,然后等概率向左向右。直到走出边界或者走到.。路上会留下相同方向的符号。问最后期望<的个数有多少。\(1\len\l......
  • 2023 牛客多校 9 B
    给定\(1\lea<m\le10^9\),求\(1\leu\le10^{18}\)使得\(a^u\equivu\pmodm\)。做法先考虑不限制解的大小怎么做。显然有如果\(a^v\equivv\pmod{\varphi(m)}\),且\(v\ge\varphi(m)\),则\(a^{a^v}\equiva^v\pmodm\),于是取\(u=a^v+m\varphi(m)......
  • 2023 牛客多校 8 E
    神仙题。题意计数长度为\(n\),满足以下条件的序列\(a\)个数\(\bmod998244353\):\(L\lea_i\leR\)。\(S_1(\suma_i)\equivS_2(\suma_i)\pmodm\)。其中\(S_1(x)\)表示\(x\)的各个数位的和,\(S_2(x)\)表示各个数位平方和(十进制下)。数据范围:\(1\len,m\le20,1\l......
  • 【多校联考NOIP#12】比赛复盘
    A.星穹铁道读完题面就想到了\(O(n^2)\)的暴力。很好想,但是只有40分。观察到\(z_i=\pm1\),然而即便如此,我也没有得到有用的性质。(正解是用到这个性质的)然后我就暴力写了。正解的性质“最终在一个区间L,R内,初始也一定在一个连续段内”赛事没有想到。同时题解用了逆向思维,对......
  • 2023牛客暑期多校训练营8 B Bloodline Counter 指数型生成函数 容斥 多项式求逆
    传送门容易想到求出竞赛图上最大环\(\lek\)的数量,再求出\(\lek-1\)的数量作差即可得到答案。设指数型生成函数\(G(x)\)表示大小为\(i\)的环的方案数。\(G(x)=\sum_{i=1}^k\frac{a_i}{i!}x^i\)那么最大环\(\lek\)的数量\(=[x^n]n!\sum_{i=1}^ki!\frac{(G(x))^i}{i!}\)这里......