CF資料結構練習

1. CF 438D The Child and Sequence

大意: n元素序列, m個操作: 1,詢問區間和. 2,區間對m取模. 3,單點修改

維護最大值, 取模時暴力對所有>m的數取模. 因為取模後至少減半, 複雜度$O(nlognlogC)$

2. CF 431E Chemistry Experiment

大意: n個試管, 第$i$個試管有$a_i$機關水銀, m個操作: 1, 修改$a_x$改為$v$. 2, 将$v$機關水倒入試管, 求一種方案使得有水的試管水銀與水總量的最大值最小, 輸出最小值 (操作2獨立)

二分出一個最小的$x$, 使得$sum[x]+v \le (x+1)cnt[x]$, 答案即為$\frac{sum[x]+v}{cnt[x]}$

3. CF 429D Tricky Function

大意: 給定序列, 求$f(i,j)=(j-i)^2+(sum[j]-sum[i])^2$的最小值

裸的平面最近點對, 可以用分治很容易求出

4. CF 420D Cup Trick

大意: 初始有一個排列, 順序未知, m個操作, 每次将位置在$y_i$處權值為$x_i$的數移到排列最前面, 求恢複原排列.

很明顯的splay模拟題, 按順序操作, 最後再逆序恢複就可以了, 然後就完美的T掉了....主要這題資料量太大, 感覺最慢的點可能跑了5s.....參考了一下其他dalao的代碼, 通過一些技巧轉化為查詢第k大, 然後可以線段樹二分, 這樣常數會小很多

5. CF 413E Maze 2D 

大意: 2*n棋盤, m次詢問, 查詢兩點最短路.

線段樹維護2*2的轉移狀态矩陣.

6. CF 418E Tricky Password

大意: n*n的矩陣, 隻給出第一行, 對于第$i(i\ge 2)$行, $a_{i,j}$為$a_{i-1,j}$在第$a_{i-1,1},...a_{i-1,j}$中的出現次數. 給定m個操作, 1,第一行單點修改. 2,查詢某位置的值

打個表發現第二行以後每兩行一循環, 然後分塊.

7. CF 436E Cardboard Box

大意: n個盒子, 從第$i$個盒子拿一顆糖消耗$a_i$, 兩顆消耗$b_i$, 求拿$w$顆糖最小花費.

按照b從小到大排序, 假設最優解選擇最大的$b$位置為$k$, 容易證明$[1,k]$一定至少拿一塊糖. 然後枚舉k, 用權值線段樹暴力模拟即可. 看了下CF大神的做法, 直接用$multiset$維護一顆糖和兩顆糖最小值貪心..

8. CF 436F Banners

大意:

9. CF 444C DZY Loves Colors

大意: 給定n元素序列, 每個元素有一個顔色和權值, m個操作, (1)區間染色x, 每個位置權值增加|x-y|, y為原色 (2)區間詢問權值和.

線段樹維護權值和, 對于異色區間暴力遞歸下去, 直到同色時打标記修改, 考慮複雜度證明.

注意到産生額外複雜度的隻有異色區間數, 并且每個異色區間每次至多産生1次貢獻(因為查詢後立刻被改為同色), 并且每次查詢時邊界處會再額外産生$O(log)$個異色區間, 再加上初始異色區間數$O(n)$, 總的複雜度就為$O(n+mlogn)$.

10. CF 446C DZY Loves Fibonacci Numbers

大意: 區間加斐波那契, 區間求和模1e9+9

這題模數比較特殊, 可以發現5模1e9+9的二次剩餘恰好存在, 就有$F_n \equiv 276601605(691504013^n-308495997^n) \space (mod\space 1e9+9)$, 用線段樹維護等比數列和.

還有一種不依賴二次剩餘的解法, 若$b_1=x,b_2=y,b_n=b_{n-2}+b_{n-1}$, 那麼$b_n=xf_{n-2}+yf_{n-1},\sum b_n=xf_n+yf_{n+1}-b_{2}$, 可以用線段樹維護每一段的$x,y$

11. CF 452E Three strings

大意:給定三個字元串$s_1,s_2,s_3$, 對于每個長度$x$, 輸出有多少個三元組$(i_1,i_2,i_3)$, 滿足$s_k[i_1,i_1+1,...,i_1+x-1]$相同.

字尾自動機以後補.

12 CF 452F Permutation

大意: 給定n排列, 判斷是否存在等差子序列.

跟FFT字元串比對差不多. 假設存在等差$a_i,a_j,a_k$, 枚舉$a_j$.

對于$a_{j-1},a_{j-2},...,1$和$a_{j+1},a_{j+2},...,n$分别維護一個二進制數, 二進制為$1$表示在$a_j$的左側, 那麼隻要兩個數二進制數不相等即存在一個等差. 用二進制壓位$O(\frac{n^2}{\omega})$, 或者線段樹維護哈希$O(nlogn)$.

13. CF 453E Little Pony and Lord Tirek 

大意: n隻小馬, 第$i$匹馬初始能量$s_i$, 每秒增長$r_i$, 最大能量$m_i$, 每次詢問$t$時刻$[l,r]$區間小馬能量和, 并将$[l,r]$區間小馬能量清零.

把每個位置最後操作時間看做顔色, 每次操作相當于一個區間染色, 跟444C一樣, 用線段樹維護區間能量和, 對異色暴力, 隻考慮同色情況. 對于連續一段同色區間按每隻馬充滿時間排好序, 可以二分出第一個未充滿的位置, 預處理出字首和可以很容易計算答案, 複雜度$O(mlog^2n)$. 看了其他dalao題解, 發現可以用$splay$或者$set$分離合并相同的區間, 這樣每次雜色區間最多産生2個, 複雜度是$O(mlogn)$

14. CF 455D Serega and Fun

大意: 給定序列a, m個操作, (1)[l,r]區間循環右移. (2)求[l,r]區間多少個元素等于k

裸的分塊, 每個塊内維護一個deque循環右移即可. 還可以用$splay$來做

15. CF 455E Function

大意: 定義f(1, j) = a[j], f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 給定a數組, m個詢問f(x,y)的值

找下規律發現轉移都是先向下再向左下, 也就是說$f(x,y)=\min\limits_{t}((x-y+t)a[t]+s[y]-s[t])$, 并且向下轉移的a[t]的值一定是遞減的, 是以可以離線後斜率優化.

16. CF 461C Appleman and a Sheet of Paper

大意: 初始一張長n的紙, 2種操作, (1)最左側往右折疊p個機關. (2)詢問[l,r]共多少層紙.

水題, 模拟折紙, 用樹狀數組求和, 若折疊超過右側的話, 可以看做是将右側折向左側然後翻轉了一下.

17. CF 464E The Classic Problem 

大意: n節點, m條邊無向圖, 邊權為2的幂, 求s->t的最短路.

線段樹維護每個二進制位, 相加相當于區間修改, 比較大小用hash判斷.

18. CF 471E MUH and Lots and Lots of Segments

大意: 給定平面上n條與坐标軸平行的線段, 求删除一部分, 使得剩餘部分連通且無環, 輸出剩餘部分最大長度.

每個連通塊的最大長度為點的個數-1, 然後掃描線不太會......... 這題以後再補 QAQ

19. CF 472G Design Tutorial: Increase the Constraints

大意: 給定兩個01字元串a,b, m個詢問, 給出$(p1,p2,len)$, 求$a_{p1}a_{p1+1}...a_{p1+len-1}$與$b_{p2}b_{p2+1}...b_{p2+len-1}$多少個對應位置的字元不同.

這題時限很大, 可以直接$bitset$水過去... 正解的話是分塊+FFT, 以後再補 QAQ

20. CF 474F Ant colony

大意: n隻螞蟻, 第i隻權值$a_i$, 每次詢問隻考慮區間$[l,r]$, 每隻螞蟻能整除其餘螞蟻那麼加一分, 求多少螞蟻得分不是r-l.

等價于求區間多少元素不等于區間gcd, 直接線段樹維護.

21. CF 475F Meta-universe

22. CF 477E Dreamoon and Notepad

23. CF 480E Parking Lot

大意: 給定01矩陣, 單點指派為1, 求最大全0正方形.

将詢問倒序處理, 那麼答案一定是遞增的, 最多增長$O(n)$次, 對于每次操作暴力判斷答案是否增長即可, 也就是說轉化為判斷是否存在一個邊長$x$的正方形包含給定點, 可以維護左右兩側第一個1的位置, 從上往下滑動視窗即可$O(n)$判斷, 總複雜度$O(n^2)$

24. CF 482E ELCA

大意: 

25. CF 484E Sign on Fence

大意:給定序列, m個詢問, 對于[l,r]區間, 求所有長為$w$的區間最小值的最大值

最小值最大要記着想二分! 對于每個權值$x$建一顆線段樹, 把所有>=x的數添進線段樹裡, 維護最大連續區間長度, 然後每次詢問二分出最大的>=w的權值.

26. CF 487D Conveyor Belts

大意:

27. CF 487E Tourists

大意:

28. CF 490F Treeland Tour 

大意: 求樹上LIS

這題資料範圍過小, 我們考慮N<=1e5的做法, 線段樹維護lis,lds, 合并的時候更新一下答案即可.

29. CF 494E Sharti

大意:

30. CF 498D Traffic Jams in the Land

大意: n+1個城市, i和i+1相距$a_i$, 若到第i個城市花費時間為$x$, 且$x|a_i$那麼到$i+1$用時2, 否則用時1. m個操作, 單點修改a, 詢問兩城市花費時間 

線段樹維護模lcm(1,2,3,4,5,6)的花費時間.

31. CF 500E New Year Domino

大意: n個多米諾骨牌, 可以任選一塊增高1, 每次詢問求推倒$x$能傳遞到$y$所需要增高最少次數.

每塊骨牌能到達的區間用線段樹覆寫, 那麼每次答案就為沒有覆寫到的區間長度和. 為了避免前面骨牌的影響可以離線或者線上主席樹. 該題也可以離線後用并查集合并區間.

32. CF 501D Misha and Permutations Summation

大意:ord(P)為排列P的字典序, perm(n)為第n大排列(從0開始), 給定排列p,q, 求perm((ord(p)+ord(q))%n!)

康托展開闆子, 線段樹二分$O(nlogn)$

33. CF 515E Drazil and Park

大意: 給定環, 每個點有高度h, 第i與i+1距離$d_i$, 每次詢問考慮不屬于[a,b]的部分, 求2(hx + hy) + dist(x, y)的最大值.

環翻倍後轉成鍊, dist轉成字首, 相當于區間求$2h[x]-sum[x]+2h[y]+sum[y]$的最大值, 線段樹可以很容易維護.

34. CF 519E A and B and Lecture Rooms

大意: 給定樹, 每次詢問給出兩點$x,y$, 求樹上多少個點到$x,y$距離相同.

兩點距離為奇數顯然不存在距離相同的點, 偶數的話求出中點, 中點不在樹鍊的子樹大小即為答案.

35. CF 522D Closest Equals

大意: 給定序列$a$, 每次詢問區間[l,r]内相同元素的最近距離.

對于一個數$a_x$, 他會對$[1,pre[a_x]]$産生$x-pre[a_x]$的貢獻, 可以用樹狀數組離線或主席樹線上.

36. CF 524E Rooks and Rectangles

大意: 給定n*m棋盤, k個點有車, m個詢問, 求矩形(x1,y1,x2,y2)區域内的車是否能攻擊到所有位置.

等價于詢問一個矩形内每行至少有一個車或每列至少有一個車, 可以離線, 詢問按$x2$排序後, 求出[y1,y2]的範圍内車的位置最小值是否>=x1. 對于[x1,x2]同理.

37. CF 524F And Yet Another Bracket Sequence

大意: 給定括号序列, 可以在任意位置添加括号任意次, 可以循環右移任意次, 求一種方案使得括号比對且總長度最短且字典序最小.

括号題不會做, 這題看題解了.

38. CF 526F Pudding Monsters

大意: n*n棋盤, n個點有怪獸, 求有多少邊長為k的正方形内恰好有k隻怪獸, 輸出k=1,...,n時的答案和.

等價于給定n排列, 對于任意一個長為$k$的區間, 若最大值最小值的差恰好為k, 則産生1貢獻, 求貢獻和.考慮分治, 問題就轉化為如何$O(n)$求出跨越$mid$的貢獻, 可以讨論最大值最小值的位置, 雙指針求出.

39. CF 536E Tavas on the Path

大意:給定樹, 有邊權, m個詢問(u,v,l), 對于路徑u->v的所有邊, 構造一個01串, 邊權>=l為1, 對于每一段連續的1, 假設長為$x$, 則産生$f[x]$的貢獻, 求貢獻和.

離線, 按邊權排序, 從大到小添邊, 樹剖+線段樹維護答案.

40. CF 533D Landmarks

大意:

41. CF 538F A Heap of Heaps

大意: 給定序列$a$, 定義一棵有根樹的不穩定度為: 所有非根結點$v$的個數, 滿足$a_v<a_{fa[v]}$. 求将序列a組成1,...,n-1叉樹的不穩定度.

n節點k叉樹非葉節結點數是$O(\frac{n}{k})$的, 問題就轉化為$O(nlogn)$個詢問(l,r,x), 求[l,r]内有多少<x的數, 可以用主席樹或樹狀數組實作.

42. CF 540E Infinite Inversions

大意: 初始有一個無限長的排列{1,2,3,....}, 求進行n次交換後排列的逆序對數.

把連續未改變的點合并一下, 然後歸并或樹狀數組.

44. CF 543E Listening to Music 

大意: 定義f(l,x)為區間[l,l+m-1]小于x的個數, q個詢問(l,r,x), 每次回答$\min\limits_{i=l}^r f(i,x)$

按權值升序排列, 建主席樹, 貢獻轉為區間加單點求最小值即可.

關鍵這題隻有64MB, 學習了下卡空間技巧

(1)标記永久化

(2)葉節點不額外開點, 直接存在父親上

(3)結構體用unsigned long long分3個位域存

45. CF 547E Mike and Friends

大意: 給定n個字元串, m個詢問(l,r,k), 求$s_k$在$s_l,s_{l+1},...,s_{r}$的出現次數.

46. CF 549F Yura and Developers 

大意: 給定序列a, 求區間個數, 滿足除去最大元素後的和被k整除.

建出笛卡爾樹後重鍊剖分, 複雜度$O(nlogn)$

47. CF 551E GukiZ and GukiZiana

48. CF 571D Campus

50. CF 573D Bear and Cavalry 

神題

51. CF 573E Bear and Bowling

52. CF 575I Robots protection

53. CF 576E Painting Edges

54. CF 580E Kefa and Watch

大意: 給定字元串, m個操作, (1)區間指派. (2)查詢[l,r]區間周期是否為d

線段樹維護哈希, 判斷[l,r-d]與[l+d,r]是否相同即可

55. CF 587C Duff in the Army

56. CF 587E Duff as a Queen

57. CF 587F Duff is Mad

58. CF 594D REQ 

大意: 給定序列a, m個詢問, 求$\prod\limits_{i=l}^{r}a_i$

時限很大, 莫隊随便過. 也可以用主席樹或離線樹狀數組, 枚舉右端點隻保留最接近右端點的素數. 類似于HH的項鍊

59. CF 601D Acyclic Organic Compounds

大意: 給定樹, 每個節點有字元, 定義dif(x)為以x為起點在x的子樹内能得到的不同字元串數, 求$dif(x)+c_x$最大值及最大值個數.

可以直接字典樹合并複雜度$O(26n)$, 或者hash+dsu on tree $O(nlogn)$

60. CF 610D Vika and Segments

大意: 給定平面n條水準或垂直的線段, 求占了多少個點.

相當于求寬度為1的矩形面積并, 離散化後掃描線.

60. CF 610E Alphabet Permutations

大意: 給定排列

轉載于:https://www.cnblogs.com/uid001/p/10645211.html