未央の童话镇

集合版本给定一个集合，问出现次数大于一半的数字 权值数组统计权值数组计数，upd后超过一半即为答案 区间版本给一个长度为$n$的序列$a$，$1 \le a_i \le n$ 给定$m$组询问，每次询问一个区间$[l,r]$ 查询是否存在一个数在$[l,r]$中出现的次数大于$\frac{r-l+1}{2}$ 如果存在，输出这个数，否则输出0 单增莫队莫队处理询问 权值数组计数，保存出现次数最多的点权和次数 非可加数据，需单增处理 复杂度$O((m+n)\sqrt{n})$ 可持久化线段树建立可持久化的权值线段树 对于区间查询，在线段树上二分查询R和L-1版本间的数值差符合要求的位置 复杂度$O(nlog_2n)$ 树上版本给定一棵$n$个点的点权树，点权$c_i \le n$ $m$组询问，查询一条树链上是否有出现次数大于长度一半的点权值 有则输出点权，没有则输出$-1$ Solution构造一个偏序对$(a,w)$ 表示一个集合中可能出现次数最多的元素，以及其权值，初始权值为1 当两个集合合并时，如果出现次数最多元素相同，则权值相加 否则权值相减，权值大的减去权值小的，保留权值大的 ...

Problem求解$\sum ^{n}{i=1}\sum ^{i}{j=1}\gcd ( i^{a}-j^{a} , i^b-j^b)[\gcd(i,j)=1][\gcd(a,b)=1]$ $1 \le n \le 10^9$ Solution因为$\gcd(i,j)=1$ 原式等价于$\sum ^{n}{i=1}\sum ^{i}{j=1}i^{\gcd (a,b)}-j^{\gcd (a,b)}[\gcd(i,j)=1][\gcd(a,b)=1]$ 又$\gcd(a,b)=1$ 式子化简为$\sum ^{n}{i=1}\sum ^{i}{j=1}i-j[\gcd(i,j)=1]$ 对称变换得$(\sum ^{n}{i=1}\sum ^{i}{j=1}j[\gcd(i,j)=1])-1$ $\sum^n_{i=1}i[\gcd(i,n)=1]=\frac{n\ast\varphi(n)+[n=1]}{2}$ 所以原式等价于$\frac{(\sum^{n}_{i=1}i\ast\varphi(i))-1}{2}$ 记$S(n)=\sum^{n}_{i=1}i\ast\varphi(i) ...

Problem给定$n(n \le 10^6)$个小球，排着一排，每个球都有一种颜色 现在要求维护两种操作： 将所有颜色为$x$的球变成颜色为$y$的球 查询这排小球有多少连续相同的色段 Solution我们维护每种颜色的位置链表 当发生合并时，将$size$小的链表并入$size$大的链表 枚举$x$颜色每个位置，暴力染成$y$，如果和左右节点染色后颜色相同则答案发生修改 并入时$size$翻倍，因此每个点最多并入$log_2n$次，复杂度$O(nlog_2n)$ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <bits/stdc++.h>using namespace std;const int N = 1000000 + 10;int G[N], nxt[N], v[N], cnt = 0;int id[N], c[N], siz[N];int n, m, op, x, y, ans;void merge ...

Problem给定一个多个3*3的棋盘格，包含#,.,O和X Alice和Bob轮流对这些棋盘格做操作，当一方不能操作了算输 Alice每次可以选择一个O，将其变成# 同时，对以下三种事件挑选一种发生：[不能不选] 选择的格子上下格子均变成# 选择的格子左右格子均变成# 上述两种事件同时发生 Bob每次可以选择一个X，将其变成#，没有任何伴随事件 如果Alice或者Bob始终能赢则对应输出Alice和Bob 否则如果先手或者后手始终能赢则对应输出First和Second 否则直接输出Others Solution$SN={Alice \ can \ get|Bob \ can \ get}$ 非平等博弈只存在三种情况： $SN>0$：Alice总能够取胜 $SN<0$：Bob总能取胜 $SN==0$：后手总能取胜 我们对$3*3$棋盘进行三进制状压 暴力预处理出每种状态下的$SN$，$Multi-SN$情况将$SN$相加判断即可 123456789101112131415161718192021222324252627282930313233343536 ...

Problem游戏开始有四座塔，每座均由正方体叠成，所有正方体是黑色或者白色 玩家$L$和$R$轮流操作，每次选定一个正方体，将正方体及其以上正方体全部拿走 $L$玩家只能选择白色正方体，$R$玩家只能选择黑色正方体，不能操作者输 如果$L$玩家无论先手或者后手都能赢，则称局面为$W-configuration$ 定义子局面为三塔局面即为$C$，对于完整局面$(C,T)$ 如果对于任意塔$T$，$(C2,T)$为$W-configuration$时，$(C1,T)$均为$W-configuration$ 则称$C1$不劣于$C2$，给定$C1$和$C2$，判断$C1$是否不劣于$C2$ Solution考虑一座塔的SN值，当塔为空时$SN={|}=0$ 如果塔包含一个白色正方体，则玩家L拥有可转移到$0$的决策，$SN={0|}=1$ 如果塔包含n个白色正方体，则$SN={0,1,…,n-1|}=n$ 同理塔包含n个黑色正方体时$SN=-n$ 当塔包含n个白色正方体和顶端一个黑色正方体时，$SN={0,1,…,n-1|n}={n-1|n}=n-\frac{1}{2}$ 如果包含n个白色 ...

Problem有$10^9$只小怪兽，第$i$只编号为$i$ 有一张$n$个点，$m$条边的无向图$(n,m \le 10^5)$ 每条边只允许编号在$[l,r]$之间的小怪兽通过 问有多少小怪兽可以从$1$点抵达$n$点 Solution我们对边标号区间$[l,r]$进行离散，最多产生$2*m-1$个区间，左闭右开处理 对区间进行时间分治，在线段树节点上保存覆盖子树所有区间的边$id$ 对线段树DFS遍历，当$1$和$n$连通时将节点包含的编号统计入答案即可 连通性判断用可回溯并查集，复杂度$O(mlog_2m)$ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#include <bits/stdc++.h>using namespace std;const int N = 200000 + 10;// Union ...

Problem给定一张无向边权图，要求维护三个操作 OP1.$[x,y,z]$:在点$x$和点$y$之间加一条边权为z的边，保证之前没有边 OP2.$[x,y]$:将点$x$和$y$之间的边删除，保证之前有边 OP3.$[x,y]$:查询$x$到$y$的路径的异或最小值，可以是非简单路 Solution图上两点异或路径的最小值为生成树上异或距离和树上环的组合 我们以OP3为时间线建线段树，将覆盖操作时间点的边保存在线段树节点 对OP3的线段树进行DFS遍历，用并查集维护两点间的$xor$距离 当成环时将环加入$xor$线性基，在叶节点查询$xor$线性基和$xor$距离组合的最小值即可 线性基空间$O(30)$可以选择直接传参，并查集空间$O(n)$需回溯 时间复杂度$O(mlog_2t)$，$t$为OP3的数量，$m$为总边数 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697 ...

Problem给定$n(n \le 10^5)$个点的坐标$(x,y)$ 选择三条距离相邻距离为r的竖线和三条相邻距离为r的横线，使得线上的点数量最多 Solution考虑枚举横线的选取，数据结构维护竖线的极值 我们把相邻为r的三条竖线的值的和保存在第一条竖线上，即可数据结构维护 考虑枚举的横线和竖线的重复点部分，我们将枚举的横线上的点删除，修改竖线，统计完加回 每个点只会被删除三次，因此总复杂度$O(nlog_2n) $ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>using namespace std;const int L = 100000;const int N = 300000 + 10;vector<int> v[N];int d[N], T[N << 2], M;void upd(int x, int y) { T[M + x] += y; ...

Problem你位于$(0,-1)$到$(0,0)$的路上，每到一个整点，你可以选择左右转或者直行，右转不产生代价，左转的代价为$a$，直行的代价为$b$，求抵达目标点$(x,y)$的最小代价 Solution考虑到右转不花费代价，我们将每四条边缩点，以方格中心为点重构图 在新图中，直行代价为$b$，斜行代价为$a$，先求出通过斜行或者直行走到一条直线上的最小代价，然后求解一条直线的最小代价即可 12345678910111213141516171819202122232425#include <bits/stdc++.h>using namespace std;typedef long long ll;int a, b;ll Calc(ll x, ll y) { if (y < x) swap(x, y); ll res = x * min(a, 2 * b); y -= x; res += (y / 2) * 2 * min(a, b); if (y & 1) res += b; return res;
...