【解题报告】NOI2021
哈哈，怎么水平这么低，被踩爆了。
大概是全网最复杂的做法，没有之一。
首先考虑链怎么做，实际上就是区间赋 $1$，两端赋 $0$。扔到树上就先剖一下，一条重链上的边可以直接在线段树上修，关键是重链顶与其父亲之间的轻边，如何维护其是否为 $1$。
记录每一条轻边最后被赋值的时间，这条轻边值为 $1$ 当且仅当父亲最后一次被覆盖的时间与当前轻边最后被赋值的时间相同。因此还需要维护一个带 $\text{chkmax}$ 的线段树。
这可以标记永久化。
于是 $\text{CXY07}$ 就在这样一个 $\text{Day1}$ 中，使用如此巧妙的算法成功花费了巨大多时间，把自己送走。
阳间解法：一条边值为 $1$ 当且仅当两个端点最后被赋值的时间相同，相当于链染色，问链上颜色段个数，这就是 [SDOI2011]染色。
好耶
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define LL long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define ull unsigned long long
#define vec vector
#define pii pair<int, int>
#define scd second
#define fst first
#define pb push_back
#define mp make_pair
const int MAXN = 1.5e5 + 10;
const int INF = 2e9;
//const int mod = 998244353;
//const int mod = 1e9 + 7;
const int G = 3;
const int base = 131;
struct EDGE {
int head[MAXN], siz;
int nxt[MAXN << 1], to[MAXN << 1];
void add(int x, int y) {
nxt[++siz] = head[x];
to[siz] = y, head[x] = siz;
}
void clear() {
for(int i = 0; i <= siz; ++i) nxt[i] = to[i] = 0;
memset(head, 0, sizeof head); siz = 0;
}
} e;
int T, n, m;
int fa[MAXN], siz[MAXN], maxson[MAXN];
int top[MAXN], dfn[MAXN], dfnc, dep[MAXN], link[MAXN];
int sum[MAXN << 2], tag[MAXN << 2], tim[MAXN << 2];
template<typename T> inline void read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while('0' <= c && c <= '9') {a = (a * 10) + (c ^ 48); c = getchar();}
a *= f;
}
void CLEAR() {
memset(sum, 0, sizeof sum), memset(tag, -1, sizeof tag);
memset(tim, 0, sizeof tim);
memset(fa, 0, sizeof fa), memset(dfn, 0, sizeof dfn), dfnc = 0;
memset(top, 0, sizeof top), memset(siz, 0, sizeof siz);
memset(dep, 0, sizeof dep), memset(link, 0, sizeof link);
memset(maxson, 0, sizeof maxson);
e.clear();
}
void DFS1(int x, int f) {
fa[x] = f, siz[x] = 1;
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
if(to == f) continue;
DFS1(to, x); siz[x] += siz[to];
if(!maxson[x] || siz[to] > siz[maxson[x]]) maxson[x] = to;
}
}
void DFS2(int x, int f, int tp) {
dfn[x] = ++dfnc, top[x] = tp, dep[x] = dep[f] + 1;
if(maxson[x]) DFS2(maxson[x], x, tp);
for(int i = e.head[x], to; i; i = e.nxt[i]) {
to = e.to[i];
if(to == maxson[x] || to == f) continue;
DFS2(to, x, to);
}
}
void pushdown(int x, int l, int r) {
if(tag[x] == -1) return;
int mid = (l + r) >> 1;
tag[x << 1] = tag[x], sum[x << 1] = (mid - l + 1) * tag[x];
tag[x << 1 | 1] = tag[x], sum[x << 1 | 1] = (r - mid) * tag[x];
tag[x] = -1;
}
void update(int x, int l, int r, int L, int R, bool opt) {
if(L <= 0 || R <= 0 || L > R) return;
if(L <= l && r <= R)
return tag[x] = opt, sum[x] = (r - l + 1) * opt, void();
int mid = (l + r) >> 1; pushdown(x, l, r);
if(L <= mid) update(x << 1, l, mid, L, R, opt);
if(R > mid) update(x << 1 | 1, mid + 1, r, L, R, opt);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
int query(int x, int l, int r, int L, int R) {
if(L <= 0 || R <= 0 || L > R) return 0;
if(L <= l && r <= R) return sum[x];
int mid = (l + r) >> 1, res = 0; pushdown(x, l, r);
if(L <= mid) res += query(x << 1, l, mid, L, R);
if(R > mid) res += query(x << 1 | 1, mid + 1, r, L, R);
return res;
}
void update_t(int x, int l, int r, int L, int R, int t) {
if(L <= l && r <= R) {
tim[x] = max(tim[x], t);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) update_t(x << 1, l, mid, L, R, t);
if(R > mid) update_t(x << 1 | 1, mid + 1, r, L, R, t);
}
int query_t(int x, int l, int r, int p) {
if(l == r) return tim[x];
int mid = (l + r) >> 1;
if(p <= mid) return max(tim[x], query_t(x << 1, l, mid, p));
else return max(tim[x], query_t(x << 1 | 1, mid + 1, r, p));
}
void UPDATE(int x, int y, int t) {
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
update(1, 1, n, dfn[top[x]] + 1, dfn[x], true);
update(1, 1, n, dfn[maxson[x]], dfn[maxson[x]], false);
update_t(1, 1, n, dfn[top[x]], dfn[x], t);
link[top[x]] = t; x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
update(1, 1, n, dfn[x], dfn[x], false);
update(1, 1, n, dfn[maxson[y]], dfn[maxson[y]], false);
update(1, 1, n, dfn[x] + 1, dfn[y], true);
update_t(1, 1, n, dfn[x], dfn[y], t);
link[x] = 0;
}
int chk(int x) {
int f = fa[x];
if(query_t(1, 1, n, dfn[f]) > link[x]) return 0;
return (bool)(link[x]);
}
int QUERY(int x, int y) {
int res = 0;
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
res += query(1, 1, n, dfn[top[x]] + 1, dfn[x]);
res += chk(top[x]); x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
res += query(1, 1, n, dfn[x] + 1, dfn[y]);
return res;
}
void solve() {
read(n), read(m); CLEAR();
for(int i = 1, x, y; i < n; ++i) {
read(x), read(y);
e.add(x, y), e.add(y, x);
}
DFS1(1, 0); DFS2(1, 0, 1);
for(int t = 1; t <= m; ++t) {
int opt, x, y;
read(opt), read(x), read(y);
if(opt == 1) UPDATE(x, y, t);
else printf("%d\n", QUERY(x, y));
}
}
signed main() {
#ifdef FILE
freopen("edge.in", "r", stdin);
freopen("edge.out", "w", stdout);
#endif
read(T);
while(T--) solve();
return 0;
}哈哈，流下了没有线代基础的眼泪。
考虑 $k=2$，显然交点个数奇偶性 $=$ 匹配的逆序对个数，所以直接邻接矩阵行列式。
那么 $n_i=n_1$ 直接组合意义一下，行列式乘起来即可。这等价于将矩阵先乘起来，再求行列式。
接着，可以观察到一个结论：不管中间的连边是如何的，最后答案就是第一层与最后一层匹配的逆序对数。可以理解为，每次出现一个交点，等价于交换排列中的两个数字，若中间的层的大小不同也是如此。所以最后逆序对数奇偶性 $=$ 交换次数奇偶性 $=$ 交点个数奇偶性。因此矩阵乘起来求行列式即可。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 210;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int T, k, n[MAXN], m[MAXN];
int A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void modadd(int &x, int y) {
x += y;
if(x >= mod) x -= mod;
}
int det() {
int res = 1, n = ::n[1];
for(int i = 1; i <= n; ++i) {
for(int k = i + 1, d; k <= n; ++k) {
while(A[k][i]) {
d = A[i][i] / A[k][i];
for(int j = i; j <= n; ++j) modadd(A[i][j], mod - d * A[k][j] % mod);
for(int j = 1; j <= n; ++j) swap(A[i][j], A[k][j]);
res = mod - res;
}
}
res = res * A[i][i] % mod;
}
return res;
}
void solve() {
read(k);
for(int i = 1; i <= k; ++i) read(n[i]);
for(int i = 1; i < k; ++i) read(m[i]);
int N = *max_element(n + 1, n + k + 1);
memset(A, 0, sizeof A), memset(B, 0, sizeof B), memset(C, 0, sizeof C);
for(int i = 1, x, y; i <= m[1]; ++i) {
read(x), read(y);
A[x][y] = 1;
}
for(int i = 2; i < k; ++i) {
for(int j = 1; j <= N; ++j)
for(int k = 1; k <= N; ++k) B[j][k] = C[j][k] = 0;
for(int j = 1, x, y; j <= m[i]; ++j)
read(x), read(y), B[x][y] = 1;
for(int a = 1; a <= n[1]; ++a)
for(int b = 1; b <= n[i]; ++b)
for(int c = 1; c <= n[i + 1]; ++c)
modadd(C[a][c], A[a][b] * B[b][c] % mod);
swap(A, C);
}
printf("%lld\n", det());
}
signed main () {
#ifdef FILE
freopen("xpath.in", "r", stdin);
freopen("xpath.out", "w", stdout);
#endif
read(T);
while(T--) solve();
return 0;
}哈哈，流下了没有梦想的眼泪。
首先这东西就是 $s$ 能到的点与 $t$ 能反向到的点的交。
题中给的条件，等价于该图缩点后，能找出一张子图为外向树，且与原图效果一致。具体方法是要找到一棵生成树使得所有非树边都是祖先 $\rightarrow$ 后代的形式。每个点只需要选择 $\text{DFS}$ 序最大的前驱作为父亲即可。
这样图就变成了树。在树上 $s$ 能到其子树，$t$ 能通过反向边到从 $t$ 到 $1$ 的链。因此对于 $k=0$，可以先将 $t$ 到根的链上的点打上标记，然后查询 $s$ 子树中标记和。对于剩下的情况，只需要随便更新一下 $t$ 能反向到达的位置，最后查询若干棵子树的标记和即可。复杂度 $\mathcal{O}((n+q)\log^2 n)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 3e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, q, k, rt;
int dfn[MAXN], low[MAXN], stk[MAXN], _top, dfnc;
int col[MAXN], colc, val[MAXN], ind[MAXN], fa[MAXN];
int siz[MAXN], maxson[MAXN], top[MAXN], idfn[MAXN];
bool instk[MAXN], vis[MAXN];
vec<int> G1[MAXN], G2[MAXN], G[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
void Tarjan(int x) {
dfn[x] = low[x] = ++dfnc, stk[++_top] = x;
instk[x] = true;
for(auto to : G1[x]) {
if(!dfn[to]) Tarjan(to), low[x] = min(low[x], low[to]);
else if(instk[to]) low[x] = min(low[x], dfn[to]);
}
if(low[x] == dfn[x]) {
col[x] = ++colc; val[colc] = 1; instk[x] = false;
while(stk[_top] ^ x) {
col[stk[_top]] = colc;
val[colc]++; instk[stk[_top--]] = false;
} _top--;
}
}
void ADD(int x) {
if(vis[x]) return;
vis[x] = true;
for(auto to : G2[x]) {
if(vis[to]) continue;
G[x].pb(to); ADD(to);
}
}
void DFS1(int x) {
siz[x] = 1, maxson[x] = 0;
for(auto to : G[x]) {
fa[to] = x; DFS1(to);
siz[x] += siz[to];
if(!maxson[x] || siz[maxson[x]] < siz[to]) maxson[x] = to;
}
}
void DFS2(int x, int tp) {
dfn[x] = ++dfnc, top[x] = tp; idfn[dfn[x]] = x;
if(maxson[x]) DFS2(maxson[x], tp);
for(auto to : G[x])
if(to ^ maxson[x]) DFS2(to, to);
}
namespace SGT {
int sum[MAXN << 2], tag[MAXN << 2], _v[MAXN << 2];
void pushdown(int x, int l, int r) {
if(tag[x] == -1) return;
tag[x << 1] = tag[x], tag[x << 1 | 1] = tag[x];
sum[x << 1] = tag[x] * _v[x << 1];
sum[x << 1 | 1] = tag[x] * _v[x << 1 | 1];
tag[x] = -1;
}
void build(int x, int l, int r) {
if(l == r) return _v[x] = val[idfn[l]], void();
int mid = (l + r) >> 1;
build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
_v[x] = _v[x << 1] + _v[x << 1 | 1];
}
void make(int x, int l, int r, int L, int R, int v) {
if(L <= l && r <= R)
return sum[x] = v * _v[x], tag[x] = v, void();
int mid = (l + r) >> 1; pushdown(x, l, r);
if(L <= mid) make(x << 1, l, mid, L, R, v);
if(R > mid) make(x << 1 | 1, mid + 1, r, L, R, v);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
int query(int x, int l, int r, int L, int R) {
if(L <= l && r <= R) return sum[x];
int mid = (l + r) >> 1, res = 0; pushdown(x, l, r);
if(L <= mid) res += query(x << 1, l, mid, L, R);
if(R > mid) res += query(x << 1 | 1, mid + 1, r, L, R);
return res;
}
bool _isok(int x, int l, int r, int p) {
if(l == r) return (bool)sum[x];
int mid = (l + r) >> 1; pushdown(x, l, r);
if(p <= mid) return _isok(x << 1, l, mid, p);
else return _isok(x << 1 | 1, mid + 1, r, p);
}
void Make(int x) {
while(x) make(1, 1, colc, dfn[top[x]], dfn[x], true), x = fa[top[x]];
}
int Query(int x) {
return query(1, 1, colc, dfn[x], dfn[x] + siz[x] - 1);
}
bool isok(int x) { return _isok(1, 1, colc, dfn[x]); }
}
using SGT::Make;
using SGT::Query;
using SGT::isok;
bool in(int x, int y) {
return dfn[x] <= dfn[y] && dfn[y] <= dfn[x] + siz[x] - 1;
}
void solve() {
static vec<int> _idx, idx; idx.clear(), _idx.clear();
SGT::make(1, 1, n, 1, n, false);
int s, t, Ans = 0; read(s), read(t); Make(col[t]);
int a[3], b[3]; _idx.pb(col[s]);
for(int i = 1; i <= k; ++i) {
read(a[i]), read(b[i]); a[i] = col[a[i]], b[i] = col[b[i]];
if(isok(b[i])) Make(a[i]);
bool flag = false;
for(auto x : _idx) if(in(x, a[i])) { flag = true; break; }
if(flag) _idx.pb(b[i]);
}
for(int i = 1; i <= k; ++i) {
if(isok(b[i])) Make(a[i]);
bool flag = false;
for(auto x : _idx) if(in(x, a[i])) { flag = true; break; }
if(flag) _idx.pb(b[i]);
}
sort(_idx.begin(), _idx.end());
_idx.erase(unique(_idx.begin(), _idx.end()), _idx.end());
for(auto x : _idx) {
bool flag = true;
for(auto y : _idx) if(x ^ y && in(y, x)) { flag = false; break; }
if(flag) idx.pb(x);
}
for(auto x : idx) Ans += Query(x);
printf("%d\n", Ans);
}
signed main () {
#ifdef FILE
freopen("celebration.in", "r", stdin);
freopen("celebration.out", "w", stdout);
#endif
read(n), read(m), read(q), read(k);
for(int i = 1, x, y; i <= m; ++i)
read(x), read(y), G1[x].pb(y);
for(int i = 1; i <= n; ++i) if(!dfn[i]) Tarjan(i);
for(int i = 1; i <= n; ++i)
for(auto to : G1[i])
if(col[i] ^ col[to]) G2[col[i]].pb(col[to]), ind[col[to]]++;
for(int i = 1; i <= colc; ++i)
sort(G2[i].begin(), G2[i].end(), greater<int>());
memset(dfn, 0, sizeof dfn), dfnc = 0;
for(int i = 1; i <= colc; ++i)
if(!ind[i]) { rt = i; break; }
memset(SGT::tag, -1, sizeof SGT::tag);
ADD(rt); DFS1(rt), DFS2(rt, rt); SGT::build(1, 1, colc);
while(q--) solve();
return 0;
}哈哈，流下了 $\text{100pts}$ 写挂的眼泪。
由于 $k\le 15$，所以若将 $256$ 位分为 $16$ 块，则至少一块内是没有被修改的。且字典是随机生成的，所以当我们钦定了一块没有修改之后，这一块将字典划分为 $2^16$ 个等价类，每一个等价类期望大小 $\dfrac{n}{2^{16}}$，暴力检查即可。复杂度 $\mathcal{O}(\dfrac{16qn}{2^{16}})$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
//#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb emplace_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 4e5 + 10;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m;
int idx[16][70010][10], siz[16][70010];
char ss[MAXN];
bool lastans;
ull a1, a2;
bitset<256> s[MAXN], now;
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
ull myRand(ull &k1, ull &k2) {
ull k3 = k1, k4 = k2;
k1 = k4;
k3 ^= (k3 << 23);
k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
return k2 + k4;
}
void Gen(int n, ull a1, ull a2) {
for(int i = 1; i <= n; i++)
for(int j = 0; j < 256; j++)
s[i][j] = (myRand(a1, a2) & (1ull << 32)) ? 1 : 0;
}
int calc(const bitset<256> &b, int L, int R) {
int res = 0;
for(int i = L; i <= R; ++i) res = (res << 1) | b[i];
return res;
}
int trans(char c) {
if('0' <= c && c <= '9') return c - '0';
return c - 'A' + 10;
}
void solve() {
int k; scanf("%s", ss); read(k);
for(int i = 0, cur; i < 64; ++i) {
cur = trans(ss[i]);
for(int p = 0; p <= 3; ++p) now[i * 4 + 3 - p] = ((cur >> p) & 1) ^ lastans;
}
lastans = false;
for(int i = 0, val; i < 16; ++i) {
val = calc(now, i * 16, i * 16 + 15);
for(int j = 1; j <= siz[i][val]; ++j)
if((s[idx[i][val][j]] ^ now).count() <= k) { lastans = true; break;}
if(lastans) break;
}
printf("%d\n", lastans);
}
signed main () {
#ifdef FILE
freopen("qi.in", "r", stdin);
freopen("qi.out", "w", stdout);
#endif
read(n), read(m), read(a1), read(a2); Gen(n, a1, a2);
for(int i = 1; i <= n; ++i)
for(int j = 0, val; j < 16; ++j) {
val = calc(s[i], j * 16, j * 16 + 15);
idx[j][val][++siz[j][val]] = i;
}
while(m--) solve();
return 0;
}后两题现在鸽了
or2