抄一下 \(\color{\black}{n}\color{\red}{antf}\) 的题解 我 nantf 怎么这么强啊…这题我不到半个小时就写掉了…为什么div1的时候只有一个人做掉这个 F 啊…这个不是我 nantf 随随便便就写掉的么… 这个 CF 评分 3300 的题为什么这么水啊，直接1A了（ 我们先考虑不带 star 的，人人会做，\(\sum len_i - len_{fa_i}\)。 考虑 star 在最前面和最后面，最后一个字符插入到 SAM 之前统计一下 \(\sum len_i - len…

构造 \(f(x,y) = xy(x-y)^2\) // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y); --i) using namespace std; using db = doub…

没啥好说的… #include <bits/stdc++.h> using namespace std; #define int long long struct cpx { double x, y; cpx(double _x = 0, double _y = 0) { x = _x; y = _y; } }; cpx operator * (cpx x , cpx y) { return cpx(x.x * y.x - x.y * y.y, x.x * y.y + x.y * y.x); } cpx…

考虑到如果 \(n=2\) 那么显然这个答案是 \(\sum_i [prime_i \leq m]\) 然后我们发现 \(ans(x) = a^n(x)\) \(ans_0\) 就是答案。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (registe…

\(calc(i,j)\) 同样满足四边形不等式，于是没了。 // powered by c++11 // by Isaunoya #include<bits/stdc++.h> #define rep(i , x , y) for(register int i = (x) ; i <= (y) ; ++ i) #define Rep(i , x , y) for(register int i = (x) ; i >= (y) ; -- i) using namespace std ; us…

求 \(p\) 使得所有 \(a_j \leq a_i + p - \sqrt |i-j|\) 发现绝对值不好搞，然后就正反做两遍 // powered by c++11 // by Isaunoya #include<bits/stdc++.h> #define rep(i , x , y) for(register int i = (x) ; i <= (y) ; ++ i) #define Rep(i , x , y) for(register int i = (x) ; i >= (…

题意: 给你 \(n\) 个点，已知 \(m\) 对关系 \([u,v] (|u - v| \leq k)\)，\(k\) 给出，询问 \(q\) 次，每次问你 \([l,r]\) 有多少个连通块。 sol: 显然的回滚莫队，我们按块来分，对于每个块 \(i\)，我们可以把所有 \(l\in block_i\) 丢到 \(i\) 里面，然后我们对 \(r\) 排序，右指针向右移动，然后左指针那边撤销就好了，复杂度 \(n \sqrt n \log n\)，如果在同一块的话直接暴力撤销就好了。 // powered …

这题似乎就 KD-Tree 板子。 矩形加法，矩形乘法，QAQ。 都是离线下来按顺序添加的，所以没有什么关系。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y); --i) using …

复习一下点分治(?) 我们发现 \(a_i \leq 2\times 10^5\) calc 一手，发现质数不会太多，直接暴力就好了。 // powered by c++11 // by Isaunoya #include <bits/stdc++.h> #define rep(i, x, y) for (register int i = (x); i <= (y); ++i) #define Rep(i, x, y) for (register int i = (x); i >= (y);…

这个其实是一个树形的 LIS。 我们考虑到 multiset 怎么维护一个序列，然后扩展到树上，这样就可以了。 怎么维护一个序列呢？ 我们考虑 \(s.size()\) 是当前的 LIS 长度，然后我们插入一个数，要么比最大的要大，比最大的要大直接丢进去，这样长度显然也是+1。 如果比最大的要小？那么我们直接替换掉那个数，这样长度还是不变，微调就可以了，不能相同就直接删掉一个 \(\leq x\) 的数。 在树上的话直接丢到上面启发式合并就好了。 // powered by c++11 // by Isaunoya…