CF_#443(Div. 1)_E

题目传送门
443的D的思路非常的新奇呀,将数的大小关系用二进制位表示了出来

题意:给你一个长度为$n$的序列$a$和$q$次询问,每次询问一个区间$[l,r]$,将这个区间提出来,执行以下操作:对于相邻两个数字$x,y$,删除$y$并将$x$替换为$x+2y$,问最后剩下的那个数最大为多少,答案模$1e9+7$
分析: $ans = \sum_{i=0}^{m}a_{l+i}2^{k_{i}}$,除了$k_{0}=0$,这个$k$序列是由一些从$1$开始的连续自然数串组成的,例如$1,2,3 \dots 1,2 \dots$,如果我们能找出这些$1$的位置,那么答案就很好求了.
我们通过枚举后缀来求$1$的位置,考虑一段区间,如果$\sum_{i=l}^{r}a_{i}2^{l - i}$大于$2e9$,那么不管前面的数是什么,该值都会变大,它的$1$的位置应该为$0$,若这个和小于$0$,那么$1$的位置就是$l-1$.
对于一段长度为$m$区间,$1$的个数最多为$m$个,所以我们需要使用倍增来维护向前跳了$2^{k}$个$1$之后的位置.
感觉自己都不知道自己在讲些什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//created by missever
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int add(int x,int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int mul(int x,int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int a[maxn],s[maxn],p[maxn],inv[maxn];
int f[maxn][20],d[maxn][20];
int main(){
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int n,q,i,j,l,r;
scanf("%d%d",&n,&q);
for(i = p[0] = inv[0] = 1;i <= n; i++) {
scanf("%d",&a[i]);
inv[i] = mul(inv[i - 1],500000004);
p[i] = mul(p[i - 1],2);
s[i] = add(s[i - 1],mul(mod + a[i],p[i]));
}
for(i = 1;i <= n; i++) {
LL x = 0;
for(j = i;j > 0; j--) {
x = (x * 2 + a[j]);
if(x <= 0) {
f[i][0] = j - 1;
d[i][0] = add(0,mod + x * 2 % mod);
break;
}
if(x > 2000000000) {
f[i][0] = -1;
break;
}
}
}
for(j = 1;j < 18; j++) {
for(i = 1;i <= n; i++) {
if(f[i][j - 1] == -1) f[i][j] = -1;
else {
f[i][j] = f[f[i][j - 1]][j - 1];
d[i][j] = add(d[i][j - 1],d[f[i][j - 1]][j - 1]);
}
}
}
while(q--) {
scanf("%d%d",&l,&r);
int ans = 0;
for(i = 17;i >= 0; i--) {
if(f[r][i] > l) {
ans = add(ans,d[r][i]);
r = f[r][i];
}
}
if(r >= l) ans = add(ans,mul(add(s[r],mod - s[l - 1]),inv[l]));
printf("%d\n",ans);
}
return 0;
}