CF438D The Child and Sequence
2024-09-07 04:48:11
外国人的数据结构题真耿直
唯一有难度的操作就是区间取模,然而这个东西可以暴力弄一下,因为一个数$x$被取模不会超过$logn$次。
证明如下(假设$x Mod y$):
如果$y \leq \frac{x}{2}$那么$x$取模之后会小于$\frac{x}{2}$,而如果$y > \frac{x}{2}$时,$x$取模之后一定也会小于$\frac{x}{2}$
然后就暴力一个一个取过去就好了,还有一个算是剪枝的优化,我们可以顺便维护一下区间最大值,如果区间最大值都小于当前的模数的话,那么就直接$return$好了。
仍然不会算时间复杂度。
丢个模板。
Code:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const int N = 1e5 + ; int n, qn;
ll a[N]; template <typename T>
inline void read(T &X) {
X = ;
char ch = ;
T op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline ll max(ll x, ll y) {
return x > y ? x : y;
} namespace SegT {
ll s[N << ], maxn[N << ]; #define lc p << 1
#define rc p << 1 | 1
#define mid ((l + r) >> 1) inline void up(int p) {
if(p) {
s[p] = s[lc] + s[rc];
maxn[p] = max(maxn[lc], maxn[rc]);
}
} void build(int p, int l, int r) {
if(l == r) {
s[p] = maxn[p] = a[l];
return;
} build(lc, l, mid);
build(rc, mid + , r);
up(p);
} void modify(int p, int l, int r, int x, ll v) {
if(x == l && x == r) {
s[p] = maxn[p] = v;
return;
} if(x <= mid) modify(lc, l, mid, x, v);
else modify(rc, mid + , r, x, v);
up(p);
} void doMod(int p, int l, int r, int x, int y, ll v) {
if(maxn[p] < v) return;
if(l == r) {
s[p] %= v, maxn[p] %= v;
return;
} if(x <= mid) doMod(lc, l, mid, x, y, v);
if(y > mid) doMod(rc, mid + , r, x, y, v);
up(p);
} ll query(int p, int l, int r, int x, int y) {
if(x <= l && y >= r) return s[p];
ll res = 0LL;
if(x <= mid) res += query(lc, l, mid, x, y);
if(y > mid) res += query(rc, mid + , r, x, y);
return res;
} } using namespace SegT; int main() {
read(n), read(qn);
for(int i = ; i <= n; i++) read(a[i]); build(, , n);
for(int op, x, y; qn--; ) {
read(op);
if(op == ) read(x), read(y), printf("%lld\n", query(, , n, x, y));
if(op == ) {
read(x), read(y);
ll v; read(v);
doMod(, , n, x, y, v);
}
if(op == ) {
read(x);
ll v; read(v);
modify(, , n, x, v);
}
} return ;
}
最新文章
- [C#] C# 知识回顾 - 序列化
- Restful.Data v2.0发布,谢谢你们的支持和鼓励
- RecyclerView再封装
- Hadoop运维操作
- 理解C#值类型和引用类型
- HDU 5071 Chat(2014鞍山B,模拟)
- ###再探Makefile
- 硬盘安装RedHat Enterprise Linux 6(转载)
- 422. Valid Word Square
- CH Round #55 - Streaming #6 (NOIP模拟赛day2)
- laravel实现发送qq邮件
- React Native环境配置
- django上传excel文件
- SpringBoot+Thymeleaf问题
- python3接收、解析邮件
- Nginx 磁盘IO的优化
- CAD绘制室外台阶步骤5.4
- CentOS7 Rsync服务搭建-Rsync+Inotify架构实现实时同步
- Python学习三|列表、字典、元组、集合的特点以及类的一些定义
- c++11 委托构造