杂题小记（2023.03.07）

更好的阅读体验戳此进入

LG-P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

标准线段树合并板子，注意每次修改存在四次 Modify 对于 Node 的数组需要开更大一些。

xxxxxxxxxx
149
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

25
template < typename T = int >
26
inline T read(void);
27

28
struct Node{
29
    #define val(p) (p ? p->val : 0)
30
    #define cnt(p) (p ? p->cnt : 0)
31
    Node* ls, *rs;
32
    int val, cnt;
33
    OPNEW;
34
}nd[LIM << 6];
35
ROPNEW_NODE;
36

37
void Pushup(Node* p){
38
    if(!p)return;
39
    if(cnt(p->ls) >= cnt(p->rs))p->val = val(p->ls), p->cnt = cnt(p->ls);
40
    else p->val = val(p->rs), p->cnt = cnt(p->rs);
41
}
42

43
class SegTree{
44
private:
45
    #define LS (p << 1)
46
    #define RS (LS | 1)
47
    #define MID ((gl + gr) >> 1)
48
public:
49
    Node* root;
50
    void Modify(int idx, int v, Node* &p, int gl = 1, int gr = LIM){
51
        if(!p)p = new Node{npt, npt, 0, 0};
52
        if(gl == gr)return p->cnt += v, p->val = p->cnt ? gl = gr : 0, void();
53
        if(idx <= MID)Modify(idx, v, p->ls, gl, MID);
54
        else Modify(idx, v, p->rs, MID + 1, gr);
55
        Pushup(p);
56
    }
57
    int Query(void){
58
        return val(root);
59
    }
60
}st[LIM];
61

62
Node* Merge(Node* A, Node* B, int gl = 1, int gr = LIM){
63
    if(!A || !B)return A ? A : B;
64
    if(gl == gr)return A->cnt += B->cnt, A->val = A->cnt ? gl = gr : 0, A;
65
    if(!A->ls && B->ls)A->ls = B->ls;
66
    else A->ls = Merge(A->ls, B->ls, gl, MID);
67
    if(!A->rs && B->rs)A->rs = B->rs;
68
    else A->rs = Merge(A->rs, B->rs, MID + 1, gr);
69
    return Pushup(A), A;
70
}
71

72
int N, M;
73

74
struct Edge{
75
    Edge* nxt;
76
    int to;
77
    OPNEW;
78
}ed[LIM << 1];
79
ROPNEW;
80
Edge* head[LIM];
81

82
int dep[LIM], dfn[LIM], idx[LIM], top[LIM], hson[LIM], siz[LIM], fa[LIM];
83

84
void dfs_pre(int p = 1, int fa = 0){
85
    ::fa[p] = fa, dep[p] = dep[fa] + 1, siz[p] = 1;
86
    for(auto i = head[p]; i; i = i->nxt){
87
        if(SON == fa)continue;
88
        dfs_pre(SON, p);
89
        siz[p] += siz[SON];
90
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
91
    }
92
}
93
void dfs_make(int p = 1, int top = 1){
94
    static int cdfn(0);
95
    dfn[p] = ++cdfn, idx[cdfn] = p;
96
    ::top[p] = top;
97
    if(hson[p])dfs_make(hson[p], top);
98
    for(auto i = head[p]; i; i = i->nxt)
99
        if(SON != fa[p] && SON != hson[p])dfs_make(SON, SON);
100
}
101
int LCA(int s, int t){
102
    while(top[s] != top[t]){
103
        if(dep[top[s]] < dep[top[t]])swap(s, t);
104
        s = fa[top[s]];
105
    }if(dep[s] < dep[t])swap(s, t);
106
    return t;
107
}
108

109
int ans[LIM];
110

111
void dfs_merge(int p = 1, int fa = 0){
112
    for(auto i = head[p]; i; i = i->nxt)
113
        if(SON != fa)dfs_merge(SON, p), st[p].root = Merge(st[p].root, st[SON].root);
114
    ans[p] = st[p].Query();
115
}
116

117
int main(){
118
    N = read(), M = read();
119
    for(int i = 1; i <= N - 1; ++i){
120
        int s = read(), t = read();
121
        head[s] = new Edge{head[s], t};
122
        head[t] = new Edge{head[t], s};
123
    }dfs_pre(), dfs_make();
124
    for(int i = 1; i <= M; ++i){
125
        int s = read(), t = read(), v = read(), lca = LCA(s, t);
126
        // printf("s = %d, t = %d, lca = %d\n", s, t, lca);
127
        st[s].Modify(v, 1, st[s].root), st[t].Modify(v, 1, st[t].root);
128
        st[lca].Modify(v, -1, st[lca].root), st[fa[lca]].Modify(v, -1, st[fa[lca]].root);
129
    }dfs_merge();
130
    for(int i = 1; i <= N; ++i)printf("%d\n", ans[i]);
131
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
132
    return 0;
133
}
134

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

LG-P5494 【模板】线段树分裂

线段树分裂模板，注意对于查询 rank 时需要考虑到 gl = gr 的点中可能有多个相同权值的点。

xxxxxxxxxx
137
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

25
template < typename T = int >
26
inline T read(void);
27

28
struct Node{
29
    Node *ls, *rs;
30
    ll cnt;
31
    OPNEW;
32
}nd[LIM << 5];
33
ROPNEW_NODE;
34
Node* root[LIM];
35

36
#define LS (p << 1)
37
#define RS (LS | 1)
38
#define MID ((gl + gr) >> 1)
39
#define cnt(p) (p ? p->cnt : 0)
40

41
void Pushup(Node* p){
42
    if(!p)return;
43
    p->cnt = cnt(p->ls) + cnt(p->rs);
44
}
45
void Modify(int idx, int val, Node* &p, int gl = 1, int gr = LIM){
46
    if(!p)p = new Node{npt, npt, 0};
47
    if(gl == gr)return p->cnt += val, void();
48
    if(idx <= MID)Modify(idx, val, p->ls, gl, MID);
49
    else Modify(idx, val, p->rs, MID + 1, gr);
50
    Pushup(p);
51
}
52
ll QueryCnt(int l, int r, Node* p, int gl = 1, int gr = LIM){
53
    if(!p || gr < l || gl > r)return 0;
54
    if(l <= gl && gr <= r)return p->cnt;
55
    return QueryCnt(l, r, p->ls, gl, MID) + QueryCnt(l, r, p->rs, MID + 1, gr);
56
}
57
ll QueryByRnk(ll rnk, Node* p, int gl = 1, int gr = LIM){
58
    // printf("Querying rnk = %lld, gl = %d, gr = %d, cnt = %lld\n", rnk, gl, gr, cnt(p));
59
    if(!p)return -1;
60
    if(gl == gr)return rnk <= cnt(p) ? gl = gr : -1;
61
    if(rnk <= cnt(p->ls))return QueryByRnk(rnk, p->ls, gl, MID);
62
    else return QueryByRnk(rnk - cnt(p->ls), p->rs, MID + 1, gr);
63
}
64
Node* Merge(Node* A, Node* B, int gl = 1, int gr = LIM){
65
    if(!A || !B)return A ? A : B;
66
    if(gl == gr)return A->cnt += B->cnt, A;
67
    if(!A->ls && B->ls)A->ls = B->ls;
68
    else A->ls = Merge(A->ls, B->ls, gl, MID);
69
    if(!A->rs && B->rs)A->rs = B->rs;
70
    else A->rs = Merge(A->rs, B->rs, MID + 1, gr);
71
    return Pushup(A), A;
72
}
73
Node* Split(Node* &S, int val, int gl = 1, int gr = LIM){
74
    if(!S)return npt;
75
    Node* np = new Node{npt, npt, 0};
76
    if(val <= MID)return np->rs = S->rs, S->rs = npt, np->ls = Split(S->ls, val, gl, MID), Pushup(S), Pushup(np), np;
77
    else if(val == MID + 1)return np->rs = S->rs, S->rs = npt, Pushup(S), Pushup(np), np;
78
    else return np->rs = Split(S->rs, val, MID + 1, gr), Pushup(S), Pushup(np), np;
79
}
80

81
int N, M;
82
int cur(1);
83

84
int main(){
85
    N = read(), M = read();
86
    for(int i = 1; i <= N; ++i)Modify(i, read(), root[cur]);
87
    while(M--){
88
        int opt = read();
89
        switch(opt){
90
            case 0:{
91
                int idx = read(), l = read(), r = read();
92
                Node *L = Split(root[idx], l), *R = Split(L, r + 1);
93
                root[++cur] = L, root[idx] = Merge(root[idx], R);
94
                // printf("origin : %lld, split : %lld\n", QueryCnt(1, LIM, root[idx]), QueryCnt(1, LIM, root[cur]));
95
                break;
96
            }
97
            case 1:{
98
                int t = read(), s = read();
99
                root[t] = Merge(root[t], root[s]);
100
                break;
101
            }
102
            case 2:{
103
                int idx = read(), cnt = read(), val = read();
104
                Modify(val, cnt, root[idx]);
105
                break;
106
            }
107
            case 3:{
108
                int idx = read(), l = read(), r = read();
109
                printf("%lld\n", QueryCnt(l, r, root[idx]));
110
                break;
111
            }
112
            case 4:{
113
                int idx = read(); ll rnk = read < ll >();
114
                printf("%lld\n", QueryByRnk(rnk, root[idx]));
115
                break;
116
            }
117
        }
118
    }
119
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
120
    return 0;
121
}
122

123
template < typename T >
124
inline T read(void){
125
    T ret(0);
126
    int flag(1);
127
    char c = getchar();
128
    while(c != '-' && !isdigit(c))c = getchar();
129
    if(c == '-')flag = -1, c = getchar();
130
    while(isdigit(c)){
131
        ret *= 10;
132
        ret += int(c - '0');
133
        c = getchar();
134
    }
135
    ret *= flag;
136
    return ret;
137
}

LG-P4005 小 Y 和地铁

LOJ #2323. 「清华集训 2017」小 Y 和地铁

找一下性质，发现对于只有一个交点的站点一定无贡献，对于有且仅有两个交点的考虑发现其有效状态只有四种（即发现对于从线段的左端点与右端点绕过是等效的），于是考虑随机一个初始状态后 $O(n^2)$$O(n^2)$ 判断任意两条线段是否有交，可以发现这是正确的。然后感性理解发现答案满足类似多峰函数的性质，考虑模拟退火，每次随机一个位置并随机一个新的权值 $O(n)$$O(n)$ 更新即可，对于大多数参数都可以保证 $90+\mathtt{\text{pts}}$$90+\texttt{pts}$，参数较为优秀时可以 AC。

xxxxxxxxxx
142
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 line(i) (lines.at(i - 1))
24

25
template < typename T = int >
26
inline T read(void);
27

28
int N;
29
int pos[50];
30
int status[50];
31
bool itsc[50][50];
32
int cur(0);
33
int ans(INT_MAX);
34
struct Line{int l, r;};
35
basic_string < Line > lines;
36

37
int main(){
38
    auto notIntersect = [](int a, int b)->bool{
39
        if(line(a).l > line(b).l)swap(a, b);
40
        switch(status[a]){
41
            case 1:{
42
                switch(status[b]){
43
                    case 1: return line(a).r < line(b).l || line(b).r < line(a).r;
44
                    case 2: return true;
45
                    case 3: return line(b).l > line(a).r;
46
                    case 4: return line(b).r > line(a).r;
47
                }break;
48
            }
49
            case 2:{
50
                switch(status[b]){
51
                    case 1: return true;
52
                    case 2: return line(a).r < line(b).l || line(b).r < line(a).r;
53
                    case 3: return line(b).r > line(a).r;
54
                    case 4: return line(b).l > line(a).r;
55
                }break;
56
            }
57
            case 3:{
58
                switch(status[b]){
59
                    case 1: return true;
60
                    case 2: return line(b).r < line(a).r || line(b).l > line(a).r;
61
                    case 3: return line(b).r > line(a).r;
62
                    case 4: return line(b).l > line(a).r;
63
                }break;
64
            }
65
            case 4:{
66
                switch(status[b]){
67
                    case 1: return line(b).r < line(a).r || line(b).l > line(a).r;
68
                    case 2: return true;
69
                    case 3: return line(b).l > line(a).r;
70
                    case 4: return line(b).r > line(a).r;
71
                }break;
72
            }
73
        }return false;
74
    };
75
    auto Intersect = [notIntersect](int i, int j)->bool{return !notIntersect(i, j);};//判断写反了，懒的改就写了个 notIntersect 转一下。。。。。。
76
    auto SetOrigin = [Intersect](void)->void{
77
        cur = 0;
78
        for(int i = 1; i <= N; ++i)for(int j = i + 1; j <= N; ++j)cur += (itsc[i][j] = itsc[j][i] = Intersect(i, j));//, printf("checking i = %d, j = %d, res = %d\n", i, j, itsc[i][j] ? 1 : 0);
79
        ans = min(ans, cur);
80
    };
81
    auto Anneal = [Intersect](void)->void{
82
        double T = 50.0, delta = 0.993;
83
        while(T > 1e-2){
84
            int idx = rndd(1, N);
85
            int val = rndd(1, 4);
86
            while(val == status[idx])val = rndd(1, 4);
87
            int nxt = cur;
88
            int lsts = status[idx]; status[idx] = val;
89
            for(int i = 1; i <= N; ++i)if(i != idx){
90
                if(itsc[idx][i] && !Intersect(idx, i))--nxt;
91
                else if(!itsc[idx][i] && Intersect(idx, i))++nxt;
92
            }
93
            if(nxt < cur || exp(-(double)(nxt - cur) / T) > (double)rndd(1, 114514) / 114514){
94
                cur = nxt;
95
                ans = min(ans, cur);
96
                for(int i = 1; i <= N; ++i)if(i != idx)itsc[idx][i] = itsc[i][idx] = Intersect(idx, i);
97
            }else status[idx] = lsts;
98
            T *= delta;
99
        }
100
    };
101
    int T = read();
102
    while(T--){
103
        memset(pos, 0, sizeof pos);
104
        memset(status, 0, sizeof status);
105
        lines.clear();
106
        ans = INT_MAX;
107
        N = read();
108
        for(int i = 1; i <= N; ++i){
109
            int val = read();
110
            if(pos[val])lines += Line{min(pos[val], i), max(pos[val], i)};
111
            else pos[val] = i;
112
        }N = lines.size();
113
        if(!N){printf("0\n"); continue;}
114
        int t = 30;
115
        while(t--){
116
            memset(itsc, 0, sizeof itsc);
117
            for(int i = 1; i <= N; ++i)status[i] = rndd(1, 4);
118
            // for(int i = 1; i <= N; ++i)printf("%d ", status[i]);
119
            // printf("\n");
120
            SetOrigin();
121
            Anneal();
122
        }printf("%d\n", ans);
123
    }
124
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
125
    return 0;
126
}
127

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

UPD

update-2023_03_07 初稿