首页 > 其他分享 >CF1567E Non-Decreasing Dilemma 题解 线段树

CF1567E Non-Decreasing Dilemma 题解 线段树

时间:2023-02-13 22:23:30浏览次数:68  
标签:Non Dilemma int 题解 线段 序列 端点 区间 leqslant

题目链接:http://codeforces.com/problemset/problem/1567/E

题目大意:

有一个长度为 \(n\) 的数列 \(a\),你需要对其进行 \(q\) 次操作,操作有两种类型,按如下格式给出:

  • 1 x y:将 \(a_x\) 变成 \(y\)。
  • 2 l r:询问位置在 \([l,r]\) 之间的不下降子串有多少个。形式化地说,你需要求出满足下列条件的数对 \((p,q)\) 的个数:
    • \(l\leqslant p\leqslant q\leqslant r\)。
    • \(\forall i\in[p,q),a_i\leqslant a_{i+1}\)。

解题思路:

维护一棵线段树,需要记录:

  • 区间左端点的数值
  • 区间右端点的数值
  • 区间左端点开始的最长连续非严格上升子序列长度
  • 区间又断电开始的最长连续非严格上升子序列长度
  • 区间内连续非严格上升子序列个数

查询的时候先统计左子树和右子树各自的非严格上升子序列个数,然后左右子树汇总。就能解决这个问题。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int n, q;

int lp[maxn<<2],    // 最左边节点权值
    rp[maxn<<2],    // 最右边节点权值
    llen[maxn<<2],  // 最左边连续一段长度
    rlen[maxn<<2];  // 最右边连续一段长度
long long tr[maxn<<2]; // 区间内连续上升子序列个数

#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1

void push_up(int l, int r, int rt) {
    lp[rt] = lp[rt<<1];
    rp[rt] = rp[rt<<1|1];
    int mid = (l + r) / 2;
    llen[rt] = llen[rt<<1];
    if (llen[rt<<1] == mid - l + 1 && rp[rt<<1] <= lp[rt<<1|1])
        llen[rt] += llen[rt<<1|1];
    rlen[rt] = rlen[rt<<1|1];
    if (rlen[rt<<1|1] == r - mid && rp[rt<<1] <= lp[rt<<1|1])
        rlen[rt] += rlen[rt<<1];
    tr[rt] = tr[rt<<1] + tr[rt<<1|1];
    if (rp[rt<<1] <= lp[rt<<1|1])
        tr[rt] += (long long) rlen[rt<<1] * llen[rt<<1|1];
}

void build(int l, int r, int rt) {
    if (l == r) {
        scanf("%d", lp+rt);
        rp[rt] = lp[rt];
        llen[rt] = rlen[rt] = tr[rt] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(lson);
    build(rson);
    push_up(l, r, rt);
}

void update(int p, int v, int l, int r, int rt) {
    if (l == r) {
        lp[rt] = rp[rt] = v;
        // llen[rt] = rlen[rt] = tr[rt] = 1; // 叶子节点这三个值不会改变
        return;
    }
    int mid = (l + r) / 2;
    (p <= mid) ? update(p, v, lson) : update(p, v, rson);
    push_up(l, r, rt);
}

long long query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return tr[rt];
    int mid = (l + r) / 2;
    long long res = 0;
    if (L <= mid) res += query(L, R, lson);
    if (R > mid) res += query(L, R, rson);
    if (L <= mid && R > mid && rp[rt<<1] <= lp[rt<<1|1]) {
        int lcnt = min(rlen[rt<<1], mid - L + 1);
        int rcnt = min(llen[rt<<1|1], R - mid);
        res += (long long) lcnt * rcnt;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &q);
    build(1, n, 1);
    while (q--) {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1)
            update(x, y, 1, n, 1);
        else
            printf("%lld\n", query(x, y, 1, n, 1));
    }
    return 0;
}

标签:Non,Dilemma,int,题解,线段,序列,端点,区间,leqslant
From: https://www.cnblogs.com/quanjun/p/17118046.html

相关文章

  • Ubuntu cmake 安装以及问题解决(muduo库编译)
    1、安装cmakesudoapt-getinstallcmake 2、安装之后查看是否安装成功:cmake--version3、出现 NoCMAKE_C_COMPILERcouldbefound.如何解决使用cmake命令时发......
  • [ABC289D] Step Up Robot 题解
    Problem有一机器人初始在\(0\)级阶梯,对于每一级阶梯,机器人可以从\(1\simN\)种任选一个\(i\)走\(A_i\)步,同时有\(M\)个障碍在\(B_i\)级阶梯,若走到障碍则将无......
  • P2430 严酷的训练 题解
    题目背景Lj的朋友WKY是一名神奇的少年,在同龄人之中有着极高的地位。。。题目描述他的老师老王对他的程序水平赞叹不已,于是下决心培养这名小子。老王的训练方式很奇怪,他......
  • 前端导出pdf字体表格被截断问题解决
    最近有个导出pdf的需求,写好之后分页出现字体,表格被截断的问题,影响美观,需要解决。  经过多方查找,发现一个比较好的思路,设置背景色为白色,然后转成图片后,获取截断处图片......
  • ABC283E 题解
    前言题目传送门!更好的阅读体验?很简单的一道题,强行在英语课的时候想到做法。存储方式与其他题解稍有不同。本题解着重讲是怎么想到这个做法的。思路首先考虑暴力。用......
  • 【题解】CF1500B Two chandeliers
    题目分析:感觉这个题难度虚高,怕是因为一般不用翻译软件翻译输入输出格式(如果我们关注到了输入格式的话就可以发现一个很有用的地方,就是\(a\)和\(b\)单个序列内包含的......
  • 【题解】ABC289 E-G
    现在ABC的G竟然沦落到我都能做出来的地步了。E.SwapPlaces题目分析:这个题初看可能不很好好做的样子,但是看到它的数据范围是个\(O(n^2)\)随便跑的复杂度,所以直接......
  • 【题解】CF364E Empty Rectangles
    题目分析:如果题目放在序列上,也就是询问一个长度为\(n\)的序列有多少个子段满足其和为\(k\),那么考虑应该怎么做。显然就是使用分治,即左边的答案+右边的答案+跨过中间的......
  • 【题解】CF150E Freezing with Style
    题目分析:看到中位数最大显然可以想到直接二分这个中位数,然后将大于等于的边设为\(1\)小于的设为\(-1\),那么一条路径权值和大于等于\(0\)就意味着中位数大于等于二分......
  • org.apache.ibatis.binding.BindingException: Parameter ‘XXXX‘ not found.的问题
    文章目录​​问题分析​​​​[1]两个普通参数​​​​[2]既有参数又有对象​​问题分析是当Dao层的方法有多个参数的时候,我们需要加入@Param注解我下面都是用注解开发的,不......