首页 > 其他分享 >7.CF438D The Child and Sequence 线段树维护区间取模

7.CF438D The Child and Sequence 线段树维护区间取模

时间:2022-10-28 10:32:24浏览次数:85  
标签:rt 取模 Sequence int update tree mid cin CF438D


7.CF438D The Child and Sequence 线段树维护区间取模


给定数列,区间查询和,区间取模,单点修改。
记录区间最大值,对于区间最大值小于模数的区间不予更新

洛谷传送门:​​CF438D The Child and Sequence - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)​

CF传送门:​​D. The Child and Sequence (codeforces.com)​

题目分析

给定数列,区间查询和,区间取模,单点修改。

记录区间最大值,对于区间最大值小于模数的区间不予更新,这样更新不会占用较多的时间。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

namespace SegTree{
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,

int tree[N << 2], maxx[N << 1], lazy[N << 1];

inline void push_up(int rt){
tree[rt] = tree[ls] + tree[rs];
maxx[rt] = std::max(maxx[ls], maxx[rs]);
}

void build(int rt, int l, int r){
if(l == r){
cin >> tree[rt], maxx[rt] = tree[rt];
return;
}
int mid = l + r >> 1;
build(lson), build(rson);
push_up(rt);
}

void update_part(int rt, int l, int r, int L, int R, int mod){
if(maxx[rt] < mod) return;
if(l == r){
tree[rt] %= mod;
maxx[rt] %= mod;
return;
}
int mid = l + r >> 1;
if(mid >= L) update_part(lson, L, R, mod);
if(mid < R) update_part(rson, L, R, mod);
push_up(rt);
}

void update_single(int rt, int l, int r, int pos, int val){
if(l == r){
tree[rt] = maxx[rt] = val;
return;
}
int mid = l + r >> 1;
if(mid >= pos) update_single(lson, pos, val);
else update_single(rson, pos, val);
push_up(rt);
}

int query(int rt, int l, int r, int L, int R){
if(l >= L && r <= R) return tree[rt];
int mid = l + r >> 1, ans = 0;
if(mid >= L) ans += query(lson, L, R);
if(mid < R) ans += query(rson, L, R);
return ans;
}
}

#define SEGRG 1, 1,

inline void solve(){
int n, m; cin >> n >> m;
SegTree::build(SEGRG);
while(m--){
int op; cin >> op;
if(op == 1){
int l, r; cin >> l >> r;
cout << SegTree::query(SEGRG, l, r) << endl;
} else if(op == 2) {
int l, r, x; cin >> l >> r >> x;
SegTree::update_part(SEGRG, l, r, x);
} else {
int k, x; cin >> k >> x;
SegTree::update_single(SEGRG, k, x);
}
}
}

signed main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout << fixed << setprecision(12);
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}


标签:rt,取模,Sequence,int,update,tree,mid,cin,CF438D
From: https://blog.51cto.com/u_12372287/5803561

相关文章

  • mysqlsequence并发
    mysql有sequence吗在该目录中创建一个小型php文件(info.php的)在浏览器中调用它。该文件将显示很多关于我们的php安装,如安装的php版本和有用的一些细节。如何用navicatpre......
  • CF438D The Child and Sequence
    题目链接:​​传送门​​区间求和,单点修改,区间取模线段树里维护一个max,取模的时候如果区间最大值小于max直接return就可以不然的话递归到叶子节点再取模有效降低复杂度不......
  • LG7521 [省选联考 2021 B 卷] 取模
    LG7521[省选联考2021B卷]取模给定\(n\)个正整数\(a_i\),请你再其中选出三个数\(i,j,k(i\neqj,i\neqk,i\neqk)\),使得\((a_i+a_j)\bmoda_k\)的值最大。复......
  • CF438D(The Child and Sequence-线段树mod x)
    维护一个区间的和,支持单点修改,区间modx考虑a>x,时,amodx<a/2,否则a=x所以暴力维护就行了#include<iostream>#include<cmath>#include<algorithm>#include<cstdio>#inclu......
  • Sequence Flow示例
    准备实践环境[root@master~]#knservicecreatesq-appender-01--imageikubernetes/appender--envMESSAGE="-HandledbySQ-01"Creatingservice'sq-appender-0......
  • SP685 SEQPAR - Partition the sequence 题解
    SP685SEQPAR-PartitionthesequenceSolution目录SP685SEQPAR-PartitionthesequenceSolution更好的阅读体验戳此进入题面SolutionCodeUPD更好的阅读体验戳此进......
  • 计算机取模运算
    一、模的概念模实际指的就是一个范围,下面摘抄自百度百科的一段话:“模”是指一个计量系统的计数范围,如过去计量粮食用的斗、时钟等。计算机也可以看成一个计量机器,因为计......
  • [Typescript] 62. Medium - Fibonacci Sequence
    Implementageneric Fibonacci<T> thattakesanumber T andreturnsitscorresponding Fibonaccinumber.Thesequencestarts:1,1,2,3,5,8,13,21,34,......
  • csu 1551: Longest Increasing Subsequence Again BIT + 思维
    预处理last[i]表示以第i个开始,的合法后缀。pre[i]表示以第i个结尾,的合法前缀。那么每一个数a[i],肯定是一个合法后缀last[i]+一个合法前缀,那么合法前缀的数字要小于a[i],并......
  • D. The Child and Sequence
    题目链接D.TheChildandSequence给定数列,区间查询和,区间取模,单点修改。\(n,m\leq10^5\)解题思路势能线段树线段树维护一个最大值\(mx\),对\(x\)取模时,当......