A Simple Problem with Integers(均摊复杂度线段树)

描述

传送门:2018 ACM 国际大学生程序设计竞赛上海大都会赛 - Problem H

You have $N$ integers $A_1, A_2, … , A_N$. You are asked to write a program to receive and execute two kinds of instructions:

  1. C a b means performing $A_i = (A_i^2 \mod 2018)$ for all $A_i$ such that $a ≤ i ≤ b$.
  2. Q a b means query the sum of $A_a, A_{a+1}, …, A_b$. Note that the sum is not taken modulo $2018$.

输入描述

The first line of the input is $T$($1≤ T ≤ 20$), which stands for the number of test cases you need to solve.

The first line of each test case contains $N$ ($1 ≤ N ≤ 50000$).The second line contains $N$ numbers, the initial values of $A_1, A_2, …, A_n$. $0 ≤ A_i < 2018$. The third line contains the number of operations $Q$ ($0 ≤ Q ≤ 50000$). The following $Q$ lines represents an operation having the format “C a b” or “Q a b”, which has been described above. $1 ≤ a ≤ b ≤ N$.

输出描述

For each test case, print a line “Case #t:” (without quotes, t means the index of the test case) at the beginning.
You need to answer all Q commands in order. One answer in a line.

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
8
17 239 17 239 50 234 478 43
10
Q 2 6
C 2 7
C 3 4
Q 4 7
C 5 8
Q 6 7
C 1 8
Q 2 5
Q 3 4
Q 1 8

样例输出

1
2
3
4
5
6
7
Case #1:
779
2507
952
6749
3486
9937

思路

  • $2018$这个数非常特殊,每个数平方取模最大周期是$6$。
  • 维护一个含六个数的序列的线段树。进入循环之后,每次更新相当于序列移位,可以用lazy标记维护。
  • 在进入循环之前,最多会有五次修改,所以维护一个修改次数,在区间的修改次数不足五次时暴力递归到叶子结点即可。

代码

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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 16;
const int mod = 2018;
int cnt[N << 2], sum[N << 2][6], tag[N << 2], p[N << 2];

#define lson o << 1
#define rson o << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson

inline void pushup(int o)
{
cnt[o] = min(cnt[lson], cnt[rson]);
if (cnt[o] < 5)
{
sum[o][0] = sum[lson][p[lson]] + sum[rson][p[rson]];
return;
}
p[o] = 0;
for (int i = 0; i < 6; i++)
sum[o][i] = sum[lson][(p[lson] + i) % 6] + sum[rson][(p[rson] + i) % 6];
}

inline void pushdown(int o)
{
if (!tag[o]) return;
p[lson] = (p[lson] + tag[o]) % 6, tag[lson] += tag[o];
p[rson] = (p[rson] + tag[o]) % 6, tag[rson] += tag[o];
tag[o] = 0;
}

void build(int l, int r, int o)
{
cnt[o] = p[o] = tag[o] = 0;
if (l == r)
{
scanf("%d", &sum[o][0]);
return;
}
const int m = l + r >> 1;
build(Lson);
build(Rson);
pushup(o);
}

void update(int L, int R, int l, int r, int o)
{
if (l == r)
{
cnt[o]++;
if (cnt[o] < 5)
{
sum[o][0] = sum[o][0] * sum[o][0] % mod;
return;
}
if (cnt[o] == 5)
{
p[o] == 0;
sum[o][0] = sum[o][0] * sum[o][0] % mod;
for (int i = 1; i < 6; i++) sum[o][i] = sum[o][i - 1] * sum[o][i - 1] % mod;
return;
}
(++p[o]) %= 6;
return;
}
if (L <= l && r <= R && cnt[o] >= 5)
{
tag[o]++;
(++p[o]) %= 6;
return;
}
pushdown(o);
const int m = l + r >> 1;
if (L <= m) update(L, R, Lson);
if (m < R) update(L, R, Rson);
pushup(o);
}

int query(int L, int R, int l, int r, int o)
{
if (L <= l && r <= R) return sum[o][p[o]];
pushdown(o);
const int m = l + r >> 1;
int ans = 0;
if (L <= m) ans += query(L, R, Lson);
if (m < R) ans += query(L, R, Rson);
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int T, kase = 0;
scanf("%d", &T);
while (T--)
{
int n;
scanf("%d", &n);
build(1, n, 1);
printf("Case #%d:\n", ++kase);
int q;
scanf("%d", &q);
while (q--)
{
static char op;
static int l, r;
scanf(" %c%d%d", &op, &l, &r);
if (op == 'Q') printf("%d\n", query(l, r, 1, n, 1));
if (op == 'C') update(l, r, 1, n, 1);
}
}
}
捐助作者
0%