盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5152 A Strange Problem(线段树+数论)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5152

题意

某天你收到了一个信封,信封里是一个奇怪的题目。首先给你一个长度为N的序列,序列为A1,A2,…,AN.然后有M个操作,每个操作为以下三种操作的其中一个:

  1. 输出操作。给你l,r,输出区间和。
  2. 修改操作。给你x,把Ax修改为2^Ax
  3. 加法操作。给你l,r,x,区间加上​​x
    由于输出操作的结果可能很大,输出结果对2333333取模。

思路

这道题复杂就是操作2。需要补充一个知识
指数循环节:当x >= Phi(C)时, A^x = A ^ (x%Phi(C) + Phi(C)) (mod C). Phi(C)是C的欧拉函数,
对于2333333这个模数来说,求18次欧拉函数后就变成了1,所以只需要保存19层第三次操作的加数即可,然后就直接是线段树区间更新和询问操作了
参考题解写的代码,主要是计算操作二的时候,用一个vector记录某一位置操作二的个数,其实只需要记录最后的19个操作即可。具体细节见代码

代码

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1 | 1
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int mod = 2333333;
const int N = 50005;
int mo[20] = {2333333, 2196720, 580608, 165888, 55296, 18432, 6144, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1};
int pow2[33];
vector<ll> vt[N];
ll mark[N << 2];
int len[N << 2], sum[N << 2];
int n, m;
inline void add(int &x, int y) {
x += y;
if (x >= mod) x -= mod;
}
void up(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
add(sum[rt], 0);
}
void down(int rt) {
if (mark[rt]) {
mark[rt << 1] += mark[rt];
mark[rt << 1 | 1] += mark[rt];
add(sum[rt << 1], 1LL * len[rt << 1] * mark[rt] % mod);
add(sum[rt << 1 | 1], 1LL * len[rt << 1 | 1] * mark[rt] % mod);
mark[rt] = 0;
}
}
void build(int l, int r, int rt) {
mark[rt] = 0;
len[rt] = r - l + 1;
if (l == r) {
int x;
scanf("%d", &x);
vt[l].clear();
vt[l].pb(x);
sum[rt] = x % mod;
return ;
}
int m = l + r >> 1;
build(lson);
build(rson);
up(rt);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return sum[rt];
down(rt);
int m = l + r >> 1, ret = 0;
if (L <= m) add(ret, query(L, R, lson));
if (R > m) add(ret, query(L, R, rson));
up(rt);
return ret;
}
void update(int L, int R, int v, int l, int r, int rt) {
if (L <= l && r <= R) {
mark[rt] += v;
add(sum[rt], 1LL * len[rt] * v % mod);
return ;
}
down(rt);
int m = l + r >> 1;
if (L <= m) update(L, R, v, lson);
if (R > m) update(L, R, v, rson);
up(rt);
}
int pow_mod(int x, int n, int mod) {
int ret = 1;
while(n) {
if (n & 1) ret = 1LL * ret * x % mod;
x = 1LL * x * x % mod;
n >>= 1;
}
return ret;
}
int cal(vector<ll> &v) {
if (v.size() < 19) {
int pos = v.size() - 1;
ll ret = v[0];
bool flag = false;
if (v[0] >= mo[pos]) {
flag = true;
ret = ret % mo[pos] + mo[pos];
}
pos--;
for (int i = 1; i < v.size(); i++) {
if (flag) {
ret = (pow_mod(2, ret, mo[pos]) + v[i]) % mo[pos] + mo[pos];
} else {
if (ret >= 30 || pow2[ret] >= mo[pos]) {
flag = true;
ret = (pow_mod(2, ret, mo[pos]) + v[i]) % mo[pos] + mo[pos];
} else {
ret = pow2[ret] + v[i];
if (ret >= mo[pos]) {
flag = true;
ret = ret % mo[pos] + mo[pos];
}
}
}
pos--;
}
return ret % mod;
} else {
ll ret = 1;
int pos = 17;
for (int i = v.size() - 18; i < v.size(); i++) {
ret = (pow_mod(2, ret, mo[pos]) + v[i]) % mo[pos] + mo[pos];
pos--;
}
return ret % mod;
}
}
void modify(int x, int l, int r, int rt) {
if (l == r) {
if (mark[rt]) {
vt[l][vt[l].size() - 1] += mark[rt];
mark[rt] = 0;
}
vt[l].pb(0);
sum[rt] = cal(vt[l]);
return ;
}
down(rt);
int m = l + r >> 1;
if (x <= m) modify(x, lson);
else modify(x, rson);
up(rt);
}
int main () {
pow2[0] = 1;
for (int i = 1; i <= 30; i++) pow2[i] = pow2[i - 1] << 1;
int op, l, r, x;
while(~scanf("%d%d", &n, &m)) {
build(1, n, 1);
while(m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r, 1, n, 1));
}else if (op == 2) {
scanf("%d", &x);
modify(x, 1, n, 1);
} else {
scanf("%d%d%d", &l, &r, &x);
update(l, r, x, 1, n, 1);
}
}
}
return 0;
}