区间增量与区间小于计数【牛客tracker 每日一题】

区间增量与区间小于计数时间限制5秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的长度为n nn的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n\}{a1​,a2​,…,an​}你需要构建一个能够动态维护区间和信息的数据结构使得其能支持区间增量将[ l , r ] [l,r][l,r]这个区间中的全部元素修改为其与一个数x xx相加后的值即∀ i ∈ [ l , r ] , a i → a i x ∀i∈[l,r],a_i→a_ix∀i∈[l,r],ai​→ai​x。区间小于计数输出下标在[ l , r ] [l,r][l,r]这个区间中的所有元素中小于一个特定的数x xx的元素的个数即∑ i l r 1 a i x ∑_{il}^r1_{a_ix}∑ilr​1ai​x​。输入描述第一行输入两个整数n , q ( 1 ≦ n , q ≦ 10 5 ) n,q(1≦n,q≦10^5)n,q(1≦n,q≦105)代表数组中的元素数量、操作次数。第二行输入n nn个整数a 1 , a 2 , … , a n ( − 10 7 ≦ a i ≦ 10 7 ) a_1,a_2,…,a_n(−10^7≦a_i≦10^7)a1​,a2​,…,an​(−107≦ai​≦107)代表初始数组。此后q qq行每行先输入一个整数o p ( 1 ≦ o p ≦ 2 ) op(1≦op≦2)op(1≦op≦2)代表操作编号随后在同一行若o p 1 op1op1输入三个整数l , r , x ( 1 ≦ l ≦ r ≦ n ; − 10 7 ≦ x ≦ 10 7 ) l,r,x(1≦l≦r≦n; −10^7≦x≦10^7)l,r,x(1≦l≦r≦n;−107≦x≦107)代表区间增量若o p 2 op2op2输入三个整数l , r , x ( 1 ≦ l ≦ r ≦ n ; − 10 9 ≦ x ≦ 10 9 ) l,r,x(1≦l≦r≦n; −10^9≦x≦10^9)l,r,x(1≦l≦r≦n;−109≦x≦109)代表区间小于计数输出描述对于每一次区间小于计数询问新起一行输出一个整数代表答案。数据保证至少存在一次询问。示例1输入6 2 1 1 4 5 1 4 1 2 4 2 2 1 6 5输出4示例2输入5 7 1 3 2 7 9 1 1 2 1 1 2 5 -3 2 1 5 4 2 2 3 5 1 4 5 -1 2 4 4 4 2 1 5 -2输出3 2 1 0解题思路本题核心是通过暴力遍历实现区间增量和区间小于计数操作首先读取数组和操作次数初始化数组后逐次处理每个操作若为区间增量操作o p 1 op1op1直接遍历[ l , r ] [l,r][l,r]区间将每个元素累加x xx若为区间小于计数操作o p 2 op2op2遍历[ l , r ] [l,r][l,r]区间逐个判断元素是否小于x xx并统计数量输出结果。该方法逻辑简单直接无需复杂数据结构仅通过基础的区间遍历完成操作。但需注意暴力解法的时间复杂度为O ( q × n ) O(q×n)O(q×n)在n 、 q n、qn、q均为1 e 5 1e51e5时会因时间超限无法通过仅适用于理解基础逻辑实际需采用线段树带懒标记离散化或分块等高效数据结构优化。总结核心逻辑暴力遍历操作指定区间o p 1 op1op1时执行区间元素增量o p 2 op2op2时统计区间内小于x xx的元素数。关键操作按操作类型遍历[ l , r ] [l,r][l,r]区间完成元素增量或计数逻辑输出计数结果。效率说明暴力解法时间复杂度O ( q n ) O(qn)O(qn)仅适配小规模测试用例1 e 5 1e51e5规模需线段树/分块优化以降低时间复杂度。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll mod1e97;constll INF1e18;ll a[N];intmain(){ll n,q;cinnq;for(ll i1;in;i)cina[i];while(q--){ll op,l,r,x;cinoplrx;if(op1){for(ll il;ir;i)a[i]x;continue;}ll res0;for(ll il;ir;i){if(a[i]x)res;}coutresendl;}return0;}