zhangxyhp

摘要： SP1043 GSS1 - Can you answer these queries I 貓樹——線性對(duì)數(shù)預(yù)處理，常數(shù)查詢的優(yōu)秀數(shù)據(jù)結(jié)構(gòu)。 其實(shí)它是線段樹的一個(gè)變種。考慮線段樹的每個(gè)節(jié)點(diǎn) \([L,R]\)，對(duì)于 \(i\in[L,mid]\) 維護(hù) \([i,mid]\) 的信息，對(duì)于 \(i\i 閱讀全文

摘要： A. 【模板】動(dòng)態(tài) DP 好像是我做過的最難的一道 DDP（？） 普通的轉(zhuǎn)移 \(\begin{cases}f_{u,0}=\sum\max(f_{v,0},f_{v,1})\\f_{u,1}=a_u+\sum f_{v,0}\end{cases}\) 是不好優(yōu)化的，我們希望 \(f_{u,0/1} 閱讀全文

摘要： 考慮將模擬賽分塊，對(duì)于每個(gè)塊維護(hù)一個(gè)合集。 閱讀全文

摘要： A B C D Sum Rank 30 10 20 15 75 7/18 A. 路徑 看到 DAG，不難想到拓?fù)渑判颉？紤]在拓?fù)渑判虻倪^程中記錄每個(gè)點(diǎn)的深度 \(dep\)。不難想到如果有兩個(gè)點(diǎn)在同一深度，則不合法。但這樣的做法不完全。首先每個(gè)點(diǎn)可能有多條邊指向它，導(dǎo)致它的深度不確定；其次一些錯(cuò)誤狀 閱讀全文

摘要： A B C D Sum Rank 60 - - 20 80 16/24 A. 集合 首先發(fā)現(xiàn)固定左端點(diǎn) \(l\)，好的子區(qū)間的右端點(diǎn)是從 \(l\) 開始的一段連續(xù)的位置。這是因?yàn)橐粋€(gè)好的區(qū)間，其子區(qū)間必然也是好的。于是雙指針，用權(quán)值線段樹維護(hù)連續(xù)段即可。 Code #include<bits/s 閱讀全文

摘要： A. Closest Equals 首先給每個(gè)位置求出它到上一次出現(xiàn)的距離，將這記為一條線段。我們發(fā)現(xiàn)，有效的線段，其隨著左端點(diǎn)的增長，右端點(diǎn)必然是增長的。因?yàn)槿绻幸粭l大線段包含了小線段，大線段必然是沒用的。于是我們便可以二分出查詢的線段區(qū)間，ST 表求出最小值即可。 Code #include< 閱讀全文

摘要： A B C D Sum Rank 40 8 20 15 83 9/22 A. origen 首先做前綴和，答案變?yōu)?\(\sum_{i=0}^{n-1}\sum_{j=i+1}^{n}a_i\oplus a_j\)。 然后拆位考慮，分別計(jì)算 \(a^2\) 和 \(2ab\)。對(duì)于 \(a_i\)， 閱讀全文

摘要： A B C D Sum Rank 80 0 15 - 95 7/21 A. 草莓列車(train) 我們需要 \(O(1)\) 修改的數(shù)據(jù)結(jié)構(gòu)，這讓我們聯(lián)想到考慮把 ST 表倒過來做。于是做法就很顯然了，將修改區(qū)間拆成兩個(gè)區(qū)間賦值，最后再 \(O(n\log n)\) 下傳即可。 剩下的全在代碼里了 閱讀全文

摘要： A B C D Sum Rank 25 - 5 - 30 16/19 連著墜🐓兩場了。 A. kotori 原 不難想到將每個(gè)投票裝置的答案都貢獻(xiàn)到根鏈上，查詢的時(shí)候也在根鏈查詢。但是這樣會(huì)將一部分非法的答案算入，解決方案是以第一個(gè)裝置為根。 我們發(fā)現(xiàn)這時(shí)只需要在新加入點(diǎn)時(shí)將根鏈最小值貢獻(xiàn)給答案， 閱讀全文

摘要： A B C D Sum Rank 20 20 - - 40 20/21 比賽是💩，我更是💩。 A. 簽 原 可以發(fā)現(xiàn)每次操作會(huì)減少 \(3\) 個(gè)逆序?qū)Γ瑫r(shí)如果只考慮奇數(shù)位或偶數(shù)位那么會(huì)減少 \(1\) 個(gè)逆序?qū)ΑＲ虼擞薪獾某湟獥l件是奇數(shù)逆序?qū)εc偶數(shù)逆序?qū)χ偷扔诳偰嫘驅(qū)Φ娜种弧＞唧w證明不 閱讀全文