Just do simulation.

Time complexity: $O(n^2)$. Expected score: 40.

We actually dont need to loop through all trees every second to check whether the tree on its right is decayed. We only need to loop through all trees that just decayed in the previous second and make those in their left decay. Note that “a tree will never recover after it was decayed”, therefore you only need to loop over each tree for at most once and the total number must be at most $n$.

For query, maintain a set to store all decayed trees and query upper bound for $x$ and thats the answer.

Time complexity: $O(nlogn)$. Expected score: 100.

A $O(N^2)$ solution with good implementation can score 90 (written by adam xu orz). of course this will not happen in the real sdic as their test data are usually strong enough.

How to solve when $N = 2$?

Divide the finite string into middle, left and right part, the left and right part are equal, and they are another finite string.

Firstly, precompute the length of different versions of the string.
Then, do the below:
- Find l and r, which is the start and end of the middle part
- If the Kth character belongs to the middle part, output the character and return.
- Else if the Kth character belongs to the right part, convert it to the right part as left part = right part
- The finite string becomes the last version of the finite string
- Repeat until the process ends

The problem is derived from the task Happy String :)

For each direction, pre-process the grids that can be attacked, then run a (multisource) breadth-first search starting from all safe cells, recording the shortest distance to the safe cells in an array. When queried, just output the precomputed distance.

$ans_i$ = sum of $A[l…r]$
Where $l$ is the largest $l$ s.t. $A_l \gt A_i$,
$r$ is the smallest $r$ s.t. $A_r > A_i$

Don’t think about segment tree or other complicated data structure, using the data structure knowledge in HKOI lecture data structure (I) is enough.

Precompute partial sum, use it for finding the sum of $A[l..r]$
Let’s see how to find the largest $l$ s.t. $A_l \gt A_i$ (and apply the same thing to finding $r$):
When we find the $l$ for some $A_i$, the stones from $A_{l+1}$ to $A_{i-1}$ is not important anymore since $A_i \gt$ all of them.
Use a stack to maintain all the useful indexes, for every $i$, pop until it sees an index $x$ where $A_x \gt A_i$, $x$ is the required $l$. Then, push $i$ to the stack. Remember to handle the case where the stack is empty.

The writer intentionally hacks $O(NlogN)$ solutions. Also, you lose a lot of marks by not using fast I/O :(

Exhaust all position of cutting the array. Take the maximum.

Time complexity: $O(2^{n-1}\cdot n)$

Let $dp[i]$ be the maximal value obtained by only considering $a[1…i]$.

While computing $dp[i]$, we can loop $j$ through $1$ to $i-1$ meaning we will cut out $a[j+1…i]$ as a new segment. Therefore we have a transition formula:
$dp[i] =$ max of $($
$dp[j]+sum(a[j+1…i])$ if $a[j+1] \le a[i]$
$dp[j]-sum(a[j+1…i])$ if $a[j+1] \gt a[i]$
$)$ for all $j$ from $1$ to $i-1$.

The answer is $dp[n]$.

The transition can be done in $O(n)$ with careful implementation.

Time complexity: $O(n^2)$. Expected score: 50

We need to further optimize the transition.

Using prefix sum, we can replace $sum(a[l…r])$ by $ps[r]-ps[l-1]$. Apply it to the transition formula,

$dp[i]=$ max of $($
$dp[j]+ps[i]-ps[j-1])$ if $a[j+1] \le a[i]$
$dp[j]-ps[i]+ps[j-1])$ if $a[j+1] \gt a[i]$
$)$ for all $j$ from $1$ to $i-1$.

Therefore,

$dp[i]=max($
case 1: $max((dp[j]-ps[j-1]) + ps[i])$ for all previous $j$ with $a[j+1]$ in range $[-inf,a[i]]$
case 2: $max((dp[j]+ps[j-1]) - ps[i])$ for all previous $j$ with $a[j+1]$ in range $[a[i]+1,inf]$
$)$

Solution 1:

Discretize a and handle the transition by maintaining one segment tree for case 1 and one for case 2. Every time when done computing $dp[i]$, update position $a[i+1]$ with value $dp[i]-ps[i-1]$ for case 1 and $dp[i]+ps[i-1]$ for case 2. for computing the dp values, do range queries for both cases and take the maximum.

Time complexity: $O(nlogn)$. Expected score: 100 (75 without discretization)

Solution 2:

Use similar idea of monotonic queue but using set for doing prefix/suffix maximum queries with update.

Time complexity: $O(nlogn)$. Expected score: 100

Remember to use long long or else you can only score 45 even with the full solution!

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘淼。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

OMG adam xu is best writer on the whole universe!!!。 orz。 orz。 orz。 有文采的OIer。 本人表示欣赏。

枚举左式的值，即$g=lpf(a_{i},a_{j})$，则$g\mid i,g\mid j$，考虑从小到大枚举$g$的所有倍数$j$，找有多少之前枚举的i，满足$p_{i} \gt p_{j},lpf(a_{i}+a_{j})=g$,预处理出$lpf(x)=g$的所有数$x$，则$a_{i}+a_{j}=x$，即$a_{i}=x-a_{j}$。只需对所有数$k$开一颗动态开点线段树，维护$a_{i}=k$的数中，$p$的一段前缀中的个数，每次询问$segtree[x-a_{j}].query(p_j)$，询问完后更新$segtree[a_{j}].update(p_{j})$。记得枚举完一个$g$后清空线段树，可以用一个懒标记解决。