Jason Fan.

LOJ-3048 题意 给一个长度为 nnn 序列 aaa，让你求前 kkk 大区间异或和 的和，这 kkk 个区间 [li,ri][l_i,r_i][li​,ri​] 要满足 1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n 且没有区间相同。 1≤n≤5×105,1≤k≤min⁡{n(n−1)2,2×105},0≤ai<2321\le n\le 5\times 10^5 ,1\le k\le \min\left\{\tfrac{n(n-1)}{2},2\times 10^5 \right\},0\le a_i\lt 2^{32} 1≤n≤5×105,1≤k≤min{2n(n−1)​,2×105},0≤ai​<232 题解 类似于 [NOI2010]超级钢琴 （那道题求区间和），先处理出异或前缀和 sn=⨁i=1nais_n=\bigoplus_{i=1}^n a_isn​=⨁i=1n​ai​，对于一个右端点 rrr ，我们首先要找到使 sr⊕sls_r\oplus s_lsr​⊕sl​ 最大的 l,(l∈[0,r])l,(l\in[0,r])l,(l∈[0, ...

CF436E 题意 给你 nnn 种物品，每个物品可以不选，选一个代价为 aia_iai​ ，选两个代价为 bib_ibi​ ，问恰好选 mmm 的最小代价是多少。 1≤n≤3×105,0≤ai,bi≤109,m≤2n1\le n\le 3\times10^5,0\le a_i,b_i\le 10^9,m\le 2n 1≤n≤3×105,0≤ai​,bi​≤109,m≤2n 题解 很 naive 的想法可以 O(nm)O(nm)O(nm) 背包，显然会 TLE。 考虑每个物品要么不选，要么选一选二，情况很少，考虑可反悔贪心。每次我们增加一个物品，希望花费最小的代价。那么有如下四种选择： 物品 xxx 从零到一：+ax+a_x+ax​ 物品 xxx 从一到二：+bx−ax+b_x-a_x+bx​−ax​ 物品 xxx 从一到零，物品 yyy 从零到二：+by−ax+b_y-a_x+by​−ax​ 物品 xxx 从二到一，物品 yyy 从零到二：+by−bx+ax+b_y-b_x+a_x+by​−bx​+ax​ 考虑如何维护： 小顶堆 Q1Q_1Q1​ 维护 axa_xax​ ，x ...

AT4438 - Chords 题意 给定一个圆, 圆上均等地放着 2×N2\times N2×N 个点, 已有 KKK 对点之间连好了线段, 从中选择剩下 N−KN−KN−K 对点随意连线段(每个点只连一条线段). 两点联通当且仅当两点在同一条线段上或两点所属于的线段相交, 求所有连边方案中, 联通块的个数和. 1≤N≤300,0≤K≤N1\le N\le 300,0\le K\le N 1≤N≤300,0≤K≤N 题解 首先考虑把圆转化的序列上，圆上线段相交  ⟺  \iff⟺序列上两区间有交但不包含 。 考虑计算每个连通块对答案的贡献，就是每个连通块出现的方案数。 定义： g(x)g(x)g(x) 表示 xxx 个点随意连的方案数，显然： g(x)={∏i=1x/2(2i−1)if x is even0otherwiseg(x)= \begin{cases} \prod_{i=1}^{x/2} (2i-1) & \text{if x is even}\\ 0 &\text{otherwise} \end{cases} g(x)={∏i=1x/2​(2i−1)0​ ...

LOJ - 2880 题意 给你平面上 NNN 个点 ，任意两个点的横坐标都不相同，任意两个点的纵坐标都不相同。问你有多少对点满足，以这两点分别为左下角和右上角的矩形内部无其它点。如下图四个点中有三对点满足条件： 1≤N≤2×105,0≤Xi,Yi≤109,Xi互不相同,Yi互不相同1\le N \le 2\times 10^5 ,0\le X_i,Y_i\le 10^9,X_i\text{互不相同},Y_i\text{互不相同} 1≤N≤2×105,0≤Xi​,Yi​≤109,Xi​互不相同,Yi​互不相同 题解 考虑CDQ分治，每个点先按 XiX_iXi​ 排序，（还有把 YiY_iYi​ 离散化一下），开始CDQ分治，考虑如何计算 [l,mid][l,mid][l,mid] 对 [mid+1,r][mid+1,r][mid+1,r] 的贡献。题目保证不会有相同的横坐标，纵坐标，直接单关键字排序就行了。 两点对可行（假设 iii 点左下，jjj 点右上），要保证 Xi<Xj,Yi<YjX_i\lt X_j,Y_i\lt Y_jXi​<Xj​,Yi​<Yj ...

fdbc2997623a61cf73a7235ddd7595318b33e643f3cb00c209b6165956d742b312d7b773317bed9ccbd44a1f16bd2ebf34fcf04e3fe7b0cdbe63bfb73a581d32c53c61ff95381d79f0c10acea5490920b81ac7880b74de7cd03a85bb24989d3602f172238edee6e54f5e1d01c603048107dec364fdb2aa34e3b4063e6befb72939dac4a858e2c4217bd41033671c57b09290787fb155a9f8737dd518849c7725041333589f6a158cc2f7a088ba70c936ad856877057937ebab04f4a10d93c8d064dd68da247ab8d163a9c6c3dfcaac14c4a56e8a765271224f6dac7d41b40a39c105b5516f21c538f3f3a4e2701c3810e7a90d21dced0ead6 ...

CF19E 题意 给出一张无向图，求删除一条边后此图变成二分图的所有删边方案。 题解 二分图无奇环，无奇环就是二分图 如果该图是二分图，则删边后还是二分图。 于是我们先随便搞一个生成树，这上面的边称为树边，剩下的非树边加上去一定会构成环，称构成奇环的边为 “坏边”，构成偶环的边为 “好边”，与非树边构成的环的树边被非树边 “覆盖”。 考虑搞出的奇环个数（这里的奇环仅仅只一条非树边和生成树构成的环）。 没奇环，本就是二分图，输出所有边即可 有一个奇环，可以删除这条坏边，或者删除被坏边覆盖但没被好边覆盖的边。 证明：消除奇环必然要删除一条奇环上的边，考虑为什么要满足 没被好边覆盖 ，删除被好边覆盖的边不能解决问题，还会存在奇环：这条边属于一个奇环又属于一个偶环，这两环有交，去掉重合部分，奇-偶=奇，还会存在一个奇环。 有多个奇环，删除的边必然被所有坏边覆盖但没被好边覆盖（证明同上）。此时这条坏边显然不能删。 考虑实现，随便搞出个生成树，搞个倍增 LCA，对于边覆盖，树上差分即可。 注意图可能不连通。 CODE 12345678910111213141516171819202 ...

并查集基础练习 普通并查集 普通并查集有两个优化，这里再记一笔复杂度。 路径压缩，均摊 O(log⁡n)O(\log n)O(logn) 1int find(int u) {return fa[u]==u?u:fa[u]=find(fa[u]);} 按秩合并，均摊 O(log⁡n)O(\log n)O(logn) ，“秩” 取最大深度或者结点个数 12345void ut(int u,int v) { int fu=find(u),fv=find(v); if(sz[fu]>sz[fv]) swap(fu,fv); fa[fu]=fv;sz[fv]+=sz[fu];} 两个都加，均摊 O(α(n))O(\alpha (n))O(α(n)) ，α(n)\alpha (n)α(n) 为反阿克曼函数，增长极慢，可视为常数。 UVA1664 - Conquer a New Region 题意 一个树 NNN 个点，N−1N-1N−1 条带边权的边，定义两点之间价值为路径上边权的最小值。你雪要找一个中心结点，使它到所有点的价值之和 ...

CF1451D Circle Game 题意 在一个二维平面直角坐标系上，有一个棋子在 (0,0)(0,0)(0,0) 位置，两玩家轮流操作。在一次操作中，当前玩家必须将棋子向右移 kkk 个单位，或向上移 kkk 个单位，（即从 (x,y)(x,y)(x,y) 到 (x+k,y)(x+k,y)(x+k,y) 或 (x,y+k)(x,y+k)(x,y+k)）且要保证移动后得点在以原点为圆心半径为 ddd 的圆内，即 x2+y2≤d2x^2+y^2\le d^2x2+y2≤d2，最后不能移动玩家输。 问先手后手谁必胜。 题解 考虑后手这样得操作：先手向右，后手向上；先手向上，后手向右。即后手使棋子一直在 y=xy=xy=x 上。 令正整数 zzz 满足 (zk,zk)(zk,zk)(zk,zk) 在圈内且最大。 倘若 (zk+k,zk)(zk+k,zk)(zk+k,zk) 出圈了，那么后手必胜。显然后手执行上面得操作一定能到 (zk,zk)(zk,zk)(zk,zk) ，而此时先手无论走哪都出圈。 若 (zk+k,zk)(zk+k,zk)(zk+k,zk) 在圈内，那先手必胜，考虑先手 ...

Innopolis Open 2020-2021, ualification, contest 1 ,Russia, Innopolis, November, 22, 2020 en-statements 前言 真就暴毙，总共 300min300min300min ，迟到 25min25min25min，前 90min90min90min 暴切 ABCD，rank 363636 吃了个饭+晚读 耗时 60min60min60min ，然后成功在 200min200min200min 后的取得 rank 133133133 的“好成绩” ，调了 两三个小时的 E，人都傻了 problems A - The Battle of Giants 过水已隐藏 B - Tetris Remastered 原题，就是 2018 提高组 T1 铺设道路 C - Optimal Truck 定义一个快递有体积和价值两种元素，现在皮特想要帮 nnn 个人送快递，第 iii 个人有 mim_imi​ 个快递，描述为 (wi,j,ci,j)(w_{i,j},c_{i,j})(wi,j​,ci,j​) ...

fdbc2997623a61cf73a7235ddd7595318b33e643f3cb00c209b6165956d742b312d7b773317bed9ccbd44a1f16bd2ebf34fcf04e3fe7b0cdbe63bfb73a581d3239bbab6c5255396f046b6fcf6821622ff08e3977770430d05fb923fd6d7901137c1d3047a552fe538fc98fc39bbe26f794b5e8bef9804c289fb43e1ebcfb5cc3508b05b3e2cd62fda36c671a209a63f1d440aa16a80fa384b48a1f6c15c8677508f84d2651f8a1deb76e6c1220988d70eb0e724efeba862943d258f31e9430627a09e3e7407dc1f53d9197c19722b01cb8f4957effe7c9167ed00bf0e4ccef7d9ea23ee2165178aec07a511da784b8813b6c9c03a68bb971a ...