[SZKOpuł raj][POI2014]Rally
我从未见过有像SZKOpuł这样迷的OJ……
很好玩的一道题qwq
首先多源最短路太不好处理，我们搞一个超级源一个超级汇，分别和所有点连边。然后转成求超级源和超级汇的最长路。
我们不妨将这张图拓扑排序。然后我们思考对于拓扑排序得到的序列\(A\)，如果我们删除\(A_i\)的话，哪些路径不会收到影响？如果说有一个路径有一条边\((u, v)\)，满足\(u\)和\(v\)在拓扑排序中分别位于\(A_i\)的两侧，那么这条路径不会受到影响。
反过来考虑每条边\((u, v)\)，过这条边最优的路径一定是从源到\(u\)的最长路加上1再加上从\(v\)到汇的最长路（用两遍DP就能搞出来），他能影响的点在拓扑排序中显然事一段区间。
然后问题变成区间取max了，然后不需要在线，所以随便做了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int maxn = 500005;
const int maxm = 750005;
std::vector<int> G[maxn], RG[maxn];
int inv[maxn], outv[maxn];
void add_edge(int u, int v) {
inv[v] ++; outv[u] ++;
G[u].push_back(v);
RG[v].push_back(u);
}
int T[maxn], ma[maxn];
void toposort() {
std::queue<int> Q; Q.push(0);
int num = 0;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
T[++ num] = u; ma[u] = num;
for(auto v : G[u]) {
inv[v] --;
if(inv[v] == 0) Q.push(v);
}
}
}
int n, m;
int f[maxn], g[maxn];
int dp1(int x) {
if(x == n + 1) return 0;
if(f[x] != -1) return f[x];
f[x] = 0;
for(auto v : G[x]) {
f[x] = std::max(f[x], dp1(v) + 1);
}
return f[x];
}
int dp2(int x) {
if(x == 0) return 0;
if(g[x] != -1) return g[x];
g[x] = 0;
for(auto v : RG[x]) {
g[x] = std::max(g[x], dp2(v) + 1);
}
return g[x];
}
struct Interval {
int l, r, v;
bool operator <(const Interval &res) const {
return v < res.v;
}
};
int E[maxm][2]; std::vector<Interval> I;
void pro_I() {
memset(f, -1, sizeof(f));
memset(g, -1, sizeof(g));
for(int u = 0; u <= n + 1; u ++) {
for(auto v : G[u]) {
int l = ma[u], r = ma[v];
l ++; r --;
if(l <= r) {
Interval seg;
seg.l = l; seg.r = r;
seg.v = dp2(u) + dp1(v) + 1;
I.push_back(seg);
}
}
}
std::sort(I.begin(), I.end());
}
const int maxno = maxn << 2;
int setv[maxno];
void pushdown(int o) {
if(setv[o] != -1) {
int lc = o << 1, rc = o << 1 | 1;
setv[lc] = setv[o]; setv[rc] = setv[o];
setv[o] = -1;
}
}
int ql, qr, v;
void modify(int o, int L, int R) {
if(ql <= L && R <= qr) {
setv[o] = v;
} else {
pushdown(o);
int M = (L + R) / 2;
if(ql <= M) modify(o << 1, L, M);
if(qr > M) modify(o << 1 | 1, M + 1, R);
}
}
int ans[maxn];
void dfs(int o, int L, int R) {
if(L == R) {
ans[L] = setv[o];
} else {
pushdown(o);
int M = (L + R) / 2;
dfs(o << 1, L, M);
dfs(o << 1 | 1, M + 1, R);
}
}
int main() {
memset(setv, -1, sizeof(setv));
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i ++) {
scanf("%d%d", &E[i][0], &E[i][1]);
add_edge(E[i][0], E[i][1]);
}
for(int i = 1; i <= n; i ++) {
if(true) {
add_edge(0, i);
}
}
for(int i = 1; i <= n; i ++) {
if(true) {
add_edge(i, n + 1);
}
}
toposort(); pro_I();
for(auto &seg : I) {
ql = seg.l, qr = seg.r, v = seg.v;
#ifdef LOCAL
printf("(%d, %d) -> %d\n", ql, qr, v);
#endif
modify(1, 1, n + 2);
}
dfs(1, 1, n + 2);
int cho = 1, ret = 0x7fffffff;
for(int i = 2; i <= n + 1; i ++) {
if(ans[i] < ret) {
cho = T[i]; ret = ans[i];
}
}
printf("%d %d\n", cho, ret - 2);
return 0;
}
[LibreOJ 6436][PKUSC2018]神仙的游戏
考场上写炸了FFT的zzs事野蛮人（确信）
兄啊这题怎么还卡常啊！
不妨设\(n = |S|\)。那么如果串有一个长度为$i$的border，就意味着串有一个长度为\(n - i\)的循环节。
那么考虑有两个非?的位置\(i\)和\(j\)（不妨设\(i < j\)），且\(S_i\neq S_j\)。那么我们设\(l = j - i\)，则\(l\)的约数都不能成为循环节的长度，否则会出现矛盾（一个位置又要是0又要是1）。
那么考虑对于所有可能的\(l\)判定是否存在这种不合法的\(i\)与\(j\)。我们利用编辑距离函数：
\[f_l = \sum_{i} A_i A_{i + l}(A_i - A_{i + l})^2\]
这里\(A_i\)相当于\(S_i\)的一个重编码，\(S_i\)为?时应当为0，其他情况一种为1一种为2。这个函数不方便我们卷积，所以我们考虑把\(A\)翻转一下（新的序列称为\(B\)）：
\[
\begin{aligned}
f_l &= \sum_{i} B_{n - i - 1} A_{i + l}(B_{n - i - 1} A_{i + l})^2\\
&= \sum_{i} B_{n - i - 1}^3 A_{i + l} - 2B_{n - i - 1}^2 A_{i + l}^2 + B_{n - i - 1}A_{i + l}^3
\end{aligned}\]
然后问题变成了三个卷积。FFT一下就行了（请注意IDFT只需要一次……否则会被卡常）。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <vector>
using R = double;
struct C {
R x, y;
C(R xx = 0.00, R yy = 0.00) {
x = xx; y = yy;
}
R real() {
return x;
}
};
C operator +(const C &a, const C &b) {
return C(a.x + b.x, a.y + b.y);
}
C operator -(const C &a, const C &b) {
return C(a.x - b.x, a.y - b.y);
}
C operator *(const C &a, const C &b) {
return C(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
using ll = long long;
constexpr R pi = acos(-1);
int flip(int bi, int x) {
int ret = 0;
for(int i = 0; i < bi; i ++) {
if(x & (1 << i)) {
ret += (1 << (bi - i - 1));
}
}
return ret;
}
void FFT(C *A, int bi, R flag = 1.00) {
int n = 1 << bi;
for(int i = 0; i < n; i ++) {
int v = flip(bi, i);
if(i < v) std::swap(A[v], A[i]);
}
for(int L = 1; L < n; L <<= 1) {
R rd = pi / (R(L));
C xi_n(cos(rd), sin(flag * rd));
for(int j = 0; j < n; j += (L << 1)) {
C xi(1.00, 0.00);
for(int i = j; i < j + L; i ++) {
C x = A[i], y = A[i + L];
A[i] = x + xi * y;
A[i + L] = x - xi * y;
xi = xi * xi_n;
}
}
}
}
const int maxn = 500005;
R tot[maxn];
C T[maxn << 2], TT[maxn << 2], D[maxn << 2];
char S[maxn];
inline int conv(char c) {
if(c == '1') return 2;
if(c == '0') return 1;
return 0;
}
int A[maxn], B[maxn];
bool boom[maxn];
int main() {
scanf("%s", S); int n = strlen(S);
for(int i = 0; i < n; i ++) {
A[i] = B[n - 1 - i] = conv(S[i]);
}
int len = 1, bi = 0;
while(len < (2 * n)) {
len <<= 1; bi ++;
}
C z(0.00, 0.00);
// std::fill(T, T + len, z);
// std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i] * A[i] * A[i]; TT[i] = B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + (T[i] * TT[i]);
}
std::fill(T, T + len, z);
std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i] * A[i]; TT[i] = B[i] * B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + C(-2.00, 0.00) * (T[i] * TT[i]);
}
std::fill(T, T + len, z);
std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i]; TT[i] = B[i] * B[i] * B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + (T[i] * TT[i]);
}
FFT(D, bi, -1.00);
for(int i = 1; i < n; i ++) {
if(fabs(D[n - 1 + i].real() / (R(len))) > 0.99) {
boom[i] = true;
}
}
for(int i = 1; i <= n; i ++) {
for(int j = i * 2; j <= n; j += i) {
boom[i] = (boom[i] || boom[j]);
}
}
ll ret = 0LL;
for(int i = 1; i <= n; i ++) {
if(!boom[n - i]) {
ret ^= (ll(i)) * (ll(i));
}
}
printf("%lld\n", ret);
return 0;
}
[BZOJ 5358][Lydsy1805月赛]口算训练
后几页有我会做的题……很好，我很安详，，，
考虑将所有数质因数分解。那么询问\([l, r]\)中所有数的积是否是\(d\)的倍数的本质就是对于\(d\)的每一类质因子，询问区间中该类质因子的指数之和是否不小于\(d\)中的。
考虑到数的范围都很小（不超过100000），我们可以先线性筛预处理，这样一次分解质因数的复杂度就降为了\(O(\log n)\)。至于维护区间每类质因子的指数和这种事……就用主席树处理吧。
代码：
/**************************************************************
Problem: 5358
User: danihao123
Language: C++
Result: Accepted
Time:2804 ms
Memory:68408 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
const int maxn = 100005;
int minp[maxn], mint[maxn], minh[maxn];
int prm[maxn], pcnt;
bool vis[maxn];
void sieve() {
const int N = 100000;
vis[1] = true; pcnt = 0;
for(int i = 2; i <= N; i ++) {
if(!vis[i]) {
prm[++ pcnt] = i;
minp[i] = pcnt; mint[i] = 1;
minh[i] = i;
}
for(int j = 1; j <= pcnt && i * prm[j] <= N; j ++) {
int v = i * prm[j];
vis[v] = true; minp[v] = j;
if(i % prm[j] == 0) {
mint[v] = mint[i] + 1; minh[v] = minh[i] * prm[j];
break;
} else {
mint[v] = 1; minh[v] = prm[j];
}
}
}
}
const int bufsiz = 64 * 1024 * 1024;
char buf[bufsiz]; char *cur;
void init_buf() {
cur = buf;
}
void *alloc(size_t size) {
if(cur + size - buf > bufsiz) {
return malloc(size);
} else {
char *ret = cur; cur += size;
return ret;
}
}
struct Node {
int v; Node *lc, *rc;
};
Node *build_tree(int L, int R) {
Node *ret = (Node*)alloc(sizeof(Node));
ret -> v = 0;
if(L == R) {
ret -> lc = ret -> rc = NULL;
} else {
int M = (L + R) / 2;
ret -> lc = build_tree(L, M);
ret -> rc = build_tree(M + 1, R);
}
return ret;
}
Node *add_p(Node *o, int L, int R, int p, int v) {
Node *ret = (Node*)alloc(sizeof(Node));
ret -> v = o -> v;
ret -> lc = o -> lc; ret -> rc = o -> rc;
if(L == R) {
ret -> v += v;
} else {
int M = (L + R) / 2;
if(p <= M) {
ret -> lc = add_p(ret -> lc, L, M, p, v);
} else {
ret -> rc = add_p(ret -> rc, M + 1, R, p, v);
}
}
return ret;
}
int query(Node *o, int L, int R, int p) {
if(L == R) {
return o -> v;
} else {
int M = (L + R) / 2;
if(p <= M) {
return query(o -> lc, L, M, p);
} else {
return query(o -> rc, M + 1, R, p);
}
}
}
Node *rt[maxn];
void solve() {
init_buf();
int n, m; scanf("%d%d", &n, &m);
rt[0] = build_tree(1, pcnt);
for(int i = 1; i <= n; i ++) {
rt[i] = rt[i - 1];
int x; scanf("%d", &x);
while(x > 1) {
int p = minp[x], t = mint[x];
rt[i] = add_p(rt[i], 1, pcnt, p, t);
x /= minh[x];
}
}
while(m --) {
int l, r, d; scanf("%d%d%d", &l, &r, &d);
bool ok = true;
while(d > 1) {
int p = minp[d], t = mint[d];
int st = query(rt[r], 1, pcnt, p) - query(rt[l - 1], 1, pcnt, p);
if(st < t) {
ok = false; break;
}
d /= minh[d];
}
if(ok) {
puts("Yes");
} else {
puts("No");
}
}
}
int main() {
sieve();
int T; scanf("%d", &T);
while(T --) {
solve();
}
return 0;
}
[BZOJ 4403]序列统计
老早做的题……
一看单调不降就想去用差分……但差分不好推（比下面的颓法要多一步……）。其实我们发现，只要给\([L, R]\)里每种整数分配出现次数，原序列就可以唯一确定了。
因此我们把\([L, R]\)中每个整数的出现次数当做一个变量，他们加起来应该等于一个\([1, n]\)中的整数。用隔板法很容易退出来式子是（令\(l = R - L + 1\)）：
\[\sum_{i = 1}^n \binom{i + l - 1}{l - 1}\]
看起来玩不动了……但是我们给式子加上一个\(\binom{l}{l}\)（其实就是1），然后我们会发现式子可以用杨辉三角的递推式合并成一个组合数，即\(\binom{n + l}{l}\)。然后求这个组合数还需要Lucas定理……
代码：
/**************************************************************
Problem: 4403
User: danihao123
Language: C++
Result: Accepted
Time:908 ms
Memory:16448 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000003LL;
const int maxn = 1000003;
ll pow_mod(ll a, ll b) {
ll ans = 1LL, res = a % ha;
while(b) {
if(1LL & b) ans = (ans * res) % ha;
res = (res * res) % ha;
b >>= 1;
}
return ans;
}
ll f[maxn], g[maxn];
void process() {
f[0] = 1LL;
for(int i = 1; i < maxn; i ++) {
f[i] = (f[i - 1] * (ll(i))) % ha;
}
g[maxn - 1] = pow_mod(f[maxn - 1], ha - 2LL);
for(int i = maxn - 2; i >= 0; i --) {
g[i] = (g[i + 1] * (ll(i + 1))) % ha;
}
}
ll C(int a, int b) {
if(a < b) return 0LL;
return (((f[a] * g[b]) % ha) * g[a - b]) % ha;
}
ll calc(int a, int b) {
if(a < b) return 0LL;
if(b == 0) return 1LL;
if(a < ha && b < ha) {
return C(a, b);
} else {
int as = a % ha, bs = b % ha;
return (C(as, bs) * calc(a / ha, b / ha)) % ha;
}
}
int main() {
process();
int T; scanf("%d", &T);
while(T --) {
int n, l, r; scanf("%d%d%d", &n, &l, &r);
int len = r - l + 1;
printf("%lld\n", (calc(n + len, len) - 1LL + ha) % ha);
}
return 0;
}
[Tsinsen A1300]JZPKIL
卡常的题见过，这么变态的卡常题……可能出题人过于文明，，，下面是卡常记录的一部分：
下面开始颓式子：
[BZOJ 3601]一个人的数论
本来想做JZPKIL的……但卡常太恶心了
上来先颓式子：
\[
\DeclareMathOperator{\id}{id}
\begin{aligned}
f_d(n) &= \sum_{i = 1}^n [(i, n) = 1]i^d\\
&= \sum_{i = 1}^n i^d\sum_{k | n, k | i}\mu(k)\\
&= \sum_{k | n}\mu(k)\sum_{i = 1}^{\frac{n}{k}} (ik)^d\\
&= \sum_{k | n}\mu(k)k^d h_d(\frac{n}{d})\\
&= ((\mu\cdot\id^k)\ast h_d)
\end{aligned}
\]
其中\(h_d\)表示指数为\(d\)时的等幂求和函数。然后我们可能会想，如果这个函数是积性函数，那么我们可以对质因数分解的每一种质因数都求一遍答案，而由于\(\mu\)的存在（对于质数的幂\(p^k\)的因数，只有\(1\)和\(p\)的莫比乌斯函数值不为0），所以需要处理的情况只有两种。
不过很可惜，\(h_d\)显然不是积性函数，所以最后的整个卷积也不是积性函数。但是我们注意到\(h_d\)事一个\(d + 1\)次多项式，所以我们可以把多项式每一项都当成单独的函数，然后每个单独函数卷出来都是一个积性函数。至于求多项式每一项的系数，用伯努利数即可。
代码：
/**************************************************************
Problem: 3601
User: danihao123
Language: C++
Result: Accepted
Time:220 ms
Memory:948 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
typedef long long ll;
ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
ll ans = 1LL, res = a;
while(b) {
if(1LL & b) ans = (ans * res) % ha;
res = (res * res) % ha;
b >>= 1;
}
return ans;
}
ll inv(ll x) {
return pow_mod(x, ha - 2LL);
}
const int maxn = 105;
ll C[maxn][maxn];
void process_C() {
C[0][0] = 1LL;
for(int i = 1; i < maxn; i ++) {
C[i][0] = C[i][i] = 1LL;
for(int j = 1; j < i; j ++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha;
}
}
}
ll B[maxn];
void process_B() {
B[0] = 1LL;
for(int i = 1; i <= 101; i ++) {
B[i] = 1LL;
for(int j = 0; j < i; j ++) {
ll d = (((C[i][j] * B[j]) % ha) * inv(i - j + 1)) % ha;
B[i] = (B[i] - d + ha) % ha;
}
}
}
const int maxw = 1005;
typedef std::pair<ll, ll> pii;
pii P[maxw]; ll dv[maxw][3];
int d, w;
void process_dv() {
for(int i = 1; i <= w; i ++) {
ll p = P[i].first, t = P[i].second;
p %= ha;
dv[i][0] = pow_mod(p, t);
dv[i][1] = pow_mod(p, t - 1LL);
dv[i][2] = pow_mod(p, d);
}
}
ll calc(ll k, int z) {
ll ans = k;
for(int i = 1; i <= w; i ++) {
ll p = P[i].first, t = P[i].second;
p %= ha;
ll f1 = pow_mod(dv[i][0], z), f2 = pow_mod(dv[i][1], z);
ll v1 = (f1 - (dv[i][2] * f2) % ha + ha) % ha;
ans = (ans * v1) % ha;
}
#ifdef LOCAL
printf("Case (%lld, %d) : %lld\n", k, z, ans);
#endif
return ans;
}
int main() {
process_C(); process_B();
scanf("%d%d", &d, &w);
for(int i = 1; i <= w; i ++) {
scanf("%lld%lld", &P[i].first, &P[i].second);
}
process_dv();
ll ans = 0LL;
for(int i = 0; i <= d; i ++) {
ll g = calc((((C[d + 1][i] * B[i]) % ha) * inv(d + 1)) % ha, d + 1 - i);
ans = (ans + g) % ha;
}
printf("%lld\n", ans);
return 0;
}
[BZOJ 2321][BeiJing2011集训]星器
物理题可还行（其实我是想学势能方法，然后误入了……）
给每个星星（假设他在的位置是\((i, j)\)）定义势能\(E_p = i^2 + j^2\)，定义势函数\(\Phi(S)\)来表示状态\(S\)时所有星星势能的和。
然后我们发现，当两个星星互相吸引时（假设他们同行，坐标分别为\((i, j)\)和\((i, k)\)，且$j<k$），他们的坐标会变为\((i, j + 1)\)和\((i, k - 1)\)，势能的总减少量（也就是势函数的减小量）为\(2(k - j - 1)\)。
因此，整个过程中势函数的总减小量，就是答案的两倍。因此算出操作前后的势能做差即可……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
typedef long long ll;
int main() {
int n, m; scanf("%d%d", &n, &m);
ll E = 0LL;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
ll delta = i * i + j * j; ll x;
scanf("%lld", &x); delta *= x;
E += delta;
}
}
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) {
ll delta = i * i + j * j; ll x;
scanf("%lld", &x); delta *= x;
E -= delta;
}
}
E /= 2LL;
printf("%lld\n", E);
return 0;
}
[LibreOJ 2562][SDOI2018]战略游戏
aji圆方树毁我青春，，，省选现场看出来是圆方树但写不出点双滚粗。
显然可以割的点是某两个点的某一条简单路径上的割点，然后两点间的简单路劲的并就是圆方树上的路径，割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并，就需要虚树。
然后做完了……直接建圆方树，每次询问建虚树xjb统计即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
for(int i = 0; i < maxn; i ++) {
G[i].clear();
}
}
void add_edge1(int u, int v) {
G[u].push_back(v); G[v].push_back(u);
}
using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
static std::stack<pii> S;
pre[x] = ++ dcnt; int low = pre[x];
int cld = 0;
for(auto v : G[x]) {
pii e = std::make_pair(x, v);
if(!pre[v]) {
S.push(e); cld ++;
int lowv = dfs(v, x);
low = std::min(low, lowv);
if(lowv >= pre[x]) {
iscut[x] = true; bcc_cnt ++;
bcc[bcc_cnt].clear();
while(true) {
pii ee = S.top(); S.pop();
int f = ee.first, g = ee.second;
if(bccno[f] != bcc_cnt) {
bccno[f] = bcc_cnt;
bcc[bcc_cnt].push_back(f);
}
if(bccno[g] != bcc_cnt) {
bccno[g] = bcc_cnt;
bcc[bcc_cnt].push_back(g);
}
if(f == x && g == v) break;
}
}
} else if(pre[v] < pre[x] && v != fa) {
S.push(e);
low = std::min(low, pre[v]);
}
}
return low;
}
int n, m;
void calc_bcc() {
std::fill(pre, pre + 1 + n, 0);
std::fill(iscut, iscut + 1 + n, false);
std::fill(bccno, bccno + 1 + m, 0);
dcnt = bcc_cnt = 0;
for(int i = 1; i <= n; i ++) {
if(!pre[i]) dfs(i);
}
}
std::vector<int> G2[maxn + maxm];
void cz2() {
for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
G2[u].push_back(v); G2[v].push_back(u);
}
int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
d[x] = s; anc[x][0] = fa; dep[x] = depth;
for(auto v : G2[x]) {
if(v != fa) {
dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
siz[x] += siz[v];
}
}
}
void process_lca() {
memset(anc, -1, sizeof(anc));
cnt2 = 0;
int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
printf("s : %d\n", s);
#endif
for(int j = 1; (1 << j) < s; j ++) {
for(int i = 1; i <= s; i ++) {
int a = anc[i][j - 1];
if(a != -1) anc[i][j] = anc[a][j - 1];
}
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
for(int j = 18; j >= 0; j --) {
int a = anc[x][j];
if(a != -1 && dep[a] >= dep[y]) {
x = a;
}
}
if(x == y) return x;
for(int j = 18; j >= 0; j --) {
int a1 = anc[x][j], a2 = anc[y][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
x = a1; y = a2;
}
}
return anc[x][0];
}
void process() {
calc_bcc();
cz2();
for(int i = 1; i <= bcc_cnt; i ++) {
int id = n + i;
for(auto u : bcc[i]) {
add_edge2(u, id);
}
}
process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
std::vector<int> V;
for(int i = 1; i <= sz; i ++) {
int x; scanf("%d", &x);
V.push_back(x);
}
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::set<int> ds; ds.insert(V[0]);
for(int i = 1; i < sz; i ++) {
ds.insert(V[i]);
ds.insert(lca(V[i - 1], V[i]));
}
V.clear(); for(auto u : ds) V.push_back(u);
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::stack<int> S;
int ans = 0;
for(int i = 0; i < V.size(); i ++) {
int u = V[i];
while(!S.empty() && !is_anc(S.top(), u)) {
S.pop();
}
if(!S.empty()) {
#ifdef LOCAL
printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
ans += get_delta(u, S.top());
}
S.push(u);
}
for(auto u : ds) {
if(u <= n) ans ++;
}
ans -= sz;
return ans;
}
int main() {
int T; scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &m); cz1();
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
add_edge1(u, v);
}
process();
int q; scanf("%d", &q);
while(q --) {
int sz; scanf("%d", &sz);
printf("%d\n", query(sz));
#ifdef LOCAL
fflush(stdout);
#endif
}
}
return 0;
}
[LibreOJ 121]可离线动态图连通性
LCT+扫描线应该随便做吧这题……但我学了一下线段树分治
这个问题有删除非常的恶心，让我们考虑怎么去掉删除的影响。
每条边存在的时间段是一个区间，而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标，对所有询问建线段树，然后对一段区间加边就是一个区间打标记，最后扫一遍线段树就可以解决问题。
同时需要注意，这个题在DFS线段树的过程中，往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩，但是可以按轶合并。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
Node *fa; int siz;
Node() {
fa = NULL; siz = 1;
}
void sc(Node *c) {
siz += c -> siz;
c -> fa = this;
}
void brk() {
fa -> siz -= siz;
fa = NULL;
}
};
Node *r[maxn];
int n;
void init_set() {
for(int i = 1; i <= n; i ++) {
r[i] = new Node();
}
}
Node *get_fa(Node *x) {
if(x -> fa == NULL) {
return x;
} else {
return get_fa(x -> fa);
}
}
Node *link_set(Node *x, Node *y) {
if(x -> siz < y -> siz) std::swap(x, y);
x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
return (get_fa(x) == get_fa(y));
}
const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
if(ql <= L && R <= qr) {
event[o].push_back(e);
} else {
int M = (L + R) / 2;
if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
}
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
if(L == R) {
que[o] = e;
} else {
int M = (L + R) / 2;
if(p <= M) {
add_query(o << 1, L, M, p, e);
} else {
add_query(o << 1 | 1, M + 1, R, p, e);
}
}
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
for(auto e : event[o]) {
int u = e.first, v = e.second;
if(!is_same(r[u], r[v])) {
#ifdef LOCAL
printf("Merging %d and %d.\n", u, v);
#endif
S.push(std::make_pair(merge_set(r[u], r[v]), o));
}
}
if(L == R) {
int u = que[o].first, v = que[o].second;
if(u == -1 && v == -1) {
ret[L] = -1;
} else {
if(is_same(r[u], r[v])) {
ret[L] = 1;
} else {
ret[L] = 0;
}
}
} else {
int M = (L + R) / 2;
solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
}
while(!S.empty() && S.top().second >= o) {
Node *u = S.top().first; S.pop();
u -> brk();
}
}
std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
int m; scanf("%d%d", &n, &m);
init_set();
pii fl(-1, -1);
for(int i = 1; i <= m; i ++) {
pii e; int op;
scanf("%d%d%d", &op, &e.first, &e.second);
if(e.first > e.second) {
std::swap(e.first, e.second);
}
if(op == 2) {
add_query(1, 1, m, i, e);
} else {
add_query(1, 1, m, i, fl);
V.push_back(e);
if(op == 0) {
ma[e].push(i);
} else {
int last = ma[e].top(); ma[e].pop();
add_event(1, 1, m, last, i - 1, e);
}
}
}
for(auto e : V) {
while(!ma[e].empty()) {
int g = ma[e].top(); ma[e].pop();
add_event(1, 1, m, g, m, e);
}
}
solve(1, 1, m);
for(int i = 1; i <= m; i ++) {
if(ret[i] != -1) {
if(ret[i]) {
puts("Y");
} else {
puts("N");
}
}
}
return 0;
}
[LibreOJ 2558][LNOI2014]LCA
现在才做这题TAT
如果询问的是一个子集和\(z\)的所有LCA的深度的和，那可以把子集里每一个元素到根的路径全部加1，然后根到\(z\)的路径上的和就是答案。
如果是区间的话，每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间，然后离线，给询问排个序然后就好做了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
using ll = long long;
const ll ha = 201314LL;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
const int maxno = maxn << 2;
ll sumv[maxno], addv[maxno];
void maintain(int o) {
sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;
}
void paint(int o, int L, int R, ll v) {
v %= ha;
addv[o] += v; addv[o] %= ha;
sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;
}
void pushdown(int o, int L, int R) {
if(addv[o] != 0LL) {
ll v = addv[o]; addv[o] = 0;
int M = (L + R) / 2;
int lc = o << 1, rc = o << 1 | 1;
paint(lc, L, M, v); paint(rc, M + 1, R, v);
}
}
int ql, qr; ll v;
void modify(int o, int L, int R) {
if(ql <= L && R <= qr) {
paint(o, L, R, v);
} else {
pushdown(o, L, R);
int M = (L + R) / 2;
if(ql <= M) modify(o << 1, L, M);
if(qr > M) modify(o << 1 | 1, M + 1, R);
maintain(o);
}
}
ll query(int o, int L, int R) {
if(ql <= L && R <= qr) {
return sumv[o];
} else {
pushdown(o, L, R);
int M = (L + R) / 2;
ll ans = 0;
if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha;
if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha;
return ans;
}
}
int siz[maxn], fa[maxn], dep[maxn], hson[maxn];
void dfs_1(int x, int f = 0, int depth = 0) {
fa[x] = f; dep[x] = depth; siz[x] = 1;
int maxs = 0;
for(auto v : G[x]) {
if(v != f) {
dfs_1(v, x, depth + 1);
siz[x] += siz[v];
if(siz[v] > maxs) {
maxs = siz[v]; hson[x] = v;
}
}
}
}
int top[maxn], tid[maxn], dfn[maxn];
void dfs_2(int x, int a) {
static int cnt = 0; cnt ++;
top[x] = a; tid[cnt] = x; dfn[x] = cnt;
if(hson[x]) {
dfs_2(hson[x], a);
} else {
return;
}
for(auto v : G[x]) {
if(v != fa[x] && v != hson[x]) {
dfs_2(v, v);
}
}
}
int n;
void update(int x, int y, const ll &delta) {
if(top[x] == top[y]) {
if(dfn[x] > dfn[y]) std::swap(x, y);
ql = dfn[x], qr = dfn[y]; v = delta;
modify(1, 1, n); return;
}
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
ql = dfn[top[x]], qr = dfn[x]; v = delta;
modify(1, 1, n);
update(fa[top[x]], y, delta);
}
ll query(int x, int y) {
if(top[x] == top[y]) {
if(dfn[x] > dfn[y]) std::swap(x, y);
ql = dfn[x], qr = dfn[y];
return query(1, 1, n);
}
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
ql = dfn[top[x]], qr = dfn[x];
ll ret = query(1, 1, n);
return (ret + query(fa[top[x]], y)) % ha;
}
struct Q {
int l, z;
int id; ll p;
bool operator <(const Q &res) const {
if(l == res.l) {
return id < res.id;
} else {
return l < res.l;
}
}
};
Q que[maxn << 1];
ll ans[maxn];
int main() {
int q; scanf("%d%d", &n, &q);
for(int i = 2; i <= n; i ++) {
int f; scanf("%d", &f); f ++;
add_edge(f, i);
}
dfs_1(1); dfs_2(1, 1);
for(int i = 1; i <= q; i ++) {
int l, r, z; scanf("%d%d%d", &l, &r, &z);
l ++; r ++; z ++;
Q &L = que[i * 2 - 1]; Q &R = que[i * 2];
L.id = R.id = i; L.p = -1; R.p = 1;
L.z = R.z = z; L.l = l - 1; R.l = r;
}
std::sort(que + 1, que + 1 + 2 * q);
int p = 0;
for(int i = 1; i <= 2 * q; i ++) {
const Q &t = que[i];
while(p < t.l) {
p ++; update(1, p, 1);
}
ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha;
}
for(int i = 1; i <= q; i ++) {
printf("%lld\n", ans[i]);
}
return 0;
}
