#include <bits/stdc++.h>
using namespace std;
const long long MOD_V = 1000000007;
const int BASE = 2 << 19;
struct segment {
// Segment stuff NEVER does modulo, calculates exactly, and is meant to figure out how big an input has to be to trigger multiplication
bool is_empty = false; // If this is set to true, the rest may be invalid
long long offset;
long long endpoint; // Never actually exceeds MOD_V, only a long long to avoid conversions
};
segment tree[2 * BASE];
segment s_identity;
segment combine(segment a, segment b) {
segment result;
if (a.is_empty || b.is_empty || a.offset > b.endpoint) {
result.is_empty = true;
}
result.offset = a.offset + b.offset;
result.endpoint = min(a.endpoint, b.endpoint - a.offset); // Combining makes segments shorter
return result;
}
bool is_ok(int input, segment s) {
return !s.is_empty && input < s.endpoint;
}
segment init_seg(long long a, long long b) {
segment result;
if (b == 1) {
result.offset = a;
result.endpoint = MOD_V - a;
result.is_empty = false;
return result;
}
if (a == 0 && b > 1) {
result.is_empty = true;
return result;
}
result.offset = a;
result.endpoint = a / (b - 1) + 1;
return result;
}
void init_tree() {
for (int i = BASE - 1; i >= 1; i--) {
tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
}
}
pair<int, long long> max_reach(int w, int querry_p, int querry_k, int interval_p, int interval_k, long long input) {
//cout << "Called max_reach with " << w << " " << querry_p << " " << querry_k << " " << interval_p << " " << interval_k << " " << input << endl;
if (querry_p == interval_p && querry_k == interval_k && is_ok(input, tree[w])) {
return {interval_k, input + tree[w].offset};
}
if (interval_p == interval_k && !is_ok(input, tree[w])) {
return {interval_p - 1, input};
}
// What if we cannot output ANYTHING? Is that handled correctly?
int sr = (interval_p + interval_k) / 2;
if (querry_p > sr) {
return max_reach(2 * w + 1, querry_p, querry_k, sr + 1, interval_k, input);
}
if (querry_k <= sr) {
return max_reach(2 * w, querry_p, querry_k, interval_p, sr, input);
}
pair<int, int> reach_l = max_reach(2*w, querry_p, sr, interval_p, sr, input);
if (reach_l.first == sr) {
return max_reach(2 * w + 1, sr + 1, querry_k, sr + 1, interval_k, reach_l.second);
}
else {
return reach_l;
}
}
long long MOD(long long x) {
if (x < 0) {
x += (((-x) / MOD_V) + 1) * MOD_V;
}
return x % MOD_V;
}
struct linear {
long long offset;
long long slope;
};
linear l_identity;
linear init_lin(long long a, long long b) {
linear result;
if (b == 1) {
result.offset = a;
result.slope = 1;
}
else {
result.offset = 0;
result.slope = b;
}
return result;
}
linear combine_l(linear a, linear b) {
linear result;
result.slope = MOD(a.slope * b.slope);
result.offset = MOD(a.offset * b.slope + b.offset);
return result;
}
long long eval(linear l, long long x) {
return MOD(l.slope * x + l.offset);
}
linear l_tree[2 * BASE];
void l_init_tree() {
for (int i = BASE - 1; i >= 1; i--) {
l_tree[i] = combine_l(l_tree[2 * i], l_tree[2 * i + 1]);
}
}
linear read_tree(int w, int querry_p, int querry_k, int interval_p, int interval_k) {
if (querry_p <= interval_p && querry_k >= interval_k) {
return l_tree[w];
}
if (querry_p > interval_k || querry_k < interval_p) {
return l_identity;
}
int sr = (interval_p + interval_k) / 2;
return combine_l(read_tree(2*w, querry_p, querry_k, interval_p, sr), read_tree(2*w+1, querry_p, querry_k, sr + 1, interval_k));
}
long long as[BASE];
long long bs[BASE];
int main() {
std::ios_base::sync_with_stdio(false);
s_identity.offset = 0;
s_identity.endpoint = MOD_V;
l_identity.offset = 0;
l_identity.slope = 1;
int n, q;
cin >> n >> q;
long long a, b;
for (int i = 0; i < BASE; i++) {
if (i < n) {
cin >> a >> b;
as[i] = a;
bs[i] = b;
tree[BASE + i] = init_seg(a, b);
l_tree[BASE + i] = init_lin(a, b);
}
else {
tree[BASE + i] = init_seg(0, 1);
l_tree[BASE + i] = init_lin(0, 1);
}
}
init_tree();
l_init_tree();
//cout << "Finished init" << endl;
int l, r;
long long x;
for (int i = 0; i < q; i++) {
cin >> x >> l >> r;
int reached_pos = l - 1;
long long partial = x;
while(reached_pos < r - 1 && partial <= MOD_V) {
pair<int, long long> aux = max_reach(1, reached_pos + 1, r - 1, 0, BASE - 1, partial);
reached_pos = aux.first;
partial = aux.second;
//cout << "After a step, got to " << reached_pos << " with output " << partial << endl;
if (reached_pos < r - 1 && partial <= MOD_V) {
if (partial * bs[reached_pos + 1] > partial + as[reached_pos + 1]) {
//cout << "Mult at " << reached_pos + 1 << " with value " << partial << endl;
partial *= bs[reached_pos + 1];
}
else {
partial += as[reached_pos + 1];
}
reached_pos++;
}
}
partial = MOD(partial);
if (reached_pos == r - 1) {
cout << partial << "\n";
}
else {
//cout << "Became big at " << reached_pos + 1 << endl;
linear lin = read_tree(1, reached_pos + 1, r - 1, 0, BASE - 1);
cout << eval(lin, partial) << "\n";
}
}
}
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 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 | #include <bits/stdc++.h> using namespace std; const long long MOD_V = 1000000007; const int BASE = 2 << 19; struct segment { // Segment stuff NEVER does modulo, calculates exactly, and is meant to figure out how big an input has to be to trigger multiplication bool is_empty = false; // If this is set to true, the rest may be invalid long long offset; long long endpoint; // Never actually exceeds MOD_V, only a long long to avoid conversions }; segment tree[2 * BASE]; segment s_identity; segment combine(segment a, segment b) { segment result; if (a.is_empty || b.is_empty || a.offset > b.endpoint) { result.is_empty = true; } result.offset = a.offset + b.offset; result.endpoint = min(a.endpoint, b.endpoint - a.offset); // Combining makes segments shorter return result; } bool is_ok(int input, segment s) { return !s.is_empty && input < s.endpoint; } segment init_seg(long long a, long long b) { segment result; if (b == 1) { result.offset = a; result.endpoint = MOD_V - a; result.is_empty = false; return result; } if (a == 0 && b > 1) { result.is_empty = true; return result; } result.offset = a; result.endpoint = a / (b - 1) + 1; return result; } void init_tree() { for (int i = BASE - 1; i >= 1; i--) { tree[i] = combine(tree[2 * i], tree[2 * i + 1]); } } pair<int, long long> max_reach(int w, int querry_p, int querry_k, int interval_p, int interval_k, long long input) { //cout << "Called max_reach with " << w << " " << querry_p << " " << querry_k << " " << interval_p << " " << interval_k << " " << input << endl; if (querry_p == interval_p && querry_k == interval_k && is_ok(input, tree[w])) { return {interval_k, input + tree[w].offset}; } if (interval_p == interval_k && !is_ok(input, tree[w])) { return {interval_p - 1, input}; } // What if we cannot output ANYTHING? Is that handled correctly? int sr = (interval_p + interval_k) / 2; if (querry_p > sr) { return max_reach(2 * w + 1, querry_p, querry_k, sr + 1, interval_k, input); } if (querry_k <= sr) { return max_reach(2 * w, querry_p, querry_k, interval_p, sr, input); } pair<int, int> reach_l = max_reach(2*w, querry_p, sr, interval_p, sr, input); if (reach_l.first == sr) { return max_reach(2 * w + 1, sr + 1, querry_k, sr + 1, interval_k, reach_l.second); } else { return reach_l; } } long long MOD(long long x) { if (x < 0) { x += (((-x) / MOD_V) + 1) * MOD_V; } return x % MOD_V; } struct linear { long long offset; long long slope; }; linear l_identity; linear init_lin(long long a, long long b) { linear result; if (b == 1) { result.offset = a; result.slope = 1; } else { result.offset = 0; result.slope = b; } return result; } linear combine_l(linear a, linear b) { linear result; result.slope = MOD(a.slope * b.slope); result.offset = MOD(a.offset * b.slope + b.offset); return result; } long long eval(linear l, long long x) { return MOD(l.slope * x + l.offset); } linear l_tree[2 * BASE]; void l_init_tree() { for (int i = BASE - 1; i >= 1; i--) { l_tree[i] = combine_l(l_tree[2 * i], l_tree[2 * i + 1]); } } linear read_tree(int w, int querry_p, int querry_k, int interval_p, int interval_k) { if (querry_p <= interval_p && querry_k >= interval_k) { return l_tree[w]; } if (querry_p > interval_k || querry_k < interval_p) { return l_identity; } int sr = (interval_p + interval_k) / 2; return combine_l(read_tree(2*w, querry_p, querry_k, interval_p, sr), read_tree(2*w+1, querry_p, querry_k, sr + 1, interval_k)); } long long as[BASE]; long long bs[BASE]; int main() { std::ios_base::sync_with_stdio(false); s_identity.offset = 0; s_identity.endpoint = MOD_V; l_identity.offset = 0; l_identity.slope = 1; int n, q; cin >> n >> q; long long a, b; for (int i = 0; i < BASE; i++) { if (i < n) { cin >> a >> b; as[i] = a; bs[i] = b; tree[BASE + i] = init_seg(a, b); l_tree[BASE + i] = init_lin(a, b); } else { tree[BASE + i] = init_seg(0, 1); l_tree[BASE + i] = init_lin(0, 1); } } init_tree(); l_init_tree(); //cout << "Finished init" << endl; int l, r; long long x; for (int i = 0; i < q; i++) { cin >> x >> l >> r; int reached_pos = l - 1; long long partial = x; while(reached_pos < r - 1 && partial <= MOD_V) { pair<int, long long> aux = max_reach(1, reached_pos + 1, r - 1, 0, BASE - 1, partial); reached_pos = aux.first; partial = aux.second; //cout << "After a step, got to " << reached_pos << " with output " << partial << endl; if (reached_pos < r - 1 && partial <= MOD_V) { if (partial * bs[reached_pos + 1] > partial + as[reached_pos + 1]) { //cout << "Mult at " << reached_pos + 1 << " with value " << partial << endl; partial *= bs[reached_pos + 1]; } else { partial += as[reached_pos + 1]; } reached_pos++; } } partial = MOD(partial); if (reached_pos == r - 1) { cout << partial << "\n"; } else { //cout << "Became big at " << reached_pos + 1 << endl; linear lin = read_tree(1, reached_pos + 1, r - 1, 0, BASE - 1); cout << eval(lin, partial) << "\n"; } } } |
English