当前位置：首页 > news >正文

打卡信奥刷题（3255）用C++实现信奥题 P8618 [蓝桥杯 2014 国 B] Log 大侠

news 2026/5/13 17:29:54

P8618 [蓝桥杯 2014 国 B] Log 大侠

题目描述

atm 参加了速算训练班，经过刻苦修炼，对以222为底的对数算得飞快，人称 Log 大侠。

一天，Log 大侠的好友 drd 有一些整数序列需要变换，Log 大侠正好施展法力。

变换的规则是：对其某个子序列的每个整数变为[log⁡2(x)+1][\log_2(x)+1][log2(x)+1]其中 [] 表示向下取整，就是对每个数字求以222为底的对数，然后取下整。

例如对序列3,4,23,4,23,4,2操作一次后，这个序列会变成2,3,22,3,22,3,2。

drd 需要知道，每次这样操作后，序列的和是多少。

输入格式

第一行两个正整数n,mn,mn,m。

第二行nnn个数，表示整数序列，都是正数。

接下来mmm行，每行两个数LLL，RRR表示 atm 这次操作的是区间[L,R][L,R][L,R]，数列序号从111开始。

输出格式

输出mmm行，依次表示 atm 每做完一个操作后，整个序列的和。

输入输出样例 #1

输入 #1

3 3 5 6 4 1 2 2 3 1 3

输出 #1

10 8 6

说明/提示

对于30%30\%30%的数据，n,m≤103n,m \le 10^3n,m≤103。

对于100%100\%100%的数据，n,m≤105n,m \le 10^5n,m≤105。

时限 1 秒, 256M。蓝桥杯 2014 年第五届国赛

官方数据似乎有错。重造数据按照1≤ai≤1091 \leq a_i \leq 10^91≤ai≤109设计。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;intval[N<<2],n,m,a[N];longlongsum;inlinevoidbuild(intp,intl,intr){if(l==r){val[p]=a[l];return;}intmid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid+1,r);val[p]=max(val[p<<1],val[p<<1|1]);}inlinevoidmodify(intp,intl,intr,intL,intR){if(val[p]<=2)return;if(l==r){intnval=(int)(log2(val[p])+1);sum-=(val[p]-nval);val[p]=nval;return;}intmid=(l+r)>>1;if(L<=mid)modify(p<<1,l,mid,L,R);if(R>mid)modify(p<<1|1,mid+1,r,L,R);val[p]=max(val[p<<1],val[p<<1|1]);}signedmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;i++){scanf("%d",&a[i]);sum+=a[i];}build(1,1,n);for(inti=1;i<=m;i++){intl,r;scanf("%d%d",&l,&r);modify(1,1,n,l,r);printf("%lld\n",sum);}return0;}