Contents

数据结构

线段树

一些资料：

一些题目：

主席树

一些资料：

一些题目：

kuangbin的主席树专题（假的，有题要用莫队）

树链剖分

一些资料：

qscqesze的讲解

一些题目：

bzoj1146

树堆

非常简洁dan，随便搜搜看看就可以了，一般都是旋转维护的（fhq版的就非常骚，不用旋转，而是合并/分割）

一份可供参考的代码：

/************************************************************************
* File Name : hdu5877.cpp
* Purpose : treap
* Creation Date : 2016年10月14日
* Last Modified : 2016年10月14日 星期五 23时06分30秒
* Created By : gou4shi1@qq.com
************************************************************************/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXN =  100000 + 100;

typedef int ARRAY[MAXN];
typedef long long LL;

ARRAY a;
bool isRoot[MAXN];
int n;
LL k, ans;

//edge
struct Edge {
    int to, next;
} edge[MAXN];

int edge_size;
ARRAY head;

inline void newEdge(int u, int v) {
    edge[++edge_size].to = v;
    edge[edge_size].next = head[u];
    head[u] = edge_size;
}

//treap
struct TreapNode {
    int val, size, pri, son[2];
} tree[MAXN];

int node_size, rt;

inline void newNode(int &x, int val) {
    x = ++node_size;
    tree[x].val = val;
    tree[x].size = 1;
    tree[x].pri = rand();
    tree[x].son[0] = tree[x].son[1] = 0;
}

inline void pushUp(int x) {
    tree[x].size = tree[tree[x].son[0]].size + 1 + tree[tree[x].son[1]].size;
}


inline void rotate(int &x, int p) {
    int y = tree[x].son[!p];
    tree[x].son[!p] = tree[y].son[p];
    pushUp(x);
    tree[y].son[p] = x;
    pushUp(y);
    x = y;
}

void ins(int &x, int val) {
    if (!x) {
        newNode(x, val);
        return;
    }

    int p = a[val] < a[tree[x].val];
    ins(tree[x].son[!p], val);
    pushUp(x);
    if (tree[x].pri < tree[tree[x].son[!p]].pri)
        rotate(x, p);
}

void del(int &x, int val) {
    if (tree[x].val == val) {
        if (tree[x].son[0] && tree[x].son[1]) {
            int p = tree[tree[x].son[0]].pri > tree[tree[x].son[1]].pri;
            rotate(x, p);
            del(tree[x].son[p], val);
            pushUp(x);
        } else {
            if (!tree[x].son[0])
                x = tree[x].son[1];
            else
                x = tree[x].son[0];
        }
    } else {
        int p = a[tree[x].val] > a[val];
        del(tree[x].son[!p], val);
        pushUp(x);
    }
}

int query(int x, int val) {
    if (!x)
        return 0;
    if ((LL)a[tree[x].val]*a[val] <= k)
        return tree[tree[x].son[0]].size + 1 + query(tree[x].son[1], val);
    else
        return query(tree[x].son[0], val);
}

//initialize
inline void init() {
    edge_size = 0;
    memset(head, 0, sizeof(head));
    memset(isRoot, true, sizeof(isRoot));

    node_size = 0;
    rt = 0;

    ans = 0;
}

void dfs(int x) {
    ans += query(rt, x);

    ins(rt, x);

    for (int i = head[x]; i; i = edge[i].next)
        dfs(edge[i].to);

    del(rt, x);
}

int main() {
    //freopen("in", "r", stdin);
    srand(time(NULL));
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        scanf("%d%lld", &n, &k);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n-1; ++i) {
            int u, v;
            scanf("%d%d", &u, &v);
            newEdge(u, v);
            isRoot[v] = false;
        }
        int root;
        for (int i = 1; i <= n; ++i)
            if (isRoot[i]) {
                root = i;
                break;
            }
        dfs(root);
        printf("%lld\n", ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

/************************************************************************

* File Name : hdu5877.cpp

* Purpose : treap

* Creation Date : 2016年10月14日

* Last Modified : 2016年10月14日星期五 23时06分30秒

* Created By : gou4shi1@qq.com

************************************************************************/

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cstdlib>

#include <ctime>

using namespace std;

const int MAXN = 100000 + 100;

typedef int ARRAY[MAXN];

typedef long long LL;

ARRAY a;

bool isRoot[MAXN];

int n;

LL k, ans;

//edge

struct Edge {

int to, next;

} edge[MAXN];

int edge_size;

ARRAY head;

inline void newEdge(int u, int v) {

edge[++edge_size].to = v;

edge[edge_size].next = head[u];

head[u] = edge_size;

}

//treap

struct TreapNode {

int val, size, pri, son[2];

} tree[MAXN];

int node_size, rt;

inline void newNode(int &x, int val) {

x = ++node_size;

tree[x].val = val;

tree[x].size = 1;

tree[x].pri = rand();

tree[x].son[0] = tree[x].son[1] = 0;

}

inline void pushUp(int x) {

tree[x].size = tree[tree[x].son[0]].size + 1 + tree[tree[x].son[1]].size;

}

inline void rotate(int &x, int p) {

int y = tree[x].son[!p];

tree[x].son[!p] = tree[y].son[p];

pushUp(x);

tree[y].son[p] = x;

pushUp(y);

x = y;

}

void ins(int &x, int val) {

if (!x) {

newNode(x, val);

return;

}

int p = a[val] < a[tree[x].val];

ins(tree[x].son[!p], val);

pushUp(x);

if (tree[x].pri < tree[tree[x].son[!p]].pri)

rotate(x, p);

}

void del(int &x, int val) {

if (tree[x].val == val) {

if (tree[x].son[0] && tree[x].son[1]) {

int p = tree[tree[x].son[0]].pri > tree[tree[x].son[1]].pri;

rotate(x, p);

del(tree[x].son[p], val);

pushUp(x);

} else {

if (!tree[x].son[0])

x = tree[x].son[1];

else

x = tree[x].son[0];

}

} else {

int p = a[tree[x].val] > a[val];

del(tree[x].son[!p], val);

pushUp(x);

}

int query(int x, int val) {

if (!x)

return 0;

if ((LL)a[tree[x].val]*a[val] <= k)

return tree[tree[x].son[0]].size + 1 + query(tree[x].son[1], val);

else

return query(tree[x].son[0], val);

}

//initialize

inline void init() {

edge_size = 0;

memset(head, 0, sizeof(head));

memset(isRoot, true, sizeof(isRoot));

node_size = 0;

rt = 0;

ans = 0;

}

void dfs(int x) {

ans += query(rt, x);

ins(rt, x);

for (int i = head[x]; i; i = edge[i].next)

dfs(edge[i].to);

del(rt, x);

}

int main() {

//freopen("in", "r", stdin);

srand(time(NULL));

int T;

scanf("%d", &T);

while (T--) {

init();

scanf("%d%lld", &n, &k);

for (int i = 1; i <= n; ++i)

scanf("%d", &a[i]);

for (int i = 1; i <= n-1; ++i) {

int u, v;

scanf("%d%d", &u, &v);

newEdge(u, v);

isRoot[v] = false;

}

int root;

for (int i = 1; i <= n; ++i)

if (isRoot[i]) {

root = i;

break;

}

dfs(root);

printf("%lld\n", ans);

}

return 0;

}

伸展树

一些资料：

一些题目：
我也没有怎么刷。。。GG。。。

动态树

直接上代码：

/************************************************************************
* File Name : hdu4010.cpp
* Purpose : link-cut-tree-template
* Creation Date : 2016年10月10日
* Last Modified : 2016年10月11日 星期二 17时59分48秒
* Created By : gou4shi1@qq.com
************************************************************************/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXN = 300010;

typedef int ARRAY[MAXN];

template<class T>
inline T max(T a, T b, T c) {return max(max(a, b), c);}

ARRAY val, head, fa, _max, add, rev;
int ch[MAXN][2];
bool rt[MAXN];

//edge
struct Edge {
    int to, next;
} edge[MAXN << 1];

int edge_size;

inline void addEdge(int u, int v) {
    edge[++edge_size].to = v;
    edge[edge_size].next = head[u];
    head[u] = edge_size;
}

//initialize
inline void init() {
    edge_size = 0;
    memset(head, 0, sizeof(head));
    fa[1] = 0;
    memset(add, 0, sizeof(add));
    memset(rev, 0, sizeof(rev));
    memset(rt, 1, sizeof(rt));
    for (int i = 0; i != MAXN; ++i)
        ch[i][0] = ch[i][1] = 0;
}

void dfs(int u) {
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        if (v == fa[u])
            continue;
        fa[v] = u;
        dfs(v);
    }
}

bool isSameRoot(int u, int v) {
    while (fa[u])
        u = fa[u];
    while (fa[v])
        v = fa[v];
    return u == v;
}

inline void updateAdd(int r, int d) {
    if (!r)
        return;
    val[r] += d;
    add[r] += d;
    _max[r] += d;
}

inline void updateRev(int r) {
    if (!r)
        return;
    swap(ch[r][0], ch[r][1]);
    rev[r] ^= 1;
}

void pushDown(int r) {
    if (add[r]) {
        updateAdd(ch[r][0], add[r]);
        updateAdd(ch[r][1], add[r]);
        add[r] = 0;
    }
    if (rev[r]) {
        updateRev(ch[r][0]);
        updateRev(ch[r][1]);
        rev[r] = 0;
    }
}

void pushDownFromRoot(int r) {
    if (!rt[r])
        pushDownFromRoot(fa[r]);
    pushDown(r);
}

inline void pushUp(int r) {
    _max[r] = max(val[r], _max[ch[r][0]], _max[ch[r][1]]);
}

inline void rotate(int x) {
    int y = fa[x];
    int kind = ch[y][1]==x;
    ch[y][kind] = ch[x][!kind];
    fa[ch[y][kind]] = y;
    fa[x] = fa[y];
    fa[y] = x;
    ch[x][!kind] = y;
    if (rt[y]) {
        rt[y] = false;
        rt[x] = true;
    } else
        ch[fa[x]][ ch[fa[x]][1]==y ] = x;
    pushUp(y);
}

void splay(int r) {
    pushDownFromRoot(r);
    while (!rt[r]) {
        int f = fa[r];
        int ff = fa[f];
        if (rt[f])
            rotate(r);
        else if ( (ch[ff][1]==f) == (ch[f][1]==r) ) {
            rotate(f);
            rotate(r);
        } else {
            rotate(r);
            rotate(r);
        }
    }
}

int access(int x) {
    int y = 0;
    for (; x; x = fa[y=x]) {
        splay(x);
        rt[ch[x][1]] = true;
        rt[y] = false;
        ch[x][1] = y;
        pushUp(x);
    }
    return y;
}

void makeRoot(int r) {
    access(r);
    splay(r);
    updateRev(r);
}

void link(int u, int v) {
    if (isSameRoot(u, v)) {
        printf("-1\n");
        return;
    }
    makeRoot(u);
    fa[u] = v;
}

void cut(int u, int v) {
    if (u == v || !isSameRoot(u, v)) {
        printf("-1\n");
        return;
    }
    makeRoot(u);
    splay(v);
    fa[ch[v][0]] = fa[v];
    rt[ch[v][0]] = true;
    fa[v] = 0;
    ch[v][0] = 0;
}

void lca(int &u, int &v) {
    access(v);
    v = 0;
    while (u) {
        splay(u);
        if (!fa[u])
            return;
        rt[ch[u][1]] = true;
        ch[u][1] = v;
        rt[ch[u][1]] = false;
        pushUp(u);
        v = u;
        u = fa[u];
    }
}

void modify_add(int u, int v, int w) {
    if (!isSameRoot(u, v)) {
        printf("-1\n");
        return;
    }
    lca(u, v);
    updateAdd(ch[u][1], w);
    updateAdd(v, w);
    val[u] += w;
    pushUp(u);
}

void query_max(int u, int v) {
    if (!isSameRoot(u, v)) {
        printf("-1\n");
        return;
    }
    lca(u, v);
    printf("%d\n", max(val[u], _max[v], _max[ch[u][1]]));
}

//main
int main() {
    //freopen("in", "r", stdin);
    int n;
    while (~scanf("%d", &n)) {
        init();
        int u, v;
        for (int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            addEdge(u, v);
            addEdge(v, u);
        }
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &val[i]);
            _max[i] = val[i];
        }
        int q;
        scanf("%d", &q);
        dfs(1);
        int op, x, y, w;
        while (q--) {
            scanf("%d", &op);
            switch (op) {
                case 1:
                    scanf("%d%d", &x, &y);
                    link(x, y);
                    break;
                case 2:
                    scanf("%d%d", &x, &y);
                    cut(x, y);
                    break;
                case 3:
                    scanf("%d%d%d", &w, &x, &y);
                    modify_add(x, y, w);
                    break;
                case 4:
                    scanf("%d%d", &x, &y);
                    query_max(x, y);
                    break;
                default:
                    printf("-1\n");
            }
        }
        printf("\n");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

/************************************************************************

* File Name : hdu4010.cpp

* Purpose : link-cut-tree-template

* Creation Date : 2016年10月10日

* Last Modified : 2016年10月11日星期二 17时59分48秒

* Created By : gou4shi1@qq.com

************************************************************************/

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <algorithm>

#include <map>

#include <vector>

#include <stack>

#include <queue>

#include <cstdlib>

#include <ctime>

using namespace std;

const int MAXN = 300010;

typedef int ARRAY[MAXN];

template<class T>

inline T max(T a, T b, T c) {return max(max(a, b), c);}

ARRAY val, head, fa, _max, add, rev;

int ch[MAXN][2];

bool rt[MAXN];

//edge

struct Edge {

int to, next;

} edge[MAXN << 1];

int edge_size;

inline void addEdge(int u, int v) {

edge[++edge_size].to = v;

edge[edge_size].next = head[u];

head[u] = edge_size;

}

//initialize

inline void init() {

edge_size = 0;

memset(head, 0, sizeof(head));

fa[1] = 0;

memset(add, 0, sizeof(add));

memset(rev, 0, sizeof(rev));

memset(rt, 1, sizeof(rt));

for (int i = 0; i != MAXN; ++i)

ch[i][0] = ch[i][1] = 0;

}

void dfs(int u) {

for (int i = head[u]; i; i = edge[i].next) {

int v = edge[i].to;

if (v == fa[u])

continue;

fa[v] = u;

dfs(v);

}

bool isSameRoot(int u, int v) {

while (fa[u])

u = fa[u];

while (fa[v])

v = fa[v];

return u == v;

}

inline void updateAdd(int r, int d) {

if (!r)

return;

val[r] += d;

add[r] += d;

_max[r] += d;

}

inline void updateRev(int r) {

if (!r)

return;

swap(ch[r][0], ch[r][1]);

rev[r] ^= 1;

}

void pushDown(int r) {

if (add[r]) {

updateAdd(ch[r][0], add[r]);

updateAdd(ch[r][1], add[r]);

add[r] = 0;

}

if (rev[r]) {

updateRev(ch[r][0]);

updateRev(ch[r][1]);

rev[r] = 0;

}

void pushDownFromRoot(int r) {

if (!rt[r])

pushDownFromRoot(fa[r]);

pushDown(r);

}

inline void pushUp(int r) {

_max[r] = max(val[r], _max[ch[r][0]], _max[ch[r][1]]);

}

inline void rotate(int x) {

int y = fa[x];

int kind = ch[y][1]==x;

ch[y][kind] = ch[x][!kind];

fa[ch[y][kind]] = y;

fa[x] = fa[y];

fa[y] = x;

ch[x][!kind] = y;

if (rt[y]) {

rt[y] = false;

rt[x] = true;

} else

ch[fa[x]][ ch[fa[x]][1]==y ] = x;

pushUp(y);

}

void splay(int r) {

pushDownFromRoot(r);

while (!rt[r]) {

int f = fa[r];

int ff = fa[f];

if (rt[f])

rotate(r);

else if ( (ch[ff][1]==f) == (ch[f][1]==r) ) {

rotate(f);

rotate(r);

} else {

rotate(r);

}

int access(int x) {

int y = 0;

for (; x; x = fa[y=x]) {

splay(x);

rt[ch[x][1]] = true;

rt[y] = false;

ch[x][1] = y;

pushUp(x);

}

return y;

}

void makeRoot(int r) {

access(r);

splay(r);

updateRev(r);

}

void link(int u, int v) {

if (isSameRoot(u, v)) {

printf("-1\n");

return;

}

makeRoot(u);

fa[u] = v;

}

void cut(int u, int v) {

if (u == v || !isSameRoot(u, v)) {

printf("-1\n");

return;

}

makeRoot(u);

splay(v);

fa[ch[v][0]] = fa[v];

rt[ch[v][0]] = true;

fa[v] = 0;

ch[v][0] = 0;

}

void lca(int &u, int &v) {

access(v);

v = 0;

while (u) {

splay(u);

if (!fa[u])

return;

rt[ch[u][1]] = true;

ch[u][1] = v;

rt[ch[u][1]] = false;

pushUp(u);

v = u;

u = fa[u];

}

void modify_add(int u, int v, int w) {

if (!isSameRoot(u, v)) {

printf("-1\n");

return;

}

lca(u, v);

updateAdd(ch[u][1], w);

updateAdd(v, w);

val[u] += w;

pushUp(u);

}

void query_max(int u, int v) {

if (!isSameRoot(u, v)) {

printf("-1\n");

return;

}

lca(u, v);

printf("%d\n", max(val[u], _max[v], _max[ch[u][1]]));

}

//main

int main() {

//freopen("in", "r", stdin);

int n;

while (~scanf("%d", &n)) {

init();

int u, v;

for (int i = 1; i < n; ++i) {

scanf("%d%d", &u, &v);

addEdge(u, v);

addEdge(v, u);

}

for (int i = 1; i <= n; ++i) {

scanf("%d", &val[i]);

_max[i] = val[i];

}

int q;

scanf("%d", &q);

dfs(1);

int op, x, y, w;

while (q--) {

scanf("%d", &op);

switch (op) {

case 1:

scanf("%d%d", &x, &y);

link(x, y);

break;

case 2:

scanf("%d%d", &x, &y);

cut(x, y);

break;

case 3:

scanf("%d%d%d", &w, &x, &y);

modify_add(x, y, w);

break;

case 4:

scanf("%d%d", &x, &y);

query_max(x, y);

break;

default:

printf("-1\n");

}

printf("\n");

}

return 0;

}

K-D树

一些资料：

一些题目：

hdu5992

/************************************************************************
* File Name : hdu5992.cpp
* Purpose : K-D Tree
* Creation Date : 2017年10月17日
* Last Modified : 2017年10月18日 星期三 02时54分13秒
* Created By : admin@goushi.me
************************************************************************/
#include <bits/stdc++.h>
using namespace std;

// const
const int N = 200000 + 10;
const int INF = 0x3f3f3f3f;
const int _INF = 0x80000000;
const int MOD = 1000000000 + 7;
const double EPS = 1E-8;

// long long
typedef long long LL;
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

// vector
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

// pair
typedef pair<int, int> PII;
#define mp make_pair
#define fi first
#define se second

#define mst(a,x) memset(a,x,sizeof(a))
#define sqr(x) ((x)*(x))

// K-D Tree
#define lr rt << 1
#define rr rt << 1 | 1
#define ls l, m-1, lr
#define rs m+1, r, rr

int now_dim;

struct Node {
    int p[2], c, id;

    void input() {
        scanf("%d%d%d", &p[0], &p[1], &c);
    }

    void output() {
        printf("%d %d %d\n", p[0], p[1], c);
    }
}a[N], tree[N*4];

bool operator < (const Node &a, const Node &b) {
    return a.p[now_dim] < b.p[now_dim];
}

inline LL dis(Node &a, Node &b) {
    return sqr((LL)a.p[0]-b.p[0]) + sqr((LL)a.p[1]-b.p[1]);
}

bool exist[N*4]; 

void build(int l, int r, int rt, int dep) {
    if (l > r)
        return;
    exist[rt] = true;

    int m = (l + r) >> 1;
    now_dim = dep % 2;
    nth_element(a+l, a+m, a+r+1);
    tree[rt] = a[m];
    build(ls, dep+1);
    build(rs, dep+1);
}

Node target, ans;
LL ans_dis;

void query(int rt, int dep) {
    if (!exist[rt])
        return;

    now_dim = dep % 2;
    int p = rr, q = lr;
    if (target < tree[rt])
        swap(p, q);
    query(p, dep+1);
    now_dim = dep % 2;

    LL rt_dis = dis(target, tree[rt]);
    bool flag(0);
    if (ans_dis == -1) {
        if (tree[rt].c <= target.c)
            ans = tree[rt], ans_dis = rt_dis;
        flag = true;
    } else  {
        if (tree[rt].c<=target.c && (rt_dis<ans_dis || (rt_dis==ans_dis && tree[rt].id < ans.id)))
            ans = tree[rt], ans_dis = rt_dis;
        if (sqr((LL)tree[rt].p[now_dim] - target.p[now_dim]) <= ans_dis)
            flag = true;
    }
    if (flag)
        query(q, dep+1);
}

void init() {
    mst(exist, 0);
}

int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif

    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            a[i].input();
            a[i].id = i;
        }
        build(1, n, 1, 0);

        while (m--) {
            target.input();
            ans_dis = -1;
            query(1, 0);
            ans.output();
        }
    }

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

/************************************************************************

* File Name : hdu5992.cpp

* Purpose : K-D Tree

* Creation Date : 2017年10月17日

* Last Modified : 2017年10月18日星期三 02时54分13秒

* Created By : admin@goushi.me

************************************************************************/

#include <bits/stdc++.h>

using namespace std;

// const

const int N = 200000 + 10;

const int INF = 0x3f3f3f3f;

const int _INF = 0x80000000;

const int MOD = 1000000000 + 7;

const double EPS = 1E-8;

// long long

typedef long long LL;

#ifdef _WIN32

#define LLD "%I64d"

#else

#define LLD "%lld"

#endif

// vector

typedef vector<int> VI;

#define pb push_back

#define all(x) (x).begin(), (x).end()

#define sz(x) ((int)(x).size())

// pair

typedef pair<int, int> PII;

#define mp make_pair

#define fi first

#define se second

#define mst(a,x) memset(a,x,sizeof(a))

#define sqr(x) ((x)*(x))

// K-D Tree

#define lr rt << 1

#define rr rt << 1 | 1

#define ls l, m-1, lr

#define rs m+1, r, rr

int now_dim;

struct Node {

int p[2], c, id;

void input() {

scanf("%d%d%d", &p[0], &p[1], &c);

}

void output() {

printf("%d %d %d\n", p[0], p[1], c);

}

}a[N], tree[N*4];

bool operator < (const Node &a, const Node &b) {

return a.p[now_dim] < b.p[now_dim];

}

inline LL dis(Node &a, Node &b) {

return sqr((LL)a.p[0]-b.p[0]) + sqr((LL)a.p[1]-b.p[1]);

}

bool exist[N*4];

void build(int l, int r, int rt, int dep) {

if (l > r)

return;

exist[rt] = true;

int m = (l + r) >> 1;

now_dim = dep % 2;

nth_element(a+l, a+m, a+r+1);

tree[rt] = a[m];

build(ls, dep+1);

build(rs, dep+1);

}

Node target, ans;

LL ans_dis;

void query(int rt, int dep) {

if (!exist[rt])

return;

now_dim = dep % 2;

int p = rr, q = lr;

if (target < tree[rt])

swap(p, q);

query(p, dep+1);

now_dim = dep % 2;

LL rt_dis = dis(target, tree[rt]);

bool flag(0);

if (ans_dis == -1) {

if (tree[rt].c <= target.c)

ans = tree[rt], ans_dis = rt_dis;

flag = true;

} else {

if (tree[rt].c<=target.c && (rt_dis<ans_dis || (rt_dis==ans_dis && tree[rt].id < ans.id)))

ans = tree[rt], ans_dis = rt_dis;

if (sqr((LL)tree[rt].p[now_dim] - target.p[now_dim]) <= ans_dis)

flag = true;

}

if (flag)

query(q, dep+1);

}

void init() {

mst(exist, 0);

}

int main() {

#ifdef LOCAL

freopen("in", "r", stdin);

#endif

int T;

scanf("%d", &T);

while (T--) {

init();

int n, m;

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; ++i) {

a[i].input();

a[i].id = i;

}

build(1, n, 1, 0);

while (m--) {

target.input();

ans_dis = -1;

query(1, 0);

ans.output();

}

return 0;

}

hdu4347

/************************************************************************
* File Name : hdu4347.cpp
* Purpose : K-D Tree
* Creation Date : 2017年10月19日
* Last Modified : 2017年10月19日 星期四 15时36分57秒
* Created By : admin@goushi.me
************************************************************************/
#include <bits/stdc++.h>
using namespace std;

// const
const int N = 50000 + 10;
const int K = 5;
const int INF = 0x3f3f3f3f;
const int _INF = 0x80000000;
const int MOD = 1000000000 + 7;
const double EPS = 1E-8;

// long long
typedef long long LL;
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif

// vector
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

// pair
typedef pair<int, int> PII;
#define mp make_pair
#define fi first
#define se second

#define mst(a,x) memset(a,x,sizeof(a))
#define sqr(x) ((x)*(x))

// K-D Tree
#define lr rt << 1
#define rr rt << 1 | 1
#define ls l, m-1, lr
#define rs m+1, r, rr

int DIM;
int now_dim;

struct Node {
    int p[K];

    void input() {
        for (int i = 0; i < DIM; ++i)
            scanf("%d", p+i);
    }

    void output() const {
        for (int i = 0; i < DIM-1; ++i)
            printf("%d ", p[i]);
        printf("%d\n", p[DIM-1]);
    }
}a[N], tree[N*4];

bool operator < (const Node &a, const Node &b) {
    return a.p[now_dim] < b.p[now_dim];
}

inline LL dis(Node &a, Node &b) {
    LL ret = 0;
    for (int k = 0; k < DIM; ++k)
        ret += sqr((LL)a.p[k]-b.p[k]);
    return ret;
}

bool exist[N*4]; 

void build(int l, int r, int rt, int dep) {
    if (l > r)
        return;
    exist[rt] = true;

    int m = (l + r) >> 1;
    now_dim = dep % DIM;
    nth_element(a+l, a+m, a+r+1);
    tree[rt] = a[m];
    build(ls, dep+1);
    build(rs, dep+1);
}

Node target;
typedef pair<LL, Node> PLN;
set<PLN> ans;
int m;

void query(int rt, int dep) {
    if (!exist[rt])
        return;

    now_dim = dep % DIM;
    int p = rr, q = lr;
    if (target < tree[rt])
        swap(p, q);
    query(p, dep+1);
    now_dim = dep % DIM;

    LL rt_dis = dis(target, tree[rt]);
    bool flag(0);
    if (ans.size() < m) {
        ans.insert(mp(rt_dis, tree[rt]));
        flag = true;
    } else  {
        auto it = ans.rbegin();
        if (rt_dis < (*it).fi) {
            ans.erase(*it);
            ans.insert(mp(rt_dis, tree[rt]));
        }
        it = ans.rbegin();
        if (sqr((LL)tree[rt].p[now_dim] - target.p[now_dim]) <= (*it).fi)
            flag = true;
    }
    if (flag)
        query(q, dep+1);
}

void init() {
    mst(exist, 0);
}


int main() {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif

    int n;
    while (scanf("%d%d", &n, &DIM) == 2) {
        init();

        for (int i = 1; i <= n; ++i)
            a[i].input();
        build(1, n, 1, 0);

        int q;
        scanf("%d", &q);
        while (q--) {
            target.input();
            scanf("%d", &m);
            ans.clear();
            query(1, 0);
            printf("the closest %d points are:\n", m);
            for (auto it = ans.begin(); it != ans.end(); ++it)
                (*it).se.output();
        }
    }

    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

/************************************************************************

* File Name : hdu4347.cpp

* Purpose : K-D Tree

* Creation Date : 2017年10月19日

* Last Modified : 2017年10月19日星期四 15时36分57秒

* Created By : admin@goushi.me

************************************************************************/

#include <bits/stdc++.h>

using namespace std;

// const

const int N = 50000 + 10;

const int K = 5;

const int INF = 0x3f3f3f3f;

const int _INF = 0x80000000;

const int MOD = 1000000000 + 7;

const double EPS = 1E-8;

// long long

typedef long long LL;

#ifdef _WIN32

#define LLD "%I64d"

#else

#define LLD "%lld"

#endif

// vector

typedef vector<int> VI;

#define pb push_back

#define all(x) (x).begin(), (x).end()

#define sz(x) ((int)(x).size())

// pair

typedef pair<int, int> PII;

#define mp make_pair

#define fi first

#define se second

#define mst(a,x) memset(a,x,sizeof(a))

#define sqr(x) ((x)*(x))

// K-D Tree

#define lr rt << 1

#define rr rt << 1 | 1

#define ls l, m-1, lr

#define rs m+1, r, rr

int DIM;

int now_dim;

struct Node {

int p[K];

void input() {

for (int i = 0; i < DIM; ++i)

scanf("%d", p+i);

}

void output() const {

for (int i = 0; i < DIM-1; ++i)

printf("%d ", p[i]);

printf("%d\n", p[DIM-1]);

}

}a[N], tree[N*4];

bool operator < (const Node &a, const Node &b) {

return a.p[now_dim] < b.p[now_dim];

}

inline LL dis(Node &a, Node &b) {

LL ret = 0;

for (int k = 0; k < DIM; ++k)

ret += sqr((LL)a.p[k]-b.p[k]);

return ret;

}

bool exist[N*4];

void build(int l, int r, int rt, int dep) {

if (l > r)

return;

exist[rt] = true;

int m = (l + r) >> 1;

now_dim = dep % DIM;

nth_element(a+l, a+m, a+r+1);

tree[rt] = a[m];

build(ls, dep+1);

build(rs, dep+1);

}

Node target;

typedef pair<LL, Node> PLN;

set<PLN> ans;

int m;

void query(int rt, int dep) {

if (!exist[rt])

return;

now_dim = dep % DIM;

int p = rr, q = lr;

if (target < tree[rt])

swap(p, q);

query(p, dep+1);

now_dim = dep % DIM;

LL rt_dis = dis(target, tree[rt]);

bool flag(0);

if (ans.size() < m) {

ans.insert(mp(rt_dis, tree[rt]));

flag = true;

} else {

auto it = ans.rbegin();

if (rt_dis < (*it).fi) {

ans.erase(*it);

ans.insert(mp(rt_dis, tree[rt]));

}

it = ans.rbegin();

if (sqr((LL)tree[rt].p[now_dim] - target.p[now_dim]) <= (*it).fi)

flag = true;

}

if (flag)

query(q, dep+1);

}

void init() {

mst(exist, 0);

}

int main() {

#ifdef LOCAL

freopen("in", "r", stdin);

#endif

int n;

while (scanf("%d%d", &n, &DIM) == 2) {

init();

for (int i = 1; i <= n; ++i)

a[i].input();

build(1, n, 1, 0);

int q;

scanf("%d", &q);

while (q--) {

target.input();

scanf("%d", &m);

ans.clear();

query(1, 0);

printf("the closest %d points are:\n", m);

for (auto it = ans.begin(); it != ans.end(); ++it)

(*it).se.output();

}

return 0;

}

数论

一些资料：

一些题目：

环境

平时用

Terminal Shell Vim 三剑客

Vim教程

（强推里面的 ACMer 必备套餐）

比赛用

set nocp hi=666 wmnu nu ru ls=2 so=5 mouse=a ar ai si et ts=4 sts=4 sw=4 tm=5000 ttm=100 nowrap backspace=eol,start,indent hls is ignorecase scs magic cindent
set makeprg=g++\ -g\ -std=gnu++0x\ -o\ %<\ %
nmap<F2> :vs %<.in <CR>
nmap<F6> :!rm -rf %<<CR>:w<CR>:make<CR>:!./%< < %<.in<CR>
nmap<F8> :w<CR>:make<CR>:cw<CR>
color evening

set nocp hi=666 wmnu nu ru ls=2 so=5 mouse=a ar ai si et ts=4 sts=4 sw=4 tm=5000 ttm=100 nowrap backspace=eol,start,indent hls is ignorecase scs magic cindent

set makeprg=g++\ -g\ -std=gnu++0x\ -o\ %<\ %

nmap<F2> :vs %<.in <CR>

nmap<F6> :!rm -rf %<<CR>:w<CR>:make<CR>:!./%< < %<.in<CR>

nmap<F8> :w<CR>:make<CR>:cw<CR>

color evening

其他

header

#include <bits/stdc++.h>
using namespace std;

// const
const int N = 1E5 + 10;
const int INF = 0x3f3f3f3f;
const int _INF = 0x80000000;
const int MOD = 1E9 + 7;
const double EPS = 1E-8;

// long long
typedef long long LL;
#ifdef _WIN32
#define lld I64d
#endif

// vector
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

// pair
typedef pair<int, int> PII;
#define mp make_pair
#define fi first
#define se second

#define mst(a,x) memset(a,x,sizeof(a))

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {

    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

// const

const int N = 1E5 + 10;

const int INF = 0x3f3f3f3f;

const int _INF = 0x80000000;

const int MOD = 1E9 + 7;

const double EPS = 1E-8;

// long long

typedef long long LL;

#ifdef _WIN32

#define lld I64d

#endif

// vector

typedef vector<int> VI;

#define pb push_back

#define all(x) (x).begin(), (x).end()

#define sz(x) ((int)(x).size())

// pair

typedef pair<int, int> PII;

#define mp make_pair

#define fi first

#define se second

#define mst(a,x) memset(a,x,sizeof(a))

int main() {

int T;

scanf("%d", &T);

while (T--) {

}

return 0;

}

别人的合集

（比我的好多了QAQ

诟屍

ACM之杂七杂八

数据结构

线段树

主席树

树链剖分

树堆

伸展树

动态树

K-D树

数论

环境

平时用

比赛用

其他

header

别人的合集

Related

Leave a Reply Cancel reply

April 2024
S	M	T	W	T	F	S
« Jun
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30