换个角度思考【牛客tracker 每日一题】

换个角度思考时间限制1秒 空间限制256M知识点线段树网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个序列有多次询问每次查询区间里小于等于某个数的元素的个数即对于询问( l , r , x ) (l,r,x)(l,r,x)你需要输出∑ i l r [ a i ≤ x ] ∑_{il}^r[a_i≤x]∑ilr​[ai​≤x]的值其中[ e x p ] [exp][exp]是一个函数它返回1 11当且仅当e x p expexp成立其中e x p expexp表示某个表达式输入描述第一行两个整数n , m n,mn,m第二行n nn个整数表示序列a aa的元素序列下标从1 11开始标号保证1 ≤ a i ≤ 10 5 1 ≤ a_i ≤ 10^51≤ai​≤105之后有m mm行每行三个整数( l , r , k ) (l,r,k)(l,r,k)保证1 ≤ l ≤ r ≤ n 1 ≤ l ≤ r ≤ n1≤l≤r≤n且1 ≤ k ≤ 10 5 1 ≤ k ≤ 10^51≤k≤105输出描述对于每一个询问输出一个整数表示答案后回车示例1输入5 1 1 2 3 4 5 1 5 3输出3备注数据范围1 ≤ n ≤ 10 5 1 ≤ n ≤ 10^51≤n≤1051 ≤ m ≤ 10 5 1 ≤ m ≤ 10^51≤m≤105解题思路本题为静态区间计数问题核心采用离线处理 树状数组求解高效适配n , m ≤ 10 5 n,m≤10^5n,m≤105的大数据规模。利用前缀和差分思想将区间查询( l , r , x ) (l,r,x)(l,r,x)拆分为前r rr个元素中≤ x \le x≤x的数量 减去 前l − 1 l-1l−1个元素中≤ x \le x≤x的数量把区间问题转化为前缀问题。将所有元素位置与拆分后的查询按下标升序排序遍历过程中用树状数组动态维护权值的出现次数查询时直接计算权值前缀和即可得到对应数量。算法时间复杂度为O ( ( n m ) log ⁡ W ) O((nm)\log W)O((nm)logW)W WW为元素最大值简洁高效。总结核心逻辑将区间计数转化为前缀计数离线排序后用树状数组完成权值统计与查询。关键操作查询差分拆分、下标排序、树状数组单点更新前缀和查询。效率保障线性遍历配合对数级操作完美处理百万级数据性能优于在线线段树。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll INF1e18;constll M1e610;constll mod998244353;ll n,m,P,A[N],T[N],AN[N];structnd{ll i,k,f,id;}Q[N];voidadd(ll x){for(;xN;xx-x)T[x];}llask(ll x){ll res0;for(;x0;x-x-x)resT[x];returnres;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;in;i)cinA[i];for(ll i1,l,r,k;im;i){cinlrk;l--;Q[P]{l,k,-1,i};Q[P]{r,k,1,i};}sort(Q1,Q1P,[](ndx,ndy)-bool{returnx.iy.i;});for(ll i1,r0;iP;i){while(rQ[i].i)r,add(A[r]);AN[Q[i].id]Q[i].f*ask(Q[i].k);}for(ll i1;im;i)coutAN[i]\n;return0;}