题目:
https://codeforces.com/group/d3FEQxSUNi/contest/335515/problem/F
思路:
从后往前推
用long long 时注意有的不要习惯性写成int
#include<stdio.h> using namespace std; const int maxn=1e5+4; long long a[maxn],s[maxn],b[maxn]; int n,w; int main() { int t; int l,r; scanf("%d",&t); while(t--) { s[0]=0; scanf("%d %d",&n,&w); for(int i=1;i<=n;i++) {scanf("%lld",&a[i]); long long te=a[i]; int r=0; while(te>1) { /*if(te%2==1) r++; te/=2; if(te>0) r++; */ if(te%2==1) { te--; r++; } else { te/=2; r++; } } b[i]=r; } for(int i=1;i<=n;i++) { s[i]=s[i-1]+b[i]; } while(w--) { scanf("%d %d",&l,&r); printf("%lld\n",s[r]-s[l-1]); } } }