ACGO Qualifying Tournament #13 - Topic Explanation
Thank you to everyone who participated in this qualifying tournament!
T1 - Epochal Meteor Shower
Title Link Jump:click to jump
It's also not particularly difficult to manually simulate.
Procedure for solving the problem
- Start by calculating the day the person first saw a meteor shower in his or her lifetime:\((E + B) \mod 50\)。
- Calculate the number of years remaining to see a meteor shower in your lifetime\(Y\)。
- The answer.\(\dfrac{Y}{50} + 1\)。
code implementation
The C++ code for this question is as follows:
#include <iostream>
using namespace std;
int solve(int B, int L, int E) {
int age_at_first_shower = (E + B) % 50;
if (age_at_first_shower > L) return 0;
int years_from_first_shower =
L - age_at_first_shower;
return years_from_first_shower / 50 + 1;
}
int main() {
int T; cin >> T;
for (int i = 0; i < T; i++) {
int B, L, E;
cin >> B >> L >> E;
cout << solve(B, L, E) << '\n';
}
return 0;
}
The Python code for this question is as follows:
T = int(input())
for _ in range(T):
B, L, E = map(int, input().split(' '))
before = B + E
after = L - before
print(before//50 + after//50 + 1)
T2 - MARCOncatenate
Title Link Jump:click to jump
Just simulate according to the topic, it's not that difficult.
code implementation
The C++ code for this question is as follows:
#include <iostream>
#include <string>
using namespace std;
string marco = "marco";
string capmarco = "MARCO";
string solve(string S) {
int i = 0;
int max = 0;
for (int i = 1; i <= min(5, int(())); ++i) {
if ((5 - i, i) == (0, i)) {
max = i;
}
}
if (max == 0) {
return S;
} else {
return capmarco + (max, int(()) - max);
}
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
string S;
cin >> S;
cout << solve(S) << '\n';
}
return 0;
}
The Python code for this question is as follows:
def solve(S: str) -> str:
marco = "MARCO"
marco_lower = "marco"
matching_count = 0
for i in range(7):
if S[0:i] == marco_lower[5 - i:]:
matching_count = i
return marco + S[matching_count:] if matching_count != 0 else S
def main():
T = int(input())
for _ in range(T):
S = input()
print(solve(S))
if __name__ == '__main__':
main()
T3 - TNT Relay
Title Link Jump:click to jump
This question was the third question of the tournament, but many of the contestants thought it was the hardest question of the tournament.
Ideas for solving the problem
-
Sliding Window: Using the sliding window technique, first in front of the\(K\) The number of air squares is calculated from the number of squares. Next, as the window slides to the right, we remove a square at the left end of the window and add a square at the right end of the window to update the number of air squares.
-
Maximum number of air cubes: we maintain a variable
mx, indicates the maximum number of air squares in the current window. -
Calculate the answer: each time you calculate the answer, use the\(K - \text{Maximum number of air cubes}\) to represent the minimum number of TNT squares, which indicates how many steps are needed to avoid the collapse of the TNT. If\(K \geq N\), indicating that the player can just jump across the entire bridge, outputs\(-1\)。
time complexity
The time complexity of processing a sequence at a time is\(O(N)\)which\(N\) is the length of the sequence of squares. The overall complexity is\(O(T \times N)\)which\(T\) is the number of test cases. Regarding the ontology, it can be further optimized with bisection. This paper does not state this too much.
code implementation
The C++ code for this question is as follows:
#include <iostream>
#include <string>
using namespace std;
int solve(int N, int K, string S) {
if (K >= N) return -1;
++K;
int mx = 0, cur = 0;
for (int i = 0; i < N; ++i) {
if (S[i] == '-') ++cur;
if (i - K >= 0 && S[i - K] == '-') --cur;
mx = max(mx, cur);
}
return K - mx;
}
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N, K;
cin >> N >> K;
string S;
cin >> S;
cout << solve(N, K, S) << '\n';
}
return 0;
}
The Python code for this question is as follows:
def solve(N: int, K: int, S: str) -> int:
if K >= N:
return -1
mx, cur = 0, 0
K += 1
for i in range(N):
if S[i] == '-':
cur += 1
if i - K >= 0 and S[i - K] == '-':
cur -= 1
mx = max(mx, cur)
return K - mx
def main():
T = int(input())
for _ in range(T):
temp = input().split()
N, K = int(temp[0]), int(temp[1])
S = input()
print(solve(N, K, S))
if __name__ == '__main__':
main()
T4 - Joker
Title Link Jump:click to jump
Ideas for solving the problem
It is also a simulation question, but the following points need to be noted:
- The same point may occur five times, then High Card should be output (as in the question).
- If there is a suit that matches more than one of the above descriptions, output the suit that was last described in the rules for the suit that matches the description.
- The number of cards is not limited to traditional playing cards, and each card can be titled in any of the four suits.
code implementation
The C++ code for this question is as follows:
#include <iostream>
#include <algorithm>
using namespace std;
int t;
struct card{
int rank;
string suit;
} cards[10];
bool cmp(card a, card b){
return < ;
}
int main(){
ios::sync_with_stdio(0);
(0); (0);
cin >> t;
while(t--){
for (int i=1; i<=5; i++){
string rank; string suit;
cin >> rank >> suit;
int act;
if (rank == "J") act = 11;
else if (rank == "Q") act = 12;
else if (rank == "K") act = 13;
else if (rank == "A") act = 14;
else if (rank == "10") act = 10;
else act = rank[0] - '0';
cards[i] = (card){act, suit};
}
sort(cards+1, cards+6, cmp);
int cnt[20] = {};
bool isSameSuit = true;
bool isRanked = true;
int pairs = 0; int greatest = 0;
for (int i=1; i<=5; i++){
cnt[cards[i].rank] += 1;
if (i > 1 && cards[i].suit != cards[i-1].suit)
isSameSuit = false;
if (i > 1 && cards[i-1].rank + 1 != cards[i].rank)
isRanked = false;
}
for (int i=1; i<=15; i++){
if (cnt[i] == 2) pairs++;
greatest = max(greatest, cnt[i]);
}
if (isRanked && isSameSuit){
if (cards[5].rank == 14) cout << "Royal Flush" << endl;
else cout << "Straight Flush" << endl;
} else if (isRanked) cout << "Straight" << endl;
else if (pairs == 1 && greatest == 3) cout << "Full House" << endl;
else if (greatest == 4) cout << "Four of a Kind" << endl;
else if (greatest == 3) cout << "Three of a Kind" << endl;
else if (pairs == 2) cout << "Two Pairs" << endl;
else if (pairs == 1) cout << "One Pair" << endl;
else cout << "High Card" << endl;
}
return 0;
}
T5 - Vertex Verse
Title Link Jump:click to jump
Simulating the situation directly is fine, but there are more details that need a bit of attention.
time complexity
included among thesework function will be called on each iteration of the\(4\) times, and the complexity of each time is\(O(E)\). Therefore, for each input\(q\) For pairs of points, the total time complexity is\(\Theta(4 \times q \times E)\)namely\(O(q \times E)\). But in the worst case, the number of edges in the graph\(E\) Approachable\(O(n \times m)\), so the total time complexity is\(O(q \times n \times m)\)。
code implementation
The C++ code for this question is as follows:
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
int n, m, q, ei;
int a, b, c, d;
int macw, alex;
struct perEdge{
int to;
int next;
} edges[2000005];
int vertex[1000005], cnt;
bool vis[1000005], memo[1000005][5], track;
inline int calc_dir(int x, int y){
if (x + 1 == y) return 1;
if (x + m == y) return 2;
if (x + m + 1 == y) return 3;
return -1;
}
void add(int v1, int v2){
ei += 1;
edges[ei].to = v2;
edges[ei].next = vertex[v1];
vertex[v1] = ei;
}
void dfs(int x, int steps, int origin, int dir){
if (steps > 4) return ;
if (steps == 4 && x == origin){
// It means that you can walk around in a circle to get to the origin。
// Determine if this ring has already been previously recorded。
if (memo[origin][dir]) return ;
memo[origin][dir] = 1;
cnt += 1;
return ;
}
for (int index = vertex[x]; index; index = edges[index].next){
int to = edges[index].to;
// Only go to points numbered larger than your own。
if (to >= origin || (to == origin && steps + 1 == 4)){
if (vis[to]) continue;
vis[to] = 1;
dfs(to, steps + 1, origin, dir);
vis[to] = 0;
}
}
}
void work(int x){
for (int index = vertex[x]; index; index = edges[index].next){
int to = edges[index].to;
if (to <= x) continue;
int dir = calc_dir(x, to);
if (dir != -1){
vis[to] = 1;
dfs(to, 1, x, dir);
vis[to] = 0;
}
}
}
int main(){
ios::sync_with_stdio(0);
(0); (0);
cin >> n >> m >> q;
for (int i=1; i<=2*q; i++){
cin >> a >> b >> c >> d;
int v1 = (a - 1) * m + b;
int v2 = (c - 1) * m + d;
add(v1, v2); add(v2, v1);
// through (a gap)v1Four steps from point.，Let's see if we can get back on track.
cnt = 0;
if (a == c){
// in the same row
work(v1); work(v2);
work(v1 - m); work(v2 - m);
} else if (b == d){
// in the same column
work(v1); work(v2);
work(v1 - 1); work(v2 - 1);
}
if (i % 2) macw += cnt / 2;
else alex += cnt / 2;
}
cout << macw << " " << alex << endl;
return 0;
}
Another way to write it is as follows:
#include <iostream>
#include <unordered_map>
#include <map>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int N = 2e5 + 10;
map<pi,map<pi,int>> dis;
int mp[2];
bool check(pi a,pi b,pi c,pi d) {
return dis[a][b] && dis[a][c] && dis[c][d] && dis[b][d];
}
int main() {
int n,m,q;
cin >> n >> m >> q;
q <<= 1;
for (int i=0;i<q;i++) {
pi a,b;
cin >> >> >> >> ;
if (a > b) swap(a,b);
dis[a][b]++;
if (dis[a][b] > 1) {
continue;
}
if ( == ) {
pi c = make_pair( + 1,);
pi d = make_pair( + 1,);
if (check(a,b,c,d)) {
mp[i%2]++;
}
pi e = make_pair( - 1,);
pi f = make_pair( - 1,);
if (check(e,f,a,b)) {
mp[i%2]++;
}
}else {
pi c = make_pair(, + 1);
pi d = make_pair(, + 1);
if (check(a,c,b,d)) {
mp[i%2]++;
}
pi e = make_pair(, - 1);
pi f = make_pair(, - 1);
if (check(e,a,f,b)) {
mp[i%2]++;
}
}
}
cout << mp[0] << " " << mp[1] << endl;
return 0;
}
T6 - Optimal Government Building Site - 2
Title Link Jump:click to jump
Ideas for solving the problem
There are so many solutions to this problem that can be written using the weighted median\(N = 10^5\)In order to take into account the plain simulated annealing algorithm, the data range of this question is appropriately lowered. If you have learned the simulated annealing algorithm doing this question is very simple, just change the evaluation function of the template to a function that calculates the degree of intention.
time complexity
The time complexity of the simulated annealing algorithm is approximately\(\Theta(k \times N)\). Among them\(k\) denotes the number of calls to the F2 function for calculating the example in the simulated annealing process.\(N\) Indicates the size of the data.
code implementation
The C++ code for this problem is as follows (simulated annealing):
#include <iostream>
#include <algorithm>
#include <cmath>
#include <random>
using namespace std;
double n;
struct apart{
double x, y;
} arr[10005];
double ei[10005];
double answ = 1e18, ansx, ansy;
double dis(double x1, double y1, double x2, double y2, int c){
return (abs(x1 - x2) + abs(y1 - y2)) * ei[c];
}
double F2(double x, double y){
double ans = 0;
for (int i=1; i<=n; i++){
ans += dis(x, y, arr[i].x, arr[i].y, i);
}
return ans;
}
void SA(){
double T = 3000, cold = 0.999, range = 1e-20;
answ = F2(ansx, ansy);
while(T > range){
double ex = ansx + (rand() * 2.0 - RAND_MAX) * T;
double ey = ansy + (rand() * 2.0 - RAND_MAX) * T;
double ea = F2(ex, ey);
double dx = ea - answ;
if (dx < 0){
ansx = ex;
ansy = ey;
answ = ea;
} else if (exp(-dx/T) * RAND_MAX > rand()){
ansx = ex;
ansy = ey;
}
T *= cold;
}
return ;
}
signed main(){
ios::sync_with_stdio(0);
(0); (0);
cin >> n;
for (int i=1; i<=n; i++) cin >> ei[i];
for (int i=1; i<=n; i++){
cin >> arr[i].x >> arr[i].y;
ansx += arr[i].x; ansy += arr[i].y;
}
ansx /= n; ansy /= n;
for (int i=1; i<=1; i++) SA();
printf("%.5lf\n", answ);
return 0;
}
C++ code using the weighted median algorithm:
#include <bits/stdc++.h>
constexpr double EPS = 1e-6;
double get_med(const std::vector<double> &a, const std::vector<int> &e) {
int n = ();
double lo = -1e3, hi = 1e3;
auto f = [&](double x) {
double sum = 0.0;
for (int i = 0; i < n; ++i)
sum += std::abs(x - a[i]) * e[i];
return sum;
};
while (hi - lo > EPS) {
double mid = (lo + hi) / 2;
if (f(mid - EPS) > f(mid) and f(mid) > f(mid + EPS))
lo = mid;
else
hi = mid;
}
return lo;
}
int main() {
int n; std::cin >> n;
std::vector<int> e(n);
for (auto &x : e) std::cin >> x;
std::vector<double> x(n), y(n);
for (int i = 0; i < n; ++i)
std::cin >> x[i] >> y[i];
double ax = get_med(x, e), ay = get_med(y, e);
double res = 0.0;
for (int i = 0; i < n; ++i)
res += (std::abs(ax - x[i]) + std::abs(ay - y[i])) * e[i];
std::cout << std::setprecision(6) << std::fixed << res << '\n';
return 0;
}
T7 - Turtle farm
Title Link Jump:click to jump
Prior knowledge:
- Understood basic dynamic programming.
- Proficiency in bitwise operations in binary.
As for why a template question was put in, the reason was because you need to get up to eight questions, and you just couldn't, so you found a moderately difficult one.
Ideas for solving problems
This is a typicaldynamic programming with state pressureQuestion. Set\(dp_{i, j}\) denotes a traversal to the first\(i\) line, the current line starts with\(j_{(base2)}\) The number of schemes that can be formed by arranging the turtles in the form of the
For each line of the program, we can represent it as a binary. For example the binary number\(10100\), indicating that there is a transverse length of\(5\) Of the sites, the first\(1, 3\) A small turtle was placed in each of the numbered positions. Thus, each placement state can be represented by a binary number. We can also iterate through each placement state in binary by iterating over it.
First, we preprocess out all the legal cases of placing turtles in the horizontal row. According to the question, two turtles cannot be placed next to each other, so in binary, there cannot be two\(1\) Adjacent. How can we preprocess out of this situation? We can use thebit operationThe methodology:
If there exists a binary number with two\(1\) adjacent to each other, then if we have a number for this\(x\) perform bitwise operations(x << 1) & x results or(x >> 1) & x The result must be greater than or equal to\(1\). We do this by excluding such cases. Also, we need to be aware that there are some grids in which turtles cannot be placed. This step can also be preprocessed out of the way by binary if the grid is in the first\(i\) A turtle cannot be placed in a grid, then when enumerating the number of all schemes directly ignore the first\(i\) bitwise\(1\) The situation will suffice.
Next, how do you make sure that the turtles in the top and bottom rows don't *? Suppose the top row is placed in the state\(y\)The current state of row placement is\(j\)Ifi & j The result is greater than or equal to\(1\)It can also be shown that there are two numbers\(1\) in the same position. So we need to exclude that as well.
In summary, we can derive the state transfer equation:\(dp_{i, j} = dp_{i, j} + dp_{i-1, k}\). Among other things.\(j\) respond in singing\(k\) Indicates all horizontal rows of legal programs. The answer is\(\mathtt{ANS} = \sum_{j=0}^{2^M-1}{dp_{N, j}}\)。
The initialization of the state is also simple, another\(dp_{0, 0} = 1\), indicating that none of the turtles are placed there is a placement option.
time complexity
By observing the above code, there are three levels of loops in enumerating all states and transferring states, which are enumerating the current row, enumerating the legal placements of the current row, and enumerating the placements of the previous row. Therefore the total time complexity is about\(O(n \times 2^M \times 2^M) = O(n \times 2^{M^2}) = O(n \times 4^M)\). However, since the number of legal placements is much less than the number of\(2^M\), so in reality the program runs much faster.
code implementation
The code for this question is implemented as follows. You need to subtract one from the output because not placing is also a legal case, and you need to exclude this legal case according to the question.
#include <iostream>
using namespace std;
const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
// All horizontal rows legal。
int terrain[505];
int ok[1050], cnt;
int dp[505][1050];
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> arr[i][j];
}
}
// Pre-processing of illegal terrain。
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
terrain[i] = (terrain[i] << 1) + !arr[i][j];
}
}
// Preprocessing out all horizontal rows of legal cases。
for (int i=0; i<(1<<m); i++){
if (((i<<1)|(i>>1)) & i) continue;
ok[++cnt] = i;
}
dp[0][1] = 1;
// enumeration。
for (int i=1; i<=n; i++){
for (int s1=1; s1<=cnt; s1++){ // enumeration当前行。
if (ok[s1] & terrain[i]) continue;
for (int s2=1; s2<=cnt; s2++){ // enumeration上一行。
if (ok[s2] & terrain[i-1]) continue;
if (ok[s1] & ok[s2]) continue;
dp[i][s1] = (dp[i][s1] + dp[i-1][s2]) % MOD;
}
}
}
// Statistical answers。
int ans = 0;
for (int i=1; i<=cnt; i++)
ans = (ans + dp[n][i]) % MOD;
cout << ans - 1 << endl;
return 0;
}
The Python code for this question is as follows. Python can pass all the test points in this question:
MOD = int(1e9 + 7)
n, m, ans = 0, 0, 0
arr = [[0] * 505 for _ in range(505)]
terrain = [0] * 505
ok = [0] * 1050
dp = [[0] * 1050 for _ in range(505)]
cnt = 0
def main():
global n, m, cnt, ans
# importation n cap (a poem) m
n, m = map(int, input().split())
# importation arr arrays
for i in range(1, n + 1):
arr[i][1:m + 1] = map(int, input().split())
# Pre-processing of illegal terrain
for i in range(1, n + 1):
for j in range(1, m + 1):
terrain[i] = (terrain[i] << 1) + (1 - arr[i][j])
# Preprocessing out all horizontal rows of legal cases
for i in range(1 << m):
if ((i << 1) | (i >> 1)) & i:
continue
cnt += 1
ok[cnt] = i
dp[0][1] = 1
# enumeration
for i in range(1, n + 1):
for s1 in range(1, cnt + 1): # enumeration当前行
if ok[s1] & terrain[i]:
continue
for s2 in range(1, cnt + 1): # enumeration上一行
if ok[s2] & terrain[i - 1]:
continue
if ok[s1] & ok[s2]:
continue
dp[i][s1] = (dp[i][s1] + dp[i - 1][s2]) % MOD
# Statistical answers
ans = 0
for i in range(1, cnt + 1):
ans = (ans + dp[n][i]) % MOD
print(ans - 1)
if __name__ == "__main__":
main()
One more violent solution is provided for counterpoise:
#include <iostream>
using namespace std;
const int MOD = 1e9+7;
int n, m, ans;
int arr[505][505];
int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};
// depth-first search Brute Force
void dfs(int x, int y){
if (x > n) {
ans += 1;
ans %= MOD;
return ;
}
if (y > m){
dfs(x+1, 1);
return ;
}
if (arr[x][y] == 0){
dfs(x, y+1);
return ;
}
// not letting go of fish
dfs(x, y+1);
// throw a fish
for (int i=0; i<4; i++){
int cx = x + dx[i];
int cy = y + dy[i];
if (cx < 1 || cy < 1 || cx > n || cy > m) continue;
if (arr[cx][cy] == 2) return ;
}
arr[x][y] = 2;
dfs(x, y+1);
arr[x][y] = 1;
return ;
}
int main(){
cin >> n >> m;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++){
cin >> arr[i][j];
}
}
// dfs discrimination
dfs(1, 1);
cout << ans-1 << endl;
return 0;
}
T8 - Data Center Energy Analysis
Title Link Jump:click to jump
This paper is intended only for players who have some knowledge of line trees and have a high level of programming skills. The prior knowledge for this paper is as follows:
- Construction and Maintenance of Line Tree - can refer to articleA Shallow Entry into Line Tree and Interval Maximum Problems。
- Middle School Math - The perfect sum of squares formula and the perfect cubic sum formula.
- Modulo - how to ensure that the result of modulo all integers is a non-negative integer - you can refer to this question in theInstructions/Hints Part.
I didn't realize when the original question came out that this question was original on many OJs, SO SAD (I'll improve it next time).
The question itself should be very easy to understand - given an array, you are asked to design a program that performs interval cubing and interval modification on the program. However, the question has a relatively large amount of data\(N, M\) Up to\(10^5\), for every modification and query is\(O(N)\) time complexity, it is clear that with a brute force approach the time complexity will definitely time out and go up to\(O(N^2 * M)\) (approximate need)\(115\) (It takes days to get a test point done). When looking at interval queries and maintenance operations, it's not hard to think of using a line tree approach, where the time complexity of a single operation is about\(O(log_2 N)\)Even when\(N\) Very large when the line tree can also be run up and down.
Ideas for solving the problem
I have to say, this is one of the nastier topics for interval maintenance in line tree. Not only is it hard to write, but the maintenance operation is quite computationally intensive. If you are not careful, you will write a crooked (so concentrate when you write this question, a slight insignificant problem is easy to explode).\(0\)）。
The main difficulty in this problem is the operation of bulk interval accumulation over an interval. It's easy to think of the connection to the perfect cube formula:\((a+b)^3 = a^3 +3a^2b + 3ab^2 + b^3\). The interval accumulation operation is also nothing more than performing that operation on all the numbers in the interval, and summing the results of all the operations is the cubic sum of the interval after the operation is performed. Simplification leads to:
To summarize, we only need to maintain three fields with the line tree, the cubic sum of intervals, the square sum of intervals, and the interval sum. The process of maintaining the sum of squares is similar to maintaining the cubic sum, according to the perfect square formula\((a+b)^2 = a^2 + 2ab + b^2\). This is obtained by accumulation and simplification:
The above three fields can be initialized together when constructing the wire tree, and each subsequent update can be directly modified with lazy markers. Everything is left to thepush_down() Function. The interval is maintained by performing a lazy marker devolution operation before each interval query and modification. The specific maintenance operations are as follows:
// rt is the parent node, l and r are the two children of rt, and len is the length of the rt node interval.
// Where (len - len / 2) is the length of the l interval and (len / 2) is the length of the r interval.
void push_down(Node &rt, Node &l, Node &r, int len){
if (){
int num = ;
// Maintain the cubic sum
l.s3 += 3 * num * l.s2 + 3 * num * num * l.s1 + (len - len / 2) * num * num * num ;{ if (){ int num = ; // Maintain cubic sum
r.s3 += 3 * num * r.s2 + 3 * num * num * r.s1 + (len / 2) * num * num * num ;
// Maintain the sum of squares
l.s2 += 2 * num * l.s1 + (len - len / 2) * num * num; // maintain the sum of squares
l.s2 += 2 * num * r.s1 + (len / 2) * num * num;
// Maintain the interval sum
l.s1 += (len - len / 2) * num; r.s1 += (len - len / 2) * num; // Maintain interval sum.
r.s1 += (len / 2) * num;
// Drop the marker into the two subintervals
+= num; += num; r.s1 += (len / 2) * num
+= num.
= 0; // Clear the marker.
}
return ;
}
caveat
- Please pay attention to modeling. To ensure that your answers are correct, model the results at each step of the operation.
- write out (a prescription, check, invoice etc)
long long, otherwise you can only pass the first three test points (the questioner was still nice enough to leave three small test points to cheat the powder). - When maintaining cubic sums, square sums, and sums, note the order in which they are maintained. The cubic sum should be maintained first, then the square sum, and finally the interval sum.
- Note the size of the line tree array, which should be\(4 \times N\)。
- It is recommended to use read optimization to directly use the
cinis more efficient thanstdapproximate\(100\%\)。
time complexity
The complexity of a single query and modification of a line tree is about\(O(log_2 N)\), the time complexity of initialization is\(\Theta(N)\), so the overall time complexity of this code can be summarized by the polynomial\(\Theta(N + M \cdot log_2(N))\) to represent it, the overall time complexity of the code is then\(O(M \cdot log_2(N))\). At the limit data, the program only needs to\(160ms\) It would be enough to do the work required for a full year of violence.
code implementation
- The code uses macro definitions for easy tuning at a later stage.
- The following code is not much different from a normal line tree, but focus on the
push_down()Decentralized operations.
#include <iostream>;
#include <algorithm>;
using namespace std.
const int N = 1e5 + 5; const int MOD = 1e9 + 7; #include <algorithm>
const int MOD = 1e9 + 7; // Macro definitions: lc and rc.
// Macro definitions: lc and rc are the indexes of the left and right sons in the array, respectively.
#define lc root << 1
#define rc root << 1 | 1
#define int long long
int n, m, k, x, y, v.
struct Node {
// Sum, sum of squares, and sum of cubes, respectively.
int s1, s2, s3.
int tag; } tree[N <<
} tree[N << 2].
// Merge intervals by simply adding the two subintervals.
void push_up(int root) {
tree[root].s1 = (tree[lc].s1 + tree[rc].s1) % MOD;
tree[root].s2 = (tree[lc].s2 + tree[rc].s2) % MOD; tree[root].s3 = (tree[lc].s2 + tree[rc].s2)
return.
}
// The devolution operation is indeed code-heavy. You need to be a bit more careful when drawing on it.
void push_down(Node &rt, Node &l, Node &r, int len) {
if () {
int num = ;
l.s3 = (l.s3 + 3 * num % MOD * l.s2 % MOD + 3 * num % MOD * num % MOD * l.s1 % MOD + (len - len / 2) * num % MOD * num % MOD * num % MOD) % MOD; l.s3 = (l.s3 + 3 * num % MOD * l.s2 % MOD + 3 * num % MOD % MOD * num % MOD)
l.s3 = (l.s3 + MOD) % MOD; r.s3 = (r.s3 + MOD) % MOD; r.s3 = (r.s3 + MOD)
r.s3 = (r.s3 + 3 * num % MOD * r.s2 % MOD + 3 * num % MOD * num % MOD * r.s1 % MOD + (len / 2) * num % MOD * num % MOD * num % MOD) % MOD;
r.s3 = (r.s3 + MOD) % MOD.
l.s2 = (l.s2 + MOD) % MOD; r.s2 = (r.s2 + MOD) % MOD; r.s2 = (r.s2 + MOD)
r.s2 = (r.s2 + 2 * num % MOD * r.s1 % MOD + (len / 2) * num % MOD * num % MOD) % MOD;
r.s2 = (r.s2 + MOD) % MOD;
l.s1 = (l.s1 + MOD) % MOD; r.s1 = (r.s2 + MOD)
r.s1 = (r.s1 + (len / 2) * num % MOD) % MOD; r.s1 = (r.s1 + (len / 2) * num % MOD) % MOD; r.s1 = (r.s1 + (len / 2) * num % MOD)
r.s1 = (r.s1 + MOD) % MOD; r.s1 = (r.s1 + (len / 2) * num % MOD) % MOD.
r.s1 = (r.s1 + MOD) % MOD; = ( + num) % MOD; = ( + MOD)
r.s1 = (r.s1 + MOD) % MOD; = ( + num) % MOD; = ( + MOD) % MOD; = ( + MOD)
= ( + MOD) % MOD.
= 0; }
}
return; }
}
// Very simple tree-building operation.
void build(int l, int r, int root) {
if (l == r) {
int t; cin >> t.
tree[root].s1 = t % MOD;
tree[root].s2 = t * t % MOD; tree[root].
tree[root].s3 = t * t % MOD * t % MOD; tree[root].s2 = t * t % MOD; tree[root].
return; }
return; }
int mid = (l + r) > > 1; build(l, mid, lc); return; }
build(l, mid, lc).
build(mid + 1, r, rc).
push_up(root).
return;
}
// Update the operation.
void update(int l, int r, int v, int L, int R, int root) {
// Basically similar to the push_down() function.
if (L <= l && r <= R) {
tree[root].tag = (tree[root].tag + v) % MOD;
tree[root].tag = (tree[root].tag + MOD) % MOD; tree[root].
tree[root].s3 = (tree[root].s3 + 3 * v % MOD * tree[root].s2 % MOD + 3 * v % MOD * v % MOD * tree[root].s1 % MOD + (r - l + 1) * v % MOD * v % MOD * v % MOD) % MOD; tree[root].tag = (tree[root].tag + v) % MOD; tree[root].tag = (tree[root].tag + MOD)
tree[root].s3 = (tree[root].s3 + MOD) % MOD; tree[root].
tree[root].s2 = (tree[root].s2 + 2 * v % MOD * tree[root].s1 % MOD + (r - l + 1) * v % MOD * v % MOD) % MOD;
tree[root].s2 = (tree[root].s2 + MOD) % MOD; tree[root].s1 = (r - l + 1 * v % MOD * v % MOD) % MOD; tree[root].
tree[root].s1 = (tree[root].s1 + (r - l + 1) * v % MOD) % MOD; tree[root].s1 = (tree[root].s1 + (r - l + 1) * v % MOD) % MOD; tree[root].s1 = (tree[root].s2 + MOD)
tree[root].s1 = (tree[root].s1 + MOD) % MOD; tree[root].
return.
}
push_down(tree[root], tree[lc], tree[rc], r - l + 1); int mid = (l + r); int mid = (l + l); int mid = (l + l); int mid = (l + l)
int mid = (l + r) >> 1; if (L <= (l + r) >> 1;)
if (L <= mid) update(l, mid, v, L, R, lc);
if (R >= mid + 1) update(mid + 1, r, v, L, R, rc);
push_up(root);
}
// Interval query operation.
int query(int l, int r, int L, int R, int root) {
if (L <= l && r <= R)
return (tree[root].s3 + MOD) % MOD;
int sum = 0; push_down(tree[root].s3 + MOD)
push_down(tree[root], tree[lc], tree[rc], r - l + 1); int mid = (l + r); r - l - 1)
int mid = (l + r) >> 1; if (L <= (l + r) >> 1;)
if (L <= mid) sum = (sum + query(l, mid, L, R, lc)) % MOD;
if (R >= mid + 1) sum = (sum + query(mid + 1, r, L, R, rc)) % MOD; return (sum + MOD) % MOD; return (sum + MOD) % MOD; return (sum + MOD) % MOD; return (sum + MOD) % MOD)
return (sum + MOD) % MOD; if (R >= mid + 1)
}
signed main() {
ios::sync_with_stdio(0); ios::sync_with_stdio(0)
(0); (0); cin >> n > n > n >
cin >> n >> m;
build(1, n, 1); while (m--) {
while (m--) {
cin >> k >> x >> y; if (k == 1) { cin >> n >> m; build(1, n, 1); while (m--) {
if (k == 1) {
cin >> v;
} else cout << query(1, n, x, y, 1) << endl;
}
return 0; }
}
Here is the Python code for this question, but there is no way to pass all the test points due to the large Python constants:
MOD = 10**9 + 7
N = int(1e5 + 5)
class Node:
def __init__(self):
self.s1 = 0
self.s2 = 0
self.s3 = 0
= 0
tree = [Node() for _ in range(N * 4)]
def push_up(root):
tree[root].s1 = (tree[root * 2].s1 + tree[root * 2 + 1].s1) % MOD
tree[root].s2 = (tree[root * 2].s2 + tree[root * 2 + 1].s2) % MOD
tree[root].s3 = (tree[root * 2].s3 + tree[root * 2 + 1].s3) % MOD
def push_down(root, l, r, length):
if tree[root].tag != 0:
num = tree[root].tag % MOD
left_child = root * 2
right_child = root * 2 + 1
left_len = length - length // 2
right_len = length // 2
# Left child updates
tree[left_child].s3 = (tree[left_child].s3 + (3 * num * tree[left_child].s2 % MOD) + (3 * num * num % MOD * tree[left_child].s1 % MOD) + (left_len * num % MOD * num % MOD * num % MOD)) % MOD
tree[left_child].s2 = (tree[left_child].s2 + (2 * num * tree[left_child].s1 % MOD) + (left_len * num % MOD * num % MOD)) % MOD
tree[left_child].s1 = (tree[left_child].s1 + (left_len * num % MOD)) % MOD
tree[left_child].tag = (tree[left_child].tag + num) % MOD
# Right child updates
tree[right_child].s3 = (tree[right_child].s3 + (3 * num * tree[right_child].s2 % MOD) + (3 * num * num % MOD * tree[right_child].s1 % MOD) + (right_len * num % MOD * num % MOD * num % MOD)) % MOD
tree[right_child].s2 = (tree[right_child].s2 + (2 * num * tree[right_child].s1 % MOD) + (right_len * num % MOD * num % MOD)) % MOD
tree[right_child].s1 = (tree[right_child].s1 + (right_len * num % MOD)) % MOD
tree[right_child].tag = (tree[right_child].tag + num) % MOD
tree[root].tag = 0
def build(l, r, root):
if l == r:
t = data[l - 1] % MOD
tree[root].s1 = t
tree[root].s2 = t * t % MOD
tree[root].s3 = t * t % MOD * t % MOD
return
mid = (l + r) // 2
build(l, mid, root * 2)
build(mid + 1, r, root * 2 + 1)
push_up(root)
def update(l, r, v, L, R, root):
if L <= l and r <= R:
num = v % MOD
length = r - l + 1
tree[root].tag = (tree[root].tag + num) % MOD
tree[root].s3 = (tree[root].s3 + (3 * num * tree[root].s2 % MOD) + (3 * num * num % MOD * tree[root].s1 % MOD) + (length * num % MOD * num % MOD * num % MOD)) % MOD
tree[root].s2 = (tree[root].s2 + (2 * num * tree[root].s1 % MOD) + (length * num % MOD * num % MOD)) % MOD
tree[root].s1 = (tree[root].s1 + (length * num % MOD)) % MOD
return
push_down(root, l, r, r - l + 1)
mid = (l + r) // 2
if L <= mid:
update(l, mid, v, L, R, root * 2)
if R > mid:
update(mid + 1, r, v, L, R, root * 2 + 1)
push_up(root)
def query(l, r, L, R, root):
if L <= l and r <= R:
return tree[root].s3 % MOD
push_down(root, l, r, r - l + 1)
mid = (l + r) // 2
res = 0
if L <= mid:
res = (res + query(l, mid, L, R, root * 2)) % MOD
if R > mid:
res = (res + query(mid + 1, r, L, R, root * 2 + 1)) % MOD
return res % MOD
if __name__ == '__main__':
import sys
(1 << 25)
n, m = map(int, ().split())
data = list(map(int, ().split()))
build(1, n, 1)
for _ in range(m):
tmp = ().split()
if not tmp:
continue
k = int(tmp[0])
x = int(tmp[1])
y = int(tmp[2])
if k == 1:
v = int(tmp[3])
update(1, n, v, x, y, 1)
else:
print(query(1, n, x, y, 1))