Jason Fan.

92ce3867a25b048540c10275d83b5b1f57ade36a2745a4b0c5bf6d67dbc1855ffb7c33e3e5663e0b924a29d38efca9b76905a617f337a56be3a8bb794de1cac07c9667a990dcaf7219afe9669ff0f08adb377869c1b1dbcaf1ecea50469df1a52b8048365510ddeb39211fdd8270ef132ce8ceebf955edb555b7f23ff0fc1317c01ece184565ac277058ee4da7a453fbcf48f905e2aba11fecf8d8e33882ebbd8c9b780fb0c474ab537fad05a69ae25edd290242e8fd8fe3a0745d1790040e49164839ce59e1cc013547a74ba73d618b67837fe1ef983467463cf782619b89a8136c2b2d7b19d1d5e837e9912a69cd7414d1f07605606d698 ...

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 ...

92ce3867a25b048540c10275d83b5b1fcf3027232b13c26c1a635d49d722095b87d098a5608cd76a18cf6bcf629ced108dd71cf883b72204a04e5906406485b3d64e1566d986d7c183c1c7aa2bcc6d9eb492d1ccdf3482138a50ab0ada1eb7ad2a997c6c105cb7a7ee44d07bb87696304897e54f36184e9ad31a4af47132d3b659fe15cece9fdf649fd22d43531690b5b917024dba4d2ac253a7286a3179f71659ba302e8244812c8e68f95dfcee29094a66c403604a70d358ae7cb2782e8c6bfc5453323c188570e8520d54882883b88cd387bd5a344f3e3b414b7ef09b36cd23c04e30ab0a2ac5c79c2a2be606c8fd1011a235b6afb5a08 ...

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​) ...