杂题小记（2023.03.21）

杂题小记（2023.03.21）更好的阅读体验戳此进入实际上是 2023.03.17-2023.03.21LG-P3233 [HNOI2014]世界树LG-P5360 [SDOI2019]世界地图LG-P4197 PeaksLG-P4768 [NOI2018] 归程LG-P4899 [IOI2018] werewolf 狼人LG-P1446 [HNOI2008] CardsUVA11255 NecklaceUPD

更好的阅读体验戳此进入

实际上是 2023.03.17-2023.03.21

LG-P3233 [HNOI2014]世界树

细节怪。

需要建虚树很套路，然后考虑维护虚树内和虚树外的，对于虚树内的是平凡的，对于虚树外难点在于考虑一条链的分割，不难想到通过倍增实现即可，思路比较清晰不是很难但是码量巨大。


x
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define S(i) (S.at(i - 1))
24
#define LIM (310000)
25
#define INF (0x3f3f3f3f)
26

27
template < typename T = int >
28
inline T read(void);
29

30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    OPNEW;
34
}ed[2100000];
35
ROPNEW;
36
Edge* head[LIM];
37
Edge* vhead[LIM];
38

39
int N, Q, M;
40
int dep[LIM], siz[LIM], dfn[LIM], fa[LIM], top[LIM], idx[LIM], hson[LIM];
41
int lg2[LIM], mndis[LIM], mnp[LIM], ans[LIM], qs[LIM];
42
int jmp[LIM][20]; //max 2^19
43
basic_string < int > S;
44
bitset < LIM > isKey;
45

46
int main(){
47
    memset(mndis, 0x3f, sizeof mndis);
48
    N = read();
49
    for(int i = 1; i <= N - 1; ++i){
50
        int s = read(), t = read();
51
        head[s] = new Edge{head[s], t};
52
        head[t] = new Edge{head[t], s};
53
    }
54
    auto Init = [](void)->void{
55
        lg2[1] = 0;
56
        for(int i = 2; i <= N; ++i)lg2[i] = lg2[i >> 1] + 1;
57
    }; Init();
58
    auto dfs_pre = [](auto&& self, int p = 1, int fa = 0)->void{
59
        dep[p] = dep[fa] + 1, ::fa[p] = fa, siz[p] = 1, jmp[p][0] = fa;
60
        for(auto i = head[p]; i; i = i->nxt){
61
            if(SON == fa)continue;
62
            self(self, SON, p);
63
            siz[p] += siz[SON];
64
            if(siz[SON] > siz[hson[p]])hson[p] = SON;
65
        }
66
    }; dfs_pre(dfs_pre);
67
    auto dfs_make = [](auto&& self, int p = 1, int top = 1)->void{
68
        static int cdfn(0);
69
        dfn[p] = ++cdfn, idx[cdfn] = p, ::top[p] = top;
70
        if(hson[p])self(self, hson[p], top);
71
        for(auto i = head[p]; i; i = i->nxt)
72
            if(SON != fa[p] && SON != hson[p])self(self, SON, SON);
73
    }; dfs_make(dfs_make);
74
    auto LCA = [](int s, int t)->int{
75
        while(top[s] != top[t]){
76
            if(dep[top[s]] < dep[top[t]])swap(s, t);
77
            s = fa[top[s]];
78
        }if(dep[s] < dep[t])swap(s, t);
79
        return t;
80
    };
81
    auto Handle = [](void)->void{
82
        for(int i = 1; i <= N; ++i)
83
            for(int j = 1; j <= 19; ++j)
84
                jmp[i][j] = jmp[jmp[i][j - 1]][j - 1];
85
    }; Handle();
86
    auto BuildVT = [LCA](void)->void{
87
        sort(S.begin(), S.end(), [](const int &a, const int &b)->bool{return dfn[a] < dfn[b];});
88
        int len = S.size();
89
        for(int i = 1; i <= len - 1; ++i)S += LCA(S(i), S(i + 1));
90
        sort(S.begin(), S.end(), [](const int &a, const int &b)->bool{return dfn[a] < dfn[b];});
91
        S.erase(unique(S.begin(), S.end()), S.end());
92
        for(auto it = S.begin(); it != S.end() && next(it) != S.end(); advance(it, 1)){
93
            int lca = LCA(*it, *next(it));
94
            vhead[lca] = new Edge{vhead[lca], *next(it)};
95
            vhead[*next(it)] = new Edge{vhead[*next(it)], lca};
96
        }
97
    };
98
    auto QueryChain = [](int s, int t)->void{
99
        int p = s;
100
        for(int i = lg2[dep[s]]; i >= 0; --i)
101
            if(dep[jmp[p][i]] > dep[t])p = jmp[p][i];
102
        ans[mnp[t]] -= siz[p];
103
        int spl = s;
104
        for(int i = lg2[dep[s]]; i >= 0; --i){
105
            int lens = dep[s] - dep[jmp[spl][i]] + mndis[s], lent = dep[jmp[spl][i]] - dep[t] + mndis[t];
106
            if(dep[jmp[spl][i]] > dep[t] && (lens < lent || (lens == lent && mnp[s] < mnp[t])))spl = jmp[spl][i];
107
        }ans[mnp[s]] += siz[spl] - siz[s], ans[mnp[t]] += siz[p] - siz[spl];
108
    };
109
    auto dfs_upward = [](auto&& self, int p = 1, int fa = 0)->void{
110
        for(auto i = vhead[p]; i; i = i->nxt){
111
            if(SON == fa)continue;
112
            self(self, SON, p);
113
            int cdis = dep[SON] - dep[p];
114
            if(mndis[SON] + cdis < mndis[p])mndis[p] = mndis[SON] + cdis, mnp[p] = mnp[SON];
115
            else if(mndis[SON] + cdis == mndis[p])mnp[p] = min(mnp[p], mnp[SON]);
116
        }if(isKey[p])mndis[p] = 0, mnp[p] = p;
117
    };
118
    auto dfs_downward = [QueryChain](auto&& self, int p = 1, int fa = 0)->void{
119
        for(auto i = vhead[p]; i; i = i->nxt){
120
            if(SON == fa)continue;
121
            int cdis = dep[SON] - dep[p];
122
            if(mndis[p] + cdis < mndis[SON])mndis[SON] = mndis[p] + cdis, mnp[SON] = mnp[p];
123
            else if(mndis[p] + cdis == mndis[SON])mnp[SON] = min(mnp[SON], mnp[p]);
124
            QueryChain(SON, p);
125
            self(self, SON, p);
126
        }ans[mnp[p]] += siz[p];
127
    };
128
    Q = read();
129
    while(Q--){
130
        for(auto p : S)vhead[p] = npt, mndis[p] = INF, mnp[p] = 0, ans[p] = 0, isKey[p] = false;
131
        S.clear();
132
        M = read();
133
        for(int i = 1; i <= M; ++i)S += (qs[i] = read()), isKey[S.back()] = true;
134
        if(!isKey[1])S += 1;
135
        BuildVT();
136
        dfs_upward(dfs_upward), dfs_downward(dfs_downward);
137
        for(int i = 1; i <= M; ++i)printf("%d%c", ans[qs[i]], i == M ? '\n' : ' ');
138
    }
139
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
140
    return 0;
141
}
142

143
template < typename T >
144
inline T read(void){
145
    T ret(0);
146
    int flag(1);
147
    char c = getchar();
148
    while(c != '-' && !isdigit(c))c = getchar();
149
    if(c == '-')flag = -1, c = getchar();
150
    while(isdigit(c)){
151
        ret *= 10;
152
        ret += int(c - '0');
153
        c = getchar();
154
    }
155
    ret *= flag;
156
    return ret;
157
}

LG-P5360 [SDOI2019]世界地图

简单提一下一些细节问题。

首先考虑一下本题的大致思路，构建前缀 MST 和后缀 MST 每次询问合成即可。合成时通过将两个 MST 所有边合成为新的 MST 然后通过虚树的思想只保留关键点，将树简化以保证点数级别。

点的重标号

这是我第一个卡住的点，最开始的思路就是朴素地开一堆 unordered_map 然后手写 pair < int, int > 的哈希建出来一堆映射，将坐标映射为点，然后每次建 MST 或者虚树的时候都重搞一遍，写了一会发现这东西常数似乎有些爆炸，且细节巨多，翻了一下题解区理解了一会才明白这个重标号点的思路：

$[1, i - 1] \to [1, i]$ $1$ $i - 1$ $1$ $i - 1\ \to i$ $n$ $1$ $n$ $1$ $A$ $B$ $B$ $A$ $A$ $n$ $B$ $n$ $A$ $n$ $B$ $n$ 作为关键点，这样即可优美地解决点的重标号。

关键点的选取

$1$ $1$ 列为关键点显然是非必要的，但维护后就可以同时适配合并前后缀，应该属于是写法的优化。

虚树的构建

$O(n)$ 的两次 dfs 了。

前后缀的合并

$A$ $n$ $B$ $n$ ，如果前缀在前后缀在后连边就会反了。

资源的回收

500MiB $2 \times 10^7$ 条边，这是不够用的，所以需要实现对边的复用，对应着代码中的：


xxxxxxxxxx
1
1
void* Edge::operator new(size_t){static Edge* P = ed; return P++;}

改为：


xxxxxxxxxx
1
1
void* Edge::operator new(size_t){static Edge* P = ed; if(P - ed > 20100000)P = ed; return P++;}

注意这里无需清空边的内存池是因为每次我调用 new 的时候都对其进行了初始化列表的初始化。

代码大同小异。


xxxxxxxxxx
145
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; if(P - ed > 20100000)P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, M, Q;
27
unsigned int SA, SB, SC;
28
int lim;
29
struct edge{int s, t; int val;};
30
int nxtR[110][11000], nxtL[110][11000];
31

32
struct Edge{
33
    Edge* nxt;
34
    int to;
35
    int val;
36
    OPNEW;
37
}ed[21000000];
38
ROPNEW;
39

40
class VirtualTree{
41
private:
42
    Edge* head[1100];
43
public:
44
    bitset < 1100 > isKey;
45
    bitset < 1100 > invt;
46
    basic_string < edge > edgs;
47
    void Clear(void){memset(head, 0, sizeof head);  isKey.reset(); invt.reset(); edgs.clear();}
48
    VirtualTree(void){Clear();}
49
    void AddEdge(int s, int t, int val){
50
        head[s] = new Edge{head[s], t, val};
51
        head[t] = new Edge{head[t], s, val};
52
    }
53
    bool dfs_pre(int p = 1, int fa = 0){
54
        int cnt(0);
55
        for(auto i = head[p]; i; i = i->nxt)
56
            if(SON != fa)cnt += dfs_pre(SON, p);
57
        invt[p] = isKey[p] | (cnt >= 2);
58
        return invt[p] | bool(cnt);
59
    }
60
    void dfs_link(int p = 1, int lst = 0, int mxv = 0, int fa = 0){
61
        if(invt[p]){
62
            if(lst)edgs += edge{lst, p, mxv};
63
            lst = p, mxv = 0;
64
        }
65
        for(auto i = head[p]; i; i = i->nxt)
66
            if(SON != fa)dfs_link(SON, lst, max(mxv, i->val), p);
67
    }
68
}vt;
69

70
class MST{
71
private:
72
public:
73
    int tot;
74
    ll sum;
75
    basic_string < edge > edgs;
76
    void Clear(void){edgs.clear(); sum = 0; tot = 0;}
77
    MST(void){Clear();}
78
    ll Query(void){ll ret(sum); for(auto edg : edgs)ret += edg.val; return ret;}
79
}pre[11000], suf[11000];
80

81
class UnionFind{
82
private:
83
    int fa[1100];
84
public:
85
    void Clear(void){for(int i = 0; i <= 1010; ++i)fa[i] = i;}
86
    UnionFind(void){Clear();}
87
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
88
    void Union(int s, int t){if(Find(s) != Find(t))fa[Find(s)] = Find(t);}
89
}uf;
90

91
int main(){
92
    N = read(), M = read();
93
    auto GetWeight = [](void)->int{SA ^= SA << 16; SA ^= SA >> 5; SA ^= SA << 1; unsigned int t = SA;SA = SB;SB = SC;SC ^= t ^ SA;return SC % lim + 1;};
94
    auto Gen = [GetWeight](void)->void{
95
        scanf("%u%u%u%d", &SA, &SB, &SC, &lim);
96
        for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j)nxtR[i][j] = GetWeight();
97
        for(int i = 1; i < N; ++i)for(int j = 1; j <= M; ++j)nxtL[i][j] = GetWeight();
98
    }; Gen();
99
    auto MergeMST = [](const MST &A, const MST &B, int idx)->auto{
100
        unordered_map < int, int > mp;
101
        ll cur(0);
102
        MST ret;
103
        ret.edgs += A.edgs;
104
        for(auto edg : B.edgs)ret.edgs += edge{edg.s + A.tot, edg.t + A.tot, edg.val};
105
        for(int i = 1; i <= N; ++i)ret.edgs += edge{A.tot - N + i, A.tot + i, nxtR[i][idx]};
106
        sort(ret.edgs.begin(), ret.edgs.end(), [](const edge &a, const edge &b)->bool{return a.val < b.val;});
107
        uf.Clear(), vt.Clear();
108
        for(int i = 1; i <= N; ++i)vt.isKey[i] = vt.isKey[A.tot + B.tot - i + 1] = true;
109
        for(auto edg : ret.edgs)
110
            if(uf.Find(edg.s) != uf.Find(edg.t))vt.AddEdge(edg.s, edg.t, edg.val), uf.Union(edg.s, edg.t), cur += edg.val;
111
        vt.dfs_pre(), vt.dfs_link();
112
        ret.edgs = vt.edgs; ret.tot = 0;
113
        for(int i = 1; i <= A.tot + B.tot; ++i)if(vt.invt[i])mp[i] = ++ret.tot;
114
        for(auto &edg : ret.edgs)edg.s = mp[edg.s], edg.t = mp[edg.t], cur -= edg.val;
115
        ret.sum = A.sum + B.sum + cur;
116
        return ret;
117
    };
118
    for(int j = 1; j <= M; ++j)for(int i = 1; i < N; ++i)
119
        pre[j].edgs += edge{i, i + 1, nxtL[i][j]}, suf[j].edgs += edge{i, i + 1, nxtL[i][j]}, suf[j].tot = pre[j].tot = N;
120
    for(int j = 2; j < M; ++j)pre[j] = MergeMST(pre[j - 1], pre[j], j - 1);
121
    for(int j = M - 1; j > 1; --j)suf[j] = MergeMST(suf[j], suf[j + 1], j);
122
    Q = read();
123
    while(Q--){
124
        int l = read(), r = read();
125
        printf("%lld\n", MergeMST(suf[r + 1], pre[l - 1], M).Query());
126
    }
127
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
128
    return 0;
129
}
130

131
template < typename T >
132
inline T read(void){
133
    T ret(0);
134
    int flag(1);
135
    char c = getchar();
136
    while(c != '-' && !isdigit(c))c = getchar();
137
    if(c == '-')flag = -1, c = getchar();
138
    while(isdigit(c)){
139
        ret *= 10;
140
        ret += int(c - '0');
141
        c = getchar();
142
    }
143
    ret *= flag;
144
    return ret;
145
}

LG-P4197 Peaks

考虑建出 Kruskal 重构树，此时对于每次查询可以在线转换为倍增找到最优祖先之后整个子树中对叶子节点的静态区间第 k 大，用主席树维护即可，细节略多。


xxxxxxxxxx
151
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (110000)
24
#define LIMV (int)(1e9)
25
#define MID ((gl + gr) >> 1)
26
#define cnt(p) (p ? p->cnt : 0)
27

28
template < typename T = int >
29
inline T read(void);
30

31
int N, M, Q;
32
struct Node{
33
    Node *ls, *rs;
34
    int cnt;
35
    OPNEW;
36
}nd[LIM << 5];
37
ROPNEW_NODE;
38
Node* root[LIM];
39

40
class UnionFind{
41
private:
42
    int fa[LIM << 1];
43
public:
44
    void Clear(void){for(int i = 1; i <= (LIM << 1) - 10; ++i)fa[i] = i;}
45
    UnionFind(void){Clear();}
46
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
47
    void Union(int s, int t){if(Find(s) != Find(t))fa[Find(s)] = Find(t);}
48
}uf;
49

50
struct edge{int s, t; int val;};
51
basic_string < edge > edgs;
52

53
struct Edge{
54
    Edge* nxt;
55
    int to;
56
    OPNEW;
57
}ed[2100000];
58
ROPNEW;
59
Edge* head[LIM << 1];
60
// unordered_map < int, pair < int, int > > rng;
61
int ccnt;
62
int ind[LIM << 1];
63
int val[LIM << 1];
64
int mnp[LIM << 1], mxp[LIM << 1];
65
int jmp[LIM << 2][20]; //max - 18
66
int idx[LIM];
67

68
int main(){
69
    memset(val, 0x3f, sizeof val);
70
    auto Pushup = [](Node* p)->void{
71
        if(!p)return;
72
        p->cnt = cnt(p->ls) + cnt(p->rs);
73
    };
74
    auto Insert = [Pushup](auto&& self, int val, int cnt, Node* lst, int gl = 0, int gr = LIMV)->Node*{
75
        Node* p = lst ? new Node(*lst) : new Node{npt, npt, 0};
76
        if(gl == gr)return p->cnt += cnt, p;
77
        if(val <= MID)p->ls = self(self, val, cnt, p->ls, gl, MID);
78
        else p->rs = self(self, val, cnt, p->rs, MID + 1, gr);
79
        return Pushup(p), p;
80
    };
81
    auto QueryKth = [](auto&& self, int k, Node* px, Node* py, int gl = 0, int gr = LIMV)->int{
82
        // printf("Querying gl = %d, gr = %d, precnt = %d, curcnt = %d, k = %d\n", gl, gr, cnt(px), cnt(py), k);
83
        if(gl == gr)return k > (cnt(py) - cnt(px)) ? -1 : gl;
84
        if(!py)return -1;
85
        int leftCnt = (py ? cnt(py->ls) : 0) - (px ? cnt(px->ls) : 0);//printf("leftcnt = %d\n", leftCnt);
86
        if(k <= leftCnt)return self(self, k, px ? px->ls : npt, py->ls, gl, MID);
87
        else return self(self, k - leftCnt, px ? px->rs : npt, py->rs, MID + 1, gr);
88
    };
89
    ccnt = N = read(), M = read(), Q = read();
90
    // for(int i = 1; i <= N; ++i)root[i] = Insert(Insert, val[i] = read(), 1, root[i - 1]);
91
    for(int i = 1; i <= N; ++i)val[i] = read();
92
    for(int i = 1; i <= M; ++i){
93
        int s = read(), t = read(), v = read();
94
        edgs += edge{s, t, v};
95
    }sort(edgs.begin(), edgs.end(), [](const edge &a, const edge &b)->bool{return a.val < b.val;});
96
    auto Kruskal = [](void)->void{
97
        for(auto [s, t, v] : edgs){
98
            int fs = uf.Find(s), ft = uf.Find(t);
99
            if(fs != ft){
100
                int fap = ++ccnt;
101
                val[fap] = v;
102
                ++ind[fs], ++ind[ft];
103
                head[fap] = new Edge{head[fap], fs};
104
                head[fap] = new Edge{head[fap], ft};
105
                // printf("linking fa = %d, p = [%d, %d], val = %d\n", fap, fs, ft, v);
106
                uf.Union(fs, fap), uf.Union(ft, fap);
107
            }
108
        }
109
    }; Kruskal();
110
    auto dfs = [](auto&& self, int p, int fa = 0)->void{
111
        static int cur(1);
112
        jmp[p][0] = fa, mnp[p] = cur;
113
        for(auto i = head[p]; i; i = i->nxt)
114
            self(self, SON, p);
115
        if(!head[p])idx[cur++] = p;
116
        mxp[p] = cur - 1;
117
        // printf("Complete dfs [%d, %d], p = %d\n", mnp[p], mxp[p], p);
118
    };
119
    
120
    for(int i = 1; i <= ccnt; ++i)if(!ind[i]){dfs(dfs, i); break;}
121
    for(int i = 1; i <= N; ++i)root[i] = Insert(Insert, val[idx[i]], 1, root[i - 1]);//, printf("test mx i = %d, mx2 = %d, cnt = %d, lc = %d, rc = %d, val = %d\n", i, QueryKth(QueryKth, 2, npt, root[i]), root[i]->cnt, cnt(root[i]->ls), cnt(root[i]->rs), val[idx[i]]);
122
    for(int i = 1; i <= 18; ++i)
123
        for(int p = 1; p <= ccnt; ++p)
124
            jmp[p][i] = jmp[jmp[p][i - 1]][i - 1];
125
    while(Q--){
126
        int p = read(), lim = read(), k = read();
127
        for(int i = 18; i >= 0; --i)
128
            if(val[jmp[p][i]] <= lim)p = jmp[p][i];
129
        // printf("Querying l = %d, r = %d, k = %d\n", mnp[p], mxp[p], k);
130
        if(k > mxp[p] - mnp[p] + 1){printf("-1\n"); continue;}
131
        printf("%d\n", QueryKth(QueryKth, mxp[p] - mnp[p] + 1 - k + 1, root[mnp[p] - 1], root[mxp[p]]));
132
    }
133
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
134
    return 0;
135
}
136

137
template < typename T >
138
inline T read(void){
139
    T ret(0);
140
    int flag(1);
141
    char c = getchar();
142
    while(c != '-' && !isdigit(c))c = getchar();
143
    if(c == '-')flag = -1, c = getchar();
144
    while(isdigit(c)){
145
        ret *= 10;
146
        ret += int(c - '0');
147
        c = getchar();
148
    }
149
    ret *= flag;
150
    return ret;
151
}

LG-P4768 [NOI2018] 归程

考虑建出 MST，不过是最大生成树，然后倍增一下，完全类比上一题去做就行，需要 Dijkstra 跑一下最短路，然后挂到线段树上求区间最小值，亦可直接维护。


xxxxxxxxxx
171
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (210000)
24
#define INFLL (0x3f3f3f3f3f3f3f3fll)
25
#define CLEAR(arr) (memset(arr, 0, sizeof arr))
26

27
template < typename T = int >
28
inline T read(void);
29

30
int N, M;
31
int Q, K, S;
32
int ccnt;
33
int curp(1);
34
int ind[LIM << 1];
35
int val[LIM << 1];
36
int idx[LIM];
37
ll dis[LIM];
38
ll lst;
39
int mnp[LIM << 1], mxp[LIM << 1];
40
int jmp[LIM << 2][20]; //max - 19
41
bitset < LIM > vis;
42
struct edge{int s, t; int val;};
43
basic_string < edge > edgs;
44

45
struct Edge{
46
    Edge* nxt;
47
    int to;
48
    int val;
49
    OPNEW;
50
}ed[41000000];
51
ROPNEW;
52
Edge* head[LIM << 1];
53
Edge* ghead[LIM];
54

55
class UnionFind{
56
private:
57
    int fa[LIM << 1];
58
public:
59
    void Clear(void){for(int i = 1; i <= (LIM << 1) - 10; ++i)fa[i] = i;}
60
    UnionFind(void){Clear();}
61
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
62
    void Union(int s, int t){if(Find(s) != Find(t))fa[Find(s)] = Find(t);}
63
}uf;
64

65
class SegTree{
66
private:
67
    ll mn[LIM << 2];
68
    #define LS (p << 1)
69
    #define RS (LS | 1)
70
    #define MID ((gl + gr) >> 1)
71
public:
72
    void Clear(void){memset(mn, 0x3f, sizeof mn);}
73
    SegTree(void){memset(mn, 0x3f, sizeof mn);}
74
    void Pushup(int p){
75
        mn[p] = min(mn[LS], mn[RS]);
76
    }
77
    void Build(int p = 1, int gl = 1, int gr = N){
78
        if(gl == gr)return mn[p] = dis[idx[gl = gr]], void();
79
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
80
        Pushup(p);
81
    }
82
    ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
83
        if(l <= gl && gr <= r)return mn[p];
84
        if(l > gr || r < gl)return INFLL;
85
        return min(Query(l, r, LS, gl, MID), Query(l, r, RS, MID + 1, gr));
86
    }
87
}st;
88

89
int main(){
90
    // freopen("return.in", "r", stdin);
91
    // freopen("return.out", "w", stdout);
92
    // freopen("in.txt", "r", stdin);
93
    // freopen("out.txt", "w", stdout);
94
    auto Dijkstra = [](void)->void{
95
        memset(dis, 0x3f, sizeof dis); vis.reset();
96
        priority_queue < pair < ll, int >, vector < pair < ll, int > >, greater < pair < ll, int > > > cur;
97
        dis[1] = 0; cur.push({dis[1], 1});
98
        while(!cur.empty()){
99
            int p = cur.top().second; cur.pop();
100
            if(vis[p])continue;
101
            vis[p] = true;
102
            for(auto i = ghead[p]; i; i = i->nxt)
103
                if(dis[p] + i->val < dis[SON])
104
                    dis[SON] = dis[p] + i->val, cur.push({dis[SON], SON});
105
        }
106
    };
107
    auto dfs = [](auto&& self, int p, int fa = 0)->void{
108
        mnp[p] = curp, jmp[p][0] = fa;
109
        for(auto i = head[p]; i; i = i->nxt)
110
            self(self, SON, p);
111
        if(!head[p])idx[curp++] = p;
112
        mxp[p] = curp - 1;
113
    };
114
    int T = read();
115
    while(T--){
116
        curp = 1;
117
        st.Clear(), uf.Clear(); edgs.clear();
118
        CLEAR(ind), CLEAR(val), CLEAR(idx), lst = 0, CLEAR(mnp), CLEAR(mxp), CLEAR(jmp), CLEAR(head), CLEAR(ghead);
119
        ccnt = N = read(), M = read();
120
        for(int i = 1; i <= M; ++i){
121
            int s = read(), t = read(), dis = read(), val = read();
122
            edgs += edge{s, t, val};
123
            ghead[s] = new Edge{ghead[s], t, dis};
124
            ghead[t] = new Edge{ghead[t], s, dis};
125
        }Dijkstra();
126
        sort(edgs.begin(), edgs.end(), [](const edge &a, const edge &b)->bool{return a.val > b.val;});
127
        for(auto [s, t, v] : edgs){
128
            int fs = uf.Find(s), ft = uf.Find(t);
129
            if(fs != ft){
130
                int fap = ++ccnt;
131
                val[fap] = v;
132
                ++ind[fs], ++ind[ft];
133
                head[fap] = new Edge{head[fap], fs};
134
                head[fap] = new Edge{head[fap], ft};
135
                uf.Union(fs, fap), uf.Union(ft, fap);
136
            }
137
        }
138
        for(int i = 1; i <= ccnt; ++i)if(!ind[i]){dfs(dfs, i); break;}
139
        for(int i = 1; i <= 19; ++i)
140
            for(int j = 1; j <= ccnt; ++j)
141
                jmp[j][i] = jmp[jmp[j][i - 1]][i - 1];
142
        st.Build();
143
        Q = read(), K = read(), S = read();
144
        while(Q--){
145
            int p = (read() + K * lst - 1) % N + 1, h = (read() + K * lst) % (S + 1);
146
            for(int i = 19; i >= 0; --i)
147
                if(val[jmp[p][i]] > h)p = jmp[p][i];
148
            ll ans = st.Query(mnp[p], mxp[p]);
149
            lst = ans;
150
            printf("%lld\n", ans);
151
        }
152
    }
153
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
154
    return 0;
155
}
156

157
template < typename T >
158
inline T read(void){
159
    T ret(0);
160
    int flag(1);
161
    char c = getchar();
162
    while(c != '-' && !isdigit(c))c = getchar();
163
    if(c == '-')flag = -1, c = getchar();
164
    while(isdigit(c)){
165
        ret *= 10;
166
        ret += int(c - '0');
167
        c = getchar();
168
    }
169
    ret *= flag;
170
    return ret;
171
}

LG-P4899 [IOI2018] werewolf 狼人

好题，难度不大，实现直观。

考虑点权转边权，分别构建最小生成树和最大生成树的 Kruskal 生成树（最大生成树用点权最小值作为边权，反之亦然），老样子维护倍增找到最大可行区间，问题转化为对两个排列的两个区间求是否有交。

考虑维护每个元素在每个排列中的位置，问题转化为二位数点，第一维作为主席树下标，第二维作为权值跑一下即可。


xxxxxxxxxx
177
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define LIM (210000)
24
#define MID ((gl + gr) >> 1)
25
#define cnt(p) (p ? p->cnt : 0)
26

27
template < typename T = int >
28
inline T read(void);
29

30
int N, M, Q;
31
int ccnt;
32
struct Edge{
33
    Edge* nxt;
34
    int to;
35
    OPNEW;
36
}ed[LIM << 2];
37
ROPNEW;
38
Edge *headMx[LIM << 1], *headMn[LIM << 1];
39
int indMx[LIM << 1], indMn[LIM << 1];
40
int valMx[LIM << 1], valMn[LIM << 1];
41
int jmpMx[LIM << 2][20], jmpMn[LIM << 2][20]; //max - 19
42
int mnpMx[LIM << 1], mxpMx[LIM << 1], mnpMn[LIM << 1], mxpMn[LIM << 1];
43
int idxMn[LIM], idxMx[LIM], dfnMn[LIM], dfnMx[LIM];
44

45
class UnionFind{
46
private:
47
    int fa[LIM << 1];
48
public:
49
    void Clear(void){for(int i = 1; i <= (LIM << 1) - 10; ++i)fa[i] = i;}
50
    UnionFind(void){Clear();}
51
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
52
    void Union(int s, int t){if(Find(s) != Find(t))fa[Find(s)] = Find(t);}
53
}uf;
54

55
struct edge{int s, t; int val;};
56
basic_string < edge > MNST, MXST;
57

58
struct Node{
59
    Node *ls, *rs;
60
    int cnt;
61
    OPNEW;
62
}nd[LIM << 6];
63
ROPNEW_NODE;
64
Node* root[LIM];//rootMn[LIM], rootMx[LIM];
65

66
int main(){
67
    memset(valMn, 0x3f, sizeof valMn);
68
    N = read(), M = read(), Q = read();
69
    for(int i = 1; i <= N; ++i)mnpMx[i] = mxpMx[i] = mnpMn[i] = mxpMn[i] = i;
70
    for(int i = 1; i <= M; ++i){
71
        int s = read() + 1, t = read() + 1;
72
        MNST += edge{s, t, max(s, t)}, MXST += edge{s, t, min(s, t)};
73
    }sort(MNST.begin(), MNST.end(), [](const edge &a, const edge &b)->bool{return a.val < b.val;});
74
    sort(MXST.begin(), MXST.end(), [](const edge &a, const edge &b)->bool{return a.val > b.val;});
75
    ccnt = N;
76
    for(auto [s, t, v] : MNST){
77
        int fs = uf.Find(s), ft = uf.Find(t);
78
        if(fs != ft){
79
            int fap = ++ccnt;
80
            valMn[fap] = v;
81
            ++indMn[fs], ++indMn[ft];
82
            headMn[fap] = new Edge{headMn[fap], fs};
83
            headMn[fap] = new Edge{headMn[fap], ft};
84
            uf.Union(fs, fap), uf.Union(ft, fap);
85
            // printf("Link fa = %d, son = %d, %d\n", fap, fs, ft);
86
        }
87
    }ccnt = N, uf.Clear();
88
    for(auto [s, t, v] : MXST){
89
        int fs = uf.Find(s), ft = uf.Find(t);
90
        if(fs != ft){
91
            int fap = ++ccnt;
92
            valMx[fap] = v;
93
            ++indMx[fs], ++indMx[ft];
94
            headMx[fap] = new Edge{headMx[fap], fs};
95
            headMx[fap] = new Edge{headMx[fap], ft};
96
            uf.Union(fs, fap), uf.Union(ft, fap);
97
        }
98
    }
99
    auto dfs_mn = [](auto&& self, int p, int fa = 0)->void{
100
        // printf("p = %d fa = %d\n", p, fa);
101
        static int cur(1);
102
        mnpMn[p] = cur, jmpMn[p][0] = fa;
103
        for(auto i = headMn[p]; i; i = i->nxt)
104
            self(self, SON, p);
105
        if(!headMn[p])dfnMn[p] = cur, idxMn[cur++] = p;
106
        // printf("cur = %d\n", cur);
107
        mxpMn[p] = cur - 1;
108
    };
109
    auto dfs_mx = [](auto&& self, int p, int fa = 0)->void{
110
        static int cur(1);
111
        mnpMx[p] = cur, jmpMx[p][0] = fa;
112
        for(auto i = headMx[p]; i; i = i->nxt)
113
            self(self, SON, p);
114
        if(!headMx[p])dfnMx[p] = cur, idxMx[cur++] = p;
115
        mxpMx[p] = cur - 1;
116
    };
117
    for(int i = 1; i <= ccnt; ++i)if(!indMn[i]){dfs_mn(dfs_mn, i); break;}
118
    for(int i = 1; i <= ccnt; ++i)if(!indMx[i]){dfs_mx(dfs_mx, i); break;}
119
    for(int i = 1; i <= 19; ++i)
120
        for(int j = 1; j <= ccnt; ++j)
121
            jmpMn[j][i] = jmpMn[jmpMn[j][i - 1]][i - 1],
122
            jmpMx[j][i] = jmpMx[jmpMx[j][i - 1]][i - 1];
123
    auto Pushup = [](Node* p)->void{
124
        if(!p)return;
125
        p->cnt = cnt(p->ls) + cnt(p->rs);
126
    };
127
    auto Insert = [Pushup](auto&& self, int idx, int cnt, Node* lst, int gl = 1, int gr = N)->Node*{
128
        Node* p = lst ? new Node(*lst) : new Node{npt, npt, 0};
129
        if(gl == gr)return p->cnt += cnt, p;
130
        if(idx <= MID)p->ls = self(self, idx, cnt, p->ls, gl, MID);
131
        else p->rs = self(self, idx, cnt, p->rs, MID + 1, gr);
132
        return Pushup(p), p;
133
    };
134
    for(int i = 1; i <= N; ++i)root[i] = Insert(Insert, dfnMx[idxMn[i]], 1, root[i - 1]);
135
    auto QueryCnt = [](auto&& self, Node* px, Node* py, int l, int r, int gl = 1, int gr = N)->int{
136
        if(l <= gl && gr <= r)return cnt(py) - cnt(px);
137
        if(l > gr || r < gl)return 0;
138
        return self(self, px ? px->ls : npt, py ? py->ls : npt, l, r, gl, MID) + self(self, px ? px->rs : npt, py ? py->rs : npt, l, r, MID + 1, gr);
139
    };
140
    auto QueryExist = [QueryCnt](int l1, int r1, int l2, int r2)->bool{
141
        return QueryCnt(QueryCnt, root[l1 - 1], root[r1], l2, r2);
142
    };
143
    // for(int i = 1; i <= N; ++i)printf("%d ", idxMn[i]);
144
    // printf("\n");
145
    // for(int i = 1; i <= N; ++i)printf("%d ", idxMx[i]);
146
    // printf("\n");
147
    while(Q--){
148
        int S = read() + 1, T = read() + 1, L = read() + 1, R = read() + 1;
149
        for(int i = 19; i >= 0; --i){
150
            if(valMx[jmpMx[S][i]] >= L)S = jmpMx[S][i];
151
            if(valMn[jmpMn[T][i]] <= R)T = jmpMn[T][i];
152
        }
153
        // printf("After jumping S p = %d, val = %d\n", S, valMx[S]);
154
        // printf("After jumping T p = %d, val = %d\n", T, valMn[T]);
155
        // printf("faT p = %d, val = %d\n", jmpMn[T][0], valMn[jmpMn[T][0]]);
156
        // printf("Querying l1 = %d, r1 = %d, l2 = %d, r2 = %d\n", mnpMn[T], mxpMn[T], mnpMx[S], mxpMx[S]);
157
        printf("%d\n", QueryExist(mnpMn[T], mxpMn[T], mnpMx[S], mxpMx[S]) ? 1 : 0);
158
    }
159
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
160
    return 0;
161
}
162

163
template < typename T >
164
inline T read(void){
165
    T ret(0);
166
    int flag(1);
167
    char c = getchar();
168
    while(c != '-' && !isdigit(c))c = getchar();
169
    if(c == '-')flag = -1, c = getchar();
170
    while(isdigit(c)){
171
        ret *= 10;
172
        ret += int(c - '0');
173
        c = getchar();
174
    }
175
    ret *= flag;
176
    return ret;
177
}

LG-P1446 [HNOI2008] Cards

$dp(c, i, j, k)$ $c$ $i, j, k$ 个的方案数，按照背包思想滚动一维倒序转移即可。


x
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template < typename T = int >
24
inline T read(void);
25

26
int N, R, G, B, M, MOD;
27
int tot(0);
28
int len[110];
29
int nxt[110];
30
bitset < 110 > vis;
31
int dp[30][30][30];
32
int ans(0);
33

34
int main(){
35
    R = read(), B = read(), G = read(), M = read(), MOD = read();
36
    N = R + G + B;
37
    auto Make = [](void)->int{
38
        vis.reset(), tot = 0;
39
        memset(dp, 0, sizeof dp);
40
        dp[0][0][0] = 1;
41
        for(int s = 1; s <= N; ++s){
42
            if(vis[s])continue;
43
            vis[s] = true;
44
            int clen(1);
45
            int cur = nxt[s];
46
            while(cur != s)vis[cur] = true, cur = nxt[cur], ++clen;
47
            len[++tot] = clen;
48
        }
49
        for(int c = 1; c <= tot; ++c)
50
            for(int i = R; i >= 0; --i)
51
                for(int j = G; j >= 0; --j)
52
                    for(int k = B; k >= 0; --k){
53
                        if(i >= len[c])(dp[i][j][k] += dp[i - len[c]][j][k]) %= MOD;
54
                        if(j >= len[c])(dp[i][j][k] += dp[i][j - len[c]][k]) %= MOD;
55
                        if(k >= len[c])(dp[i][j][k] += dp[i][j][k - len[c]]) %= MOD;
56
                    }
57
        return dp[R][G][B];
58
    };
59
    for(int i = 1; i <= M; ++i){
60
        for(int j = 1; j <= N; ++j)nxt[j] = read();
61
        (ans += Make()) %= MOD;
62
    }
63
    for(int i = 1; i <= N; ++i)nxt[i] = i;
64
    (ans += Make()) %= MOD;
65
    auto qpow = [](ll a, ll b)->ll{
66
        ll ret(1), mul(a);
67
        while(b){
68
            if(b & 1)ret = ret * mul % MOD;
69
            b >>= 1;
70
            mul = mul * mul % MOD;
71
        }return ret;
72
    };
73
    printf("%lld\n", ans * qpow(M + 1, MOD - 2) % MOD);
74
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
75
    return 0;
76
}
77

78
template < typename T >
79
inline T read(void){
80
    T ret(0);
81
    int flag(1);
82
    char c = getchar();
83
    while(c != '-' && !isdigit(c))c = getchar();
84
    if(c == '-')flag = -1, c = getchar();
85
    while(isdigit(c)){
86
        ret *= 10;
87
        ret += int(c - '0');
88
        c = getchar();
89
    }
90
    ret *= flag;
91
    return ret;
92
}

UVA11255 Necklace


xxxxxxxxxx
1
1


xxxxxxxxxx
1
1


xxxxxxxxxx
1
1

UPD

update-2023__ 初稿