Problem - 444C - Codeforces題意： 給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。 M 筆詢問，兩種形式： 1 l r x：將 [ l, r ] 都塗色為 x 2 l r：輸出 [ l, r ] 的貢獻總和 初始時所有元素的貢獻為 0。 當一個元素由 u 變為 v 時，增加貢…

Problem - 522D - Codeforces題意： 給你長度 N 的數列 A[]。 M 筆詢問，問 [ L, R ] 中，最近的相同元素距離是多少。若不存在，輸出 -1。制約： 1 ≤ N, M ≤ 5e5 abs( A[ i ] ) ≤ 1e9解法： 可以很快想到，給每一個位置 i 紀錄前一個 A[ i ] 的位置 pre[ i ]…

Problem - 566D - Codeforces題意： 給你 N 個人，初始時他們自己一個組。 Q 筆詢問，三種形式： 1 x y：merge( x, y ) 2 x y：merge( x, x + 1, ..., y ) 3 x y：print "YES" if group( x ) == group( y ) else "NO"制約： 1 ≤ N ≤ 2e5 1 ≤ Q ≤ 5e5解法： …

Problem - C - Codeforces題意： 給你 N 次多項式 F()。 係數的絕對值不能超過 K。 問你修改一個值之後，F( 2 ) = 0 的方案數。 特別的，A[ N ] != 0。制約： 1 ≤ N ≤ 2e5 abs( K ) ≤ 1e9解法： 哈希水掉。 原本不能暴力算的原因只是因為數字會太大，不過哈…

Problem - D - Codeforces題意： 給長度 N 的字串，以及定數 K。 對於 i = [ 0 .. N - 1 ]，問是否存在字串 A 和 B，使得 A + B + A + B .. + A = S[ 0 .. i ]，其中 A 重複 K + 1 次，B 重複 K 次。 A, B 可為空字串。制約： 1 ≤ N, K ≤ 1e6解法： KMP 真是…

F: Lotus Leaves - AtCoder Regular Contest 074 | AtCoder題意： H * W 的棋盤。 起點 S，終點 T。這兩個點都有葉子。 其他葉子用 'o' 描述。 每次可以選擇同行或同列的 'o' 移動到那裡。 問最少要移除多少葉子才能使 S 不能到達 T。無解輸出 -1。制約： 2≤…

E: RGB Sequence - AtCoder Regular Contest 074 | AtCoder題意： N 個格子一排。 有三種顏色可以塗。 M 條限制，表示 [ L, R ] 中要有 X 種顏色。 求方案數模 1e9 + 7。制約： 1≤N≤300 1≤M≤300 1≤li≤ri≤N 1≤xi≤3解法： dp[ i ][ j ][ k ]：第 { 1, 2, 3 } …