CF438D The Child and Sequence
The and sequence child
2023-09-27 14:28:12 时间
一、题目大意
给你一个序列,你要在这个序列上进行操作。
-
操作\(1\)
给定区间\([l,r]\),对序列中这个区间中每个数字累加求和。 -
操作\(2\)
给定区间\([l,r]\) 和 \(x\),对区间每个数字对\(x\)取模。 -
操作\(3\)
给定两个数\(i,k\),将\(a[i]\)的值修改为\(k\)。
二、思路
注意到\(m = 1e5\),所以整体时间复杂度\(O(nlog n)\),也就是说你的所有操作时间复杂度不超过\(O(log n)\)才过通过这个题。
注意到区间求和,单点操作用线段树都可以在\(O(log n)\)做到,唯一有难度的就是操作对区间所有数取模。
首先考虑一个小小的剪枝,如果某个区间里面的最大数都\(<x\),那么这个区间不用管了,也就是说对于区间内的每个数\(x\),对它取模,这个数至少会减低\(x/2\),那么我们每次对这个数进行取模,这个数到\(0\)的时间复杂度也无非就是\(O(logx)\),所以整体时间复杂度\(O(mlogmlogx)\),带两个\(log\)是可以过这道题的。
三、实现代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
int n, m;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
struct Node {
int l, r;
LL sum, max;
} tr[N << 2];
void pushup(int u) {
tr[u].sum = tr[ls].sum + tr[rs].sum;
tr[u].max = max(tr[ls].max, tr[rs].max);
}
void build(int u, int l, int r) {
tr[u] = {l, r, 0, 0};
if (l == r) {
tr[u].max = tr[u].sum = a[l];
return;
}
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int c) {
if (tr[u].l > x || tr[u].r < x) return;
if (tr[u].l == tr[u].r) {
tr[u].sum = tr[u].max = c;
return;
}
modify(ls, x, c), modify(rs, x, c);
pushup(u);
}
void modify(int u, int l, int r, int x) {
if (tr[u].l > r || tr[u].r < l) return;
if (tr[u].max < x) return; //剪枝
if (tr[u].l == tr[u].r) {
tr[u].sum %= x;
tr[u].max = tr[u].sum;
return;
}
modify(ls, l, r, x), modify(rs, l, r, x);
pushup(u);
}
LL query(int u, int l, int r) {
if (tr[u].l > r || tr[u].r < l) return 0;
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
return query(ls, l, r) + query(rs, l, r);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
build(1, 1, n);
int l, r, k, x;
while (m--) {
int op;
cin >> op;
if (op == 1) {
cin >> l >> r;
printf("%lld\n", query(1, l, r));
}
if (op == 2) {
cin >> l >> r >> x;
modify(1, l, r, x);
}
if (op == 3) {
cin >> k >> x;
modify(1, k, x);
}
}
return 0;
}
相关文章
- What's the difference between {% tag variable%} and {{variable}}
- Resolve the conflict between docker and VMWare-ITworkman
- Commerce Implements New Export Controls on Advanced Computing and Semiconductor Manufacturing Items to the People’s Republic of China (PRC)
- Security headers quick reference Learn more about headers that can keep your site safe and quickly look up the most important details.
- What is the difference between DSA and RSA?
- What is the difference between the template method and the strategy patterns?
- Updates to the Git Commit Graph Feature
- Unable to access the IIS metabase
- What is the difference between Web Farm and Web Garden?
- T4 Templates and the Entity Framework
- The 18th Zhejiang Provincial Collegiate Programming Contest
- The 13th Chinese Northeast Collegiate Programming Contest
- The Geometry has no Z values 解决办法
- 【BZOJ4800】[Ceoi2015]Ice Hockey World Championship Meet in the Middle
- xtu read problem training 3 A - The Child and Homework
- All Aboard, Part 1: The -march, -mabi, and -mtune arguments to RISC-V Compilers
- CodeForces 743B Chloe and the sequence (递归)
- HDU 4489 The King’s Ups and Downs (DP+数学计数)
- [geeksforgeeks] Count the number of occurrences in a sorted array
- evo: Python package for the evaluation of odometry and SLAM
- Forking and Executing the Process
- The Binder Architecture
- Mongoose: `findOneAndUpdate()` and `findOneAndDelete()` without the `useFindAndModify
- Graph Databases—The NOSQL Phenomenon阅读笔记
- Codeforces Round #250 (Div. 1) D. The Child and Sequence
- Field [_id] is a metadata field and cannot be added inside a document. Use the index API request parameters--转