# 2024 成大邀請賽 pF 海星爭霸-SeaStarCraft 題解

一開始 a=b=0，每回合可以其中一種操作執行
操作1 : a+=1
操作2 : b+=a
第一行有兩正整數 n,m，n 代表總共會經歷幾個回合，m 代表會有幾個事件
第二行有m個正整數 c_i，代表第i件事件發生的回合
第三行有m個正整數 d_i，為1~m的排列，代表第i個事件的重要性名次，數字越小越重要
定義一種操作組合的結果為長度m的數組A，A_i是在第i重要的事件的回合結束時，b的值
而兩個不同操作產出的A，第一個相異元素的較大者較好，若所有元素都相同則代表一樣好
輸出最好的A

思路：
優先級較高的事件能決定他之前的回合如何操作，所以如果某個事件之前的所有操作已經被更高優先級的事件確定了，則他是一個沒有決策力的事件
對於一個當前最優先且有決策力的事件：
是當前最未來的事件：
假設有k次操作 那設x為執行操作一的次數，結果等於 b + (a+x)*(k-x) = b + -x^2+(k-a)x+ak，顯然的，要使結果最大，x必須等於(k-a)/2
一個的case：
將其稱為必定事件
在此之前的所有操作皆會是必定的事。
兩個的case：
將其稱為不定事件
這兩種case的差異是：
操作1多一次時，該事件結束時的a較大，對之後的事件有利。
操作2多一次時，前(k-1)/2回合不變，(k+1)/2到k-1之間的b則會較大。
也就是說，若下一個優先的有意義事件位於(k+1)/2~k-1之間，則操作2多一次較好
否則操作1多一次一定不會比較差
不是當前最未來的事件：
將其稱為決策事件
只有一種可能使某事件不是最未來的卻有決策力，那就是他後面有一個不定事件
此時確認該不定事件，必須得是操作2多一次的事件，且變為必定事件
哪些事件沒有決策力？
1.該事件的未來，存在優先度更高的必定事件
2.該事件的未來，存在優先度更高的不定事件，且自己不位於該不定事件的(k+1)/2~k-1之間
哪些事件有決策力？
1.該事件的未來，不存在優先度更高的必定事件
2.該事件的未來，不存在優先度更高的不定事件，或自己位於該不定事件的(k+1)/2~k-1之間
若某事件能決策未來發生且優先度更高的不定事件，稱它為決策事件

設計策略：
1.初始化時，所有回合設皆為不確定狀態
1.從優先度高的事件開始看，找到有決策力的事件
2.對於一個有決策力的事件，判斷該回合的狀態，取得自身是必定、不定或決策中的哪種事件
3.對於必定事件，直接標記前面所有回合為確定狀態
4.對於不定事件，對前(k-1)/2回合標記為確定狀態，對(k+1)/2~k-1回合標記為決策狀態
5.對於決策事件，對後面的不定事件前的所有回合標記為確定狀態
6.對於每個確定狀態的事件回合，紀錄當下的a和b，以此推算未來的狀況

維護最新的不定與必定事件，每次更改與查詢 O(1)
維護所有必定事件，其 a 與 b 值
維護所有必定事件，其之前 or 之後會用幾次操作一 O(mlogm)