G - 区间操作 Ⅱ
创始人
2024-06-01 00:49:16
0

终于拿下了这棵线段树!!!!(哭)

#include 
#define endl '\n'
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
typedef pair PII;
const int N = 1e5 + 10;
struct Tree
{int l, r;int max, cnt, lazy;
} tr[N << 2];
int w[N];
int n, m;
void change(int u, int lazy)
{tr[u].max += lazy;tr[u].lazy += lazy;
}
void pushdown(int u)
{if (tr[u].lazy){change(u << 1, tr[u].lazy);change(u << 1 | 1, tr[u].lazy);tr[u].lazy = 0;}
}
void pushup(Tree &u, Tree &l, Tree &r)
{u.max = max(l.max, r.max);if (l.max == r.max)u.cnt = l.cnt + r.cnt;else if (l.max > r.max)u.cnt = l.cnt;elseu.cnt = r.cnt;
}
void pushup(int u)
{pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{if (l == r){tr[u] = {l, r, w[l], 1, 0};}else{tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);pushup(u);}
}
void modify(int u, int l, int r, int k)
{if (tr[u].l >= l && tr[u].r <= r){change(u, k);return;}pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (l <= mid)modify(u << 1, l, r, k);if (r > mid)modify(u << 1 | 1, l, r, k);pushup(u);
}
Tree query(int u, int l, int r)
{if (tr[u].l >= l && tr[u].r <= r)return tr[u];pushdown(u);int mid = tr[u].l + tr[u].r >> 1;if (r <= mid)return query(u << 1, l, r);else if (l > mid)return query(u << 1 | 1, l, r);else{auto left = query(u << 1, l, r);auto right = query(u << 1 | 1, l, r);Tree res;pushup(res, left, right);return res;}
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> w[i];}build(1, 1, n);int op, l, r, c;while (m--){cin >> op >> l >> r;if (op == 1){cin >> c;modify(1, l, r, c);}else{cout << query(1, l, r).cnt << endl;}}return 0;
}

相关内容

热门资讯

监控摄像头接入GB28181平... 流程简介将监控摄像头的视频在网站和APP中直播,要解决的几个问题是:1&...
Windows10添加群晖磁盘... 在使用群晖NAS时,我们需要通过本地映射的方式把NAS映射成本地的一块磁盘使用。 通过...
protocol buffer... 目录 目录 什么是protocol buffer 1.protobuf 1.1安装  1.2使用...
在Word、WPS中插入AxM... 引言 我最近需要写一些文章,在排版时发现AxMath插入的公式竟然会导致行间距异常&#...
【PdgCntEditor】解... 一、问题背景 大部分的图书对应的PDF,目录中的页码并非PDF中直接索引的页码...
修复 爱普生 EPSON L4... L4151 L4153 L4156 L4158 L4163 L4165 L4166 L4168 L4...
Fluent中创建监测点 1 概述某些仿真问题,需要创建监测点,用于获取空间定点的数据࿰...
educoder数据结构与算法...                                                   ...
MySQL下载和安装(Wind... 前言:刚换了一台电脑,里面所有东西都需要重新配置,习惯了所...
MFC文件操作  MFC提供了一个文件操作的基类CFile,这个类提供了一个没有缓存的二进制格式的磁盘...