2025-12-26 hetao1733837的刷题记录
2025-12-26 hetao1733837的刷题记录2025-12-26CF1009F Dominant Indices原题链接1CF1009F Dominant Indices原题链接2F. Dominant Indices分析还是先打树剖吧呃换而言之就是求取每个点x xx的j jj其中j jj为d x , … d_{x,\dots}dx,…的峰。由d x , i d_{x,i}dx,i的定义显然的长剖吧。但是后面那个呃……三分那时间复杂度是多少长剖大概在O ( n ) O(\sqrt{n})O(n)三分大概在O ( n l o g 3 n ) O(nlog_3n)O(nlog3n)预处理d dd数组大概在O ( n 2 n ) O(n^2\sqrt{n})O(n2n)吗我不太清楚反正挺炸的吧……MX课上讲的什么DP我翻一下。好的d数组本身就是一个DP数组。其转移是相当经典的树形DPd p v , x ∑ d p v , x − 1 dp_{v,x} \sum{dp_{v,x-1}}dpv,x∑dpv,x−1在链上时间复杂度将会来到O ( n 2 ) O(n^2)O(n2)。那就是长剖优化DP的板子。也就是说当我们遇到那些与深度有关的树形DP后就要考虑使用长剖优化。盯不出来状态和转移怎么办行应该是会了。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN1000005;intn;vectorinte[N];intfa[N],len[N],son[N],ans[N];voiddfs1(intu,intpa){fa[u]pa;for(autov:e[u]){if(vpa)continue;dfs1(v,u);if(len[v]len[son[u]]){son[u]v;len[u]len[v]1;}}}vectorintdp[N];voiddfs2(intu){if(son[u]){dfs2(son[u]);swap(dp[u],dp[son[u]]);dp[u].push_back(1);ans[u]ans[son[u]];if(dp[u][ans[u]]1)ans[u]len[u];for(autov:e[u]){if(vfa[u]||vson[u])continue;dfs2(v);for(intilen[v];i0;i--){intlilen[u]-len[v]-1;dp[u][l]dp[v][i];if(dp[u][l]dp[u][ans[u]]||(dp[u][l]dp[u][ans[u]]lans[u]))ans[u]l;}}}else{dp[u].push_back(1);ans[u]0;}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1,u,v;in;i){cinuv;e[u].push_back(v);e[v].push_back(u);}dfs1(1,0);dfs2(1);for(inti1;in;i)coutlen[i]-ans[i]\n;}LG5903 【模板】树上 K 级祖先原题链接【模板】树上 K 级祖先分析不能正常一点吗不是那我重剖双log不是也很不错吗正解#includebits/stdc.husingnamespacestd;constintN500005;#defineuiunsignedintui s;inlineuiget(){s^s13;s^s17;s^s5;returns;}intn,q,f[N][22],rt;inttop[N],de[N],dfn[N],ncnt,len[N],son[N];vectorinte[N];intlg[N];intup[N],down[N];voiddfs1(intu){for(inti1;i19;i){f[u][i]f[f[u][i-1]][i-1];}for(autov:e[u]){de[v]len[v]de[u]1;dfs1(v);len[u]max(len[u],len[v]);if(len[v]len[son[u]]){son[u]v;}}}voiddfs2(intu,intp){dfn[u]ncnt;down[ncnt]u;up[ncnt]p;if(son[u]){top[son[u]]top[u];dfs2(son[u],f[p][0]);}for(autov:e[u]){if(vson[u])continue;top[v]v;dfs2(v,v);}}intquery(intx,intk){if(!k)returnx;xf[x][lg[k]];k-(1lg[k]);k-de[x]-de[top[x]];xtop[x];if(k0)returnup[dfn[x]k];returndown[dfn[x]-k];}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnqs;lg[0]-1;for(inti1;in;i){lg[i]lg[i1]1;}rt1;for(inti1;in;i){cinf[i][0];if(f[i][0]0)rti;elsee[f[i][0]].push_back(i);}de[rt]1;dfs1(rt);top[rt]rt;dfs2(rt,rt);longlongans0;intlst0;for(inti1;iq;i){intx(get()^lst)%n1;intk(get()^lst)%de[x];lstquery(x,k);ans^1ll*i*lst;}coutans;}
