【省選模拟】20/04/16

傳送門

A

• 題意：給定 n ≤ 1 e 5 n\le 1e5 n≤1e5 個點 ( i , y i ) (i,y_i) (i,yi​)， m ≤ 4 e 5 , q ≤ 1 e 5 m\le 4e5,q\le 1e5 m≤4e5,q≤1e5 次操作，操作可以單點修改，區間将 y i y_i yi​ 變成 A − y i A-y_i A−yi​，詢問 [ l , r ] [l,r] [l,r] 中 a x + b y + c x y ax+by+cxy ax+by+cxy 的最大值，資料随機

• 考慮什麼樣的點可以成為最有值，那一定是字尾 y y y 的最大值

  由于資料随機，那麼這樣的點不超過 log ⁡ n \log n logn，線段樹直接維護單調棧是修改 n log ⁡ 2 n n\log^2 n nlog2n 詢問 n log ⁡ n n\log n nlogn

  考慮搞成修改 n log ⁡ n n\log n nlogn，詢問 n log ⁡ 2 n n\log^2n nlog2n，那麼我們維護區間最大值，每次查詢 log ⁡ n \log n logn 次即可

  c o d e code code

B

• 題意：将 a r a_r ar​ 放到 a l a_{l} al​ 前面，查詢 [ l , r ] [l,r] [l,r] 中為 k k k 的個數， n ≤ 1 e 5 , a i ≤ n n\le 1e5,a_i\le n n≤1e5,ai​≤n

• 自己搞了個連結清單 + 分塊，連結清單維護插入删除，分塊維護區間和，順便記一下塊頭的标号，就可以知道塊内每個點位置了， O ( n n ) O(n\sqrt n) O(nn

  ​)，出題人不講道理，居然有 l = r l=r l=r 的修改？挂了 60

  c o d e code code

C

• 題意：給定 a ≤ 16 a\le 16 a≤16，輸出 l , r l,r l,r 滿足 ∑ i = l r f ( i ) ≡ 0 ( m o d   a ) \sum_{i=l}^rf(i)\equiv 0(mod\ a) ∑i=lr​f(i)≡0(mod a)， f ( i ) f(i) f(i) 為 i i i 各位數位之和

• 有一點瞎搞的味道，找到最小的 r r r 滿足字首和剛好 ≥ a \ge a ≥a，然後雙指針調整，最壞的情況 s u m r sum_r sumr​ 和 a a a 差了 144，很快就可以調整到，找 r r r 用二分 + 數位 d p dp dp 即可

  c o d e code code