蓝桥杯2014年第五届真题-Log大侠 （C++代码）

解题思路:
既能实现数组的二分查找，又能实现链表的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;

}