联想杯 - Gentle Jena(单调栈)
生活随笔
收集整理的這篇文章主要介紹了
联想杯 - Gentle Jena(单调栈)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Problem G. Gentle Jena
Input file:
Standard Input
Time limit: 2 seconds
Output file: Standard Output
Memory limit: 512 megabytes
... Why don’t you come to the planetarium?
The beautiful twinkling of eternity that will never fade, no matter what.
All the stars in the sky are waiting for you...
A planetarium, it was once where people went to soothe their hearts by gazing at a starry sky.
And Yumemi, a planetarium guide who has been waiting for a visitor for a long time, is looking up at
the stars.
Stars in the sky can be defined by their brightness, denoted by S = {b1, b2, · · · , bn}.
Yumemi found that stars always appear in groups, and she thinks the beauty of the starry night depends
on the darkest one, so she defined the beauty value as
B(S) = ∑
1≤l
≤r≤|S|
f(l, r) mod 998244353
where
f(l, r) = min
l≤i≤r
{bi}
But the night sky is not always the same. The movement of celestial bodies will make more and more
stars in the night sky. The following events will happen in order every second:
1. There are exactly i stars in the sky so S = {b1, b2, · · · , bi}. A star with brightness bi+1 appears,
and it will be appended to the end of the sequence S, so it will be S = {b1, b2, · · · , bi+1}.
2. Yumemi records the value (i.e., She calculates the value of B(S)).
At the beginning, there is no star in the sky, so S = {} initially.
As time goes by, because she is not as good at calculation as before, the task will be given to you.
Note that the sequence is given in a modified way.
Input
To avoid huge input, we use Linear Congruential Method to generate input data, and your solution should
be on-line.
The first line contains six integers n, p, x, y, z, b1(1 ≤ n ≤ 107, 2 ≤ p ≤ 109, 0 ≤ x, y, z, b1 < p), indicating
the number of the stars and the parameters of the data generator.
You need to generate the sequence {b1, b2, · · · , bn}by yourself using the following formula:
bi+1 = (x × Ai + y × bi + z) mod p
where Ai is the value of B(S) when |S| = i .
Page 13 of 272020 “Lenovo Cup” USST Campus Online Invitational Contest
May 30, 2020
Output
To avoid huge output, you only need to output ⊕
1≤
i≤n
Ai , where ”⊕” denotes the bitwise XOR operation (https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
Samples
Standard Input
Standard Output
5 13 2 0 1 3
27
Note
In the first second, S = {b1} = {3}, so A1 = f(1, 1) mod 998244353 = 3.
It can be inferred that b2 = (2A1 + 1) mod 13 = 7.
In the second second, S = {b1, b2} = {3, 7}, so A2 = [f(1, 1) + f(2, 2) + f(1, 2)] mod 998244353 = 13.
It can be inferred that b3 = (2A2 + 1) mod 13 = 1.
Keep calculating, and you will get A3 = 16, b4 = 7, A4 = 26, b5 = 1, A5 = 31.
So you should output A1 ⊕A2 ⊕A3 ⊕A4 ⊕A5 = 27.
題目大意：給出一個長度為 1e7 的序列，求出所有長度下的 B( S ) 的異或和，函數 B 在題意中已經定義，要求算法強制在線
題目分析：如果直接去考慮區間可能會有些困難，所以我們不妨可以從最小值出發，計算出每個 b[ i ] 所可以控制的區間個數，這樣就能不難計算出總貢獻了
如果是這樣想的話，不難想到用單調棧來維護了，考慮一般情況，當序列 S?在加入元素 b[ i ] 后，新增加了 i 個后綴區間，分別是 [ 1 , i ] , [ 2 , i ] .... [ i - 1 , i ] , [ i , i?] 這 i 個區間，利用單調棧找到當前元素左側首個小于自己的元素 pos，這樣 [ pos + 1 , i ] , [ pos + 2 , i ] , ... [ i , i ] 這 i - pos 個區間的最小值顯然就是 b[ i ] 了，現在我們需要快速計算得到 [ 1 , i ] , [ 2 , i ] ... [ pos?, i ] 這 pos 個區間的貢獻
如果我們想要利用單調棧去維護左側首個小于自己元素的位置，就需要維護一個大頂棧，這個大頂棧的特點是，不僅棧內元素滿足單調遞增，同時相應位置的下標也滿足單調遞增（根據單調棧的原理顯然可知），那么我們就可以將一直維護的這個大頂棧，想象成?[ 1 , i ] , [ 2 , i ] .... [ i - 1 , i ] , [ i , i?] 這 i 個區間分別對應的最小值，因為對于每個位置 i ，在將非法元素出棧后，最后一步是需要將位置 i 入棧，所以此時整個棧內的位置將區間 [ 1 , i ] 分割成了數個相連接的區間，假設我們可以遍歷棧中的元素，舉個簡單的例子：
假設 st[ 0 ] = 0 , st[ 1 ] = 3 , st[ 2 ] = 4 , st[ 3 ] = 6 ，同時 top = 3 ，此時剛好遍歷完位置 6 ，并且位置 6 已經入棧
那么 [ 1 , i ] 的每個位置所代表的的區間都可以根據棧內元素分類：
[ 1 , 6 ] , [ 2 , 6 ] , [ 3 , 6 ] 的最小值為 b[ 3 ] [ 4 , 6 ]? 的最小值為 b[ 4 ] [ 5 , 6 ] , [ 6 , 6 ] 的最小值為 b[ 6 ]
這樣每次維護一個 pre 代表在加入 b[ i ] 后，i 個區間貢獻之和，對于在加入 b[ i + 1 ] 時，彈棧的過程可以完成實時更新
因為每個元素至多入棧和出棧一次，所以時間復雜度是 O( n ) 級別的
代碼：
?
?
總結
以上是生活随笔為你收集整理的联想杯 - Gentle Jena(单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 牛客 - 减成一(差分数组)
- 下一篇： CodeForces - 1363E T