2019-1-23 尔

Posted on |

problem

给一个长度为n的序列。

支持两个操作

1.给区间[L，R]第i项加上斐波那契数列的第i项。

2.查询区间[L，R]的异或和。

$n,m<3e5$

solution

这一题其实要考虑Fibonacci数列的两个性质:

(i) $\sum_{i=1}^{n} fib(i)=fib(n+2)−1$

(ii)令$Si=S{i−1}+S_{i−2}$,

其中$S_1=a,S_2=b$

那么$S_i=bFib(i−1)+aFib(i−2)$

还有一个推导式$\sum_{i=1}^{n} S(i)=S(n+2)−S_2$

那么就很好做了， 在线段树中， 我们要只要记数列的前两项就可以方便的对数列进行求和。

然后用一个标记永久化的线段树做一下就可以了。

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
	int sum = 0, fg = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
	for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
	return fg * sum;
}

const int Maxn = 3e5 + 10;
const int mod = 1e9 + 7;
bool ok;
inline int add(int A,int B){ 
	if(A + B >= mod) return A + B - mod;
	if(A + B < 0) return A + B + mod;
	return A + B;
}
struct STR{
	int s1, s2, len, sum;
	STR operator + (const STR &t) const{
		if(len == 1) return (STR){add(s1 , t.s1), s2, len, sum};
		return (STR){add(s1 , t.s1), add(s2 , t.s2), len, sum};
	}
}tre[Maxn << 2];
int fib[Maxn << 2], sum[Maxn], ls[Maxn << 2], rs[Maxn << 2], cnt;
inline int Sum(int l ,int r) { return add(sum[r], mod - sum[l - 1]);}
inline int Fib(int l,int r){
	return add(fib[r + 2], mod - fib[l + 1]);
}
inline void init(int n){
	fib[1] = 1;fib[2] = 1;
	for (int i = 3; i <= (n << 1); ++i) fib[i] = add(fib[i - 1], fib[i - 2]);
}
inline int calc(STR &t,int L, int R){
	if(t.s1 == 0 && t.s2 == 0) return 0;
	if(L > R) return 0;
	if(L == R) return t.s1;
	if(L + 1 == R) return add(t.s1, t.s2);
	return add(add(1ll * t.s2 * fib[R - L + 2] % mod ,mod - t.s2), 1ll * t.s1 * fib[R - L + 1] % mod);
}
inline int Sib(STR &t,int L, int R, int B){
	int S_R = calc(t, B, R);
	int S_L = calc(t, B, L - 1);
	return S_R - S_L;
}
inline void modify(int &rt, int l, int r, int L, int R, int B){
	if(!rt) rt = ++cnt;
	if(l == L && r == R) {
		tre[rt].len = r - l + 1;
		tre[rt] = tre[rt] + (STR){fib[B],fib[B + 1],tre[rt].len,tre[rt].sum};
		return;
	}
	int mid = l + r >> 1;
	if(mid >= R) modify(ls[rt], l, mid, L, R, B);
	else if(mid < L) modify(rs[rt], mid + 1, r, L, R, B);
	else modify(ls[rt], l, mid, L, mid, B),modify(rs[rt], mid + 1, r, mid + 1, R, B + mid - L + 1);
	tre[rt].sum = add(tre[rt].sum, Fib(B, R - L + B));
}
inline int Query(int rt,int l,int r,int L,int R){
	if(!rt) return 0;
	int cur = Sib(tre[rt],L,R,l);
	if(l == L && r == R) return add(tre[rt].sum, cur);
	int mid = l + r >> 1;
	if(mid >= R) return add(Query(ls[rt], l, mid, L, R), cur);
	else if(mid < L) return add(Query(rs[rt], mid + 1, r, L, R), cur);
	else return add(add(Query(ls[rt], l, mid, L, mid), Query(rs[rt], mid + 1, r, mid + 1, R)), cur);
}
int main() {
	freopen("you.in", "r", stdin);
	freopen("you.out", "w", stdout);
	int n = read(), m = read();
	for (int i = 1; i <= n; ++i)
		sum[i] = add(sum[i - 1], read() % mod);
	init(n);
	int opt, l, r;
	int root = 0;
	while(m--){
		opt = read() - 1, l = read(), r = read();
		if(!opt) {
			modify(root, 1, n, l, r, 1);
		}
		else printf("%d\n",add(Sum(l,r), Query(1, 1, n, l, r)));
	}
	return 0;
}