解题思路:
既能实现数组的二分查找,又能实现链表的O(1)删除,原来是map。
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int> M;
map<int,int>::iterator it,it2;
int getPow(int x){
static ll Pow[33],op=-1;
if(op==-1){
Pow[0]=1;
for(int i=1;i<32;i++){
Pow[i]=Pow[i-1]<<1;
}
op=1;
}
return upper_bound(Pow,Pow+31,x)-Pow;
}
int main()
{
int n,m,x;
ll sum=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&x);
sum+=x;
M[i]=x;
}
int l,r;
for(int i=1;i<=m;i++){
scanf("%d%d",&l,&r);
for(it=M.lower_bound(l);it!=M.end()&&it->first<=r;){
x=getPow(it->second);
sum-=it->second-x;
it->second=x;
if(x<=2){
it2=it;
it++;
M.erase(it2);
}else{
it++;
}
}
printf("%lld\n",sum);
}
return 0;
}
0.0分
0 人评分
最小公倍数 (C语言代码)浏览:863 |
C语言训练-大、小写问题 (C语言代码)浏览:613 |
WU-字符串比较 (C++代码)浏览:756 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:585 |
1012题解浏览:869 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:486 |
大家好,我是验题君浏览:577 |
DNA (C语言代码)浏览:749 |
C语言训练-大、小写问题 (C语言代码)浏览:681 |
拆分位数 (C语言代码)浏览:521 |