3.1 题目描述
南极的企鹅王国大学中生活着 n 只企鹅,作为 21 世纪的优秀大学生,企鹅们积极响应“大众创业,万众创新”的号召,纷纷创业。但是创业需要资金,企鹅们最近手头比较紧,只能互相借钱。
企鹅的借钱行为是有规律可循的:每只企鹅只会借一次钱,并且只会从一只企鹅那里借钱。借钱关系中不存在环(即不存在类似“金企鹅欠银企鹅钱,银企鹅欠铜企鹅钱,铜企鹅欠金企鹅钱”这种情况)。
企鹅的还钱行为也是有规律可循的:每只企鹅一旦新获得了一笔钱,就会立刻用这笔钱尽可能偿还自己欠的债务,直到债务偿清或用光这笔钱。它只会使用新获得的这笔钱,至于以前它有没有钱、有多少钱,与还钱行为无关。
企鹅们经常会做美梦。在一只企鹅 A 的梦里,它梦见自己创业成功,一下子获得了 +∞ 元钱,于是(按照上文的还钱规则)它赶快把钱用来还债,接着拿到钱的那只企鹅也赶快把钱用来还债......如此往复,直到所有获得钱的企鹅都完成了还债操作。梦醒之后,它开心地把梦的内容告诉了另外一只企鹅 B,企鹅 B 听了,也很开心,于是它问道:在你的梦里,我获得了多少钱呢?(指 B 去还债之前手里的钱,包括后来用于还债的钱和还债后B 手里剩下的钱。)
梦毕竟是梦,对实际的欠债情况没有影响。
3.2格式
3.2.1输入格式
第一行两个整数 n 和 m,表示有 n 只企鹅,m 个操作。
接下来 m 行,有两种可能的格式:
- 0 a b c:修改操作,企鹅 a 向企鹅 b 借了 c 元钱。
- 1 a b:查询操作,询问假如 a 有了 +∞ 元钱,企鹅 b 会净收入多少钱。
本题强制在线,也就是说:对于每个操作输入的变量 a, b, c(如果没有c,那就只有 a, b)都不是实际的 a, b, c,想获得实际的 a, b, c 应当经过以下操作:
a = (a + lastans) % n + 1;
b = (b + lastans) % n + 1;
c = (c + lastans) % n + 1;
其中,lastans 是上一次询问的答案。如果没有上一次询问,lastans 为0。
3.2.2输出格式
对每个询问操作,输出一行一个数表示答案。
3.3样例
3.3.1样例输入
5 9
0 1 2 1
0 0 1 2
1 0 1
1 2 4
0 2 1 1
1 2 0
0 3 1 0
1 4 2
1 3 4
3.3.2样例输出
3
2
0
1
0
3.4 数据范围
数据分为以下几种:
第一种:占 10%,n ≤ 5000 且 m ≤ 10000;
第二种:占 20%,所有借钱事件(0 开头的操作)发生在所有询问事件(1 开头的操作)之前;
第三种:占 30%,对于一只企鹅 A,最多只有一只企鹅向 A 借钱;
第四种:占 40%,没有特殊性质,n、m 大小有一定梯度。
对于所有数据,满足:n ≤ 10 5 ,m ≤ 10 6 ,0 ≤ a, b, c ≤ n 且 a != b。
正解:求动态树上某链中最小值LCT!
LCT板子题
然而可以乱搞搞过去
出题的兔哥还找了某毒瘤出题人王逸松验了题
兔哥的做法:
将有向有根树改成无向无根树存下来,树上倍增+启发式合并,每次合并时暴力重构倍增数组,倍增数组多存一个到(2^j)的父节点的方向,全向上为1,全向下为2,两个都有为3,询问时判断两个点的方向关系就过了..
O(松)的做法:
题目大意
n 个结点，m 个操作，一开始啥也没有。
每次操作可以加一条有向边，保证任何时候图的每个连通块都是一棵有向树。
每次操作也可以询问两个结点 a 到 b 的路径上的最小边权，注意需要判断 a 是否能走到 b。
算法描述
如果事先知道整棵树的形态，我们可以用【倍增】来进行预处理和询问，时间复杂度 O((n + m) log n)，空间复杂度 O(n log n)。
注意：在倍增算法中，可以不记录每个结点的深度，只记录倍增数组（fa[N][17], val[N][17]），并通过倍增来查询结点的深度。（见 getdep 函数）
在本题中，我们可以实时维护【每个连通块的倍增数组】，那么询问可以用朴素的倍增算法实现。而在新增一条边的同时，需要【不重复不遗漏】地更新这些倍增数组。由于倍增数组中一共有 O(n log n) 个元素，如果能恰好只枚举需要更新的元素，那么更新的总时间复杂度也是 O(n log n) 的。
我们考虑每次加边操作。“新增一条 a 到 b 的有向边”，本质上是将 a 作为 b 的儿子，b 作为 a 的爸爸。我们再考虑倍增数组的本质，就是树上所有【长度为 2^k 的 祖先—儿子 链】。新增一条边时，需要更新的元素，就是树上新增的这样的链，也就是跨过 a 和 b 之间的边的这些链。
我们注意到，新增的这些链，在 b 所在连通块的端点必然是 b 的某个祖先，而在 a 所在连通块的端点，在确定另一个端点后【只和深度有关】。也就是，如果把 a 所在连通块所有结点按到 b 的距离（深度+1）排在数轴的负半轴，b 的所有祖先按照到 b 的距离排在数轴的正半轴，那么新增的这些链，就是跨过数轴原点的那些【长度为 2^k 的整端点线段】。
为了枚举这些线段，我们从正半轴和负半轴中选择长度较短的一侧，枚举每个位置（即距离），然后枚举线段的长度（2^k），满足线段的另一端点落在数轴的另一侧。注意枚举的一些小技巧（见代码）就可以恰好只枚举需要枚举的线段，且满足倍增数组建立的顺序（DP 的拓扑序）。
为了实现这个算法，我们还需要维护【每个连通块的每个深度的结点集合】，并在每次加边操作之后，都要合并对应的两个连通块。具体做法是，每个连通块用一个【双端 vector】记录【每个深度的结点集合】，而集合使用【单向链表】来维护。这样就可以方便地实现集合的合并，以及【基于启发式合并的】连通块的合并（见代码）。
在合并的过程中，枚举链的总复杂度是 O(n log n) 的，而合并连通块的复杂度，不会超过一般情况下的启发式合并（即，直接对连通块中每个结点进行启发式合并）的复杂度，即 O(n log n)。询问的总时间复杂度是 O(m log n)，空间复杂度是 O(n log n)。
兔哥代码
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cassert>
#define space putchar(' ')
#define enter putchar('
')
typedef long long ll;
using namespace std;
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 100005, INF = 0x3f3f3f3f;
int n, m, lastans;
int ecnt, nxt[2*N], go[2*N], adj[N], edir[2*N], emi[2*N];
int sze[N], bel[N], dep[N];
int anc[N][20], mi[N][20], dir[N][20];
void out(){
for(int i = 1; i <= n; i++)
for(int j = 0; anc[i][j]; j++)
printf("anc[%d][%d] = %d, dir = %d, mi = %d
", i, j, anc[i][j], dir[i][j], mi[i][j]);
}
void adde(int u, int v, int d, int w){
go[++ecnt] = v;
nxt[ecnt] = adj[u];
adj[u] = ecnt;
edir[ecnt] = d;
emi[ecnt] = w;
}
void dfs(int u, int pre, int rt){
bel[u] = rt;
dep[u] = dep[pre] + 1;
for(int i = 0; i < 19; i++){
anc[u][i + 1] = anc[anc[u][i]][i];
mi[u][i + 1] = min(mi[u][i], mi[anc[u][i]][i]);
dir[u][i + 1] = dir[u][i] | dir[anc[u][i]][i];
}
for(int e = adj[u], v; e; e = nxt[e])
if((v = go[e]) != pre){
anc[v][0] = u;
mi[v][0] = emi[e];
dir[v][0] = edir[e] ^ 3;
dfs(v, u, rt);
}
}
void add(int u, int v, int w){
adde(u, v, 1, w);
adde(v, u, 2, w);
int d = sze[bel[u]] > sze[bel[v]] ? 2 : 1;
if(d == 2) swap(u, v);
anc[u][0] = v, mi[u][0] = w, dir[u][0] = d;
sze[bel[v]] += sze[bel[u]];
dfs(u, v, bel[v]);
}
int query(int u, int v){
if(bel[u] != bel[v]) return 0;
int d = 3, ret = INF;
if(dep[u] > dep[v])
swap(u, v), d = 0;
for(int i = 19; i >= 0; i--)
if(dep[v] - (1 << i) >= dep[u]){
if(dir[v][i] != (1 ^ d)) return 0;
ret = min(ret, mi[v][i]);
v = anc[v][i];
}
if(u == v) return ret;
for(int i = 19; i >= 0; i--)
if(anc[u][i] != anc[v][i]){
if(dir[v][i] != (1 ^ d) || dir[u][i] != (2 ^ d)) return 0;
ret = min(ret, min(mi[v][i], mi[u][i]));
u = anc[u][i];
v = anc[v][i];
}
if(dir[v][0] != (1 ^ d) || dir[u][0] != (2 ^ d)) return 0;
ret = min(ret, min(mi[v][0], mi[u][0]));
return ret;
}
int main(){
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
read(n), read(m);
for(int i = 1; i <= n; i++)
bel[i] = i, sze[i] = 1;
int op, a, b, c;
while(m--){
read(op), read(a), read(b);
a = (a + lastans) % n + 1;
b = (b + lastans) % n + 1;
if(op == 0) read(c), c = (c + lastans) % n + 1, add(a, b, c);
else write(lastans = query(a, b)), enter;
}
return 0;
}
O(松)代码
#include <stdio.h>
#include <vector>
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int MAXN = 100005;
int n, m;
int fa[MAXN][17];
int val[MAXN][17];
int getdep(int x) {
int ret = 0;
for (int i = 16; i >= 0; i--) {
if (fa[x][i]) {
x = fa[x][i];
ret += 1 << i;
}
}
return ret;
}
int jump(int x, int d) {
for (int i = 16; i >= 0; i--) {
if (d & (1 << i)) {
x = fa[x][i];
}
}
return x;
}
inline int min(int a, int b) {
return a < b ? a : b;
}
int getmin(int x, int d) {
int ret = 0x3f3f3f3f;
for (int i = 16; i >= 0; i--) {
if (d & (1 << i)) {
ret = min(ret, val[x][i]);
x = fa[x][i];
}
}
return ret;
}
int query(int a, int b) {
int d_a = getdep(a);
int d_b = getdep(b);
if (d_a <= d_b) {
return 0;
}
int b1 = jump(a, d_a - d_b);
if (b1 != b) {
return 0;
}
return getmin(a, d_a - d_b);
}
struct node {
node *next; // val = this - nodes
};
node nodes[MAXN];
#define NODE(i) (nodes + (i))
#define FOR_EACH_NODE(x, n) for (int (x) = (n) - nodes; (x) > 0; (x) = nodes[(x)].next - nodes)
struct list {
node *first, *last;
};
list new_list(node *a) {
return (list){a, a};
}
list join(list a, list b) {
a.last->next = b.first;
return (list){a.first, b.last};
}
template <class T>
struct vector {
std::vector<T> L, R;
int size, sizeL;
vector() {
size = 0;
sizeL = 0;
}
void push_front(const T &x) {
L.push_back(x);
++size;
++sizeL;
}
void push_back(const T &x) {
R.push_back(x);
++size;
}
void clear() {
L.clear();
R.clear();
size = 0;
sizeL = 0;
}
T & operator [](int x) {
return x < sizeL ? L[sizeL - 1 - x] : R[x - sizeL];
}
};
vector<list> _trees[MAXN];
vector<list> *trees[MAXN];
void add(int a, int b, int c) {
vector<list> *tree_a = trees[a];
int len_a = tree_a->size;
int len_b = getdep(b) + 1;
fa[a][0] = b;
val[a][0] = c;
if (len_a < len_b) {
int start = 1;
for (int i = 0; i < len_a; i++) {
while (1 << start < 1 + i) ++start;
node *n = (*tree_a)[i].first;
for (int j = start; 1 << j < 1 + i + len_b; j++) {
FOR_EACH_NODE(x, n) {
int tf = fa[x][j - 1];
fa[x][j] = fa[tf][j - 1];
val[x][j] = min(val[x][j - 1], val[tf][j - 1]);
}
}
}
} else {
int f = b;
int start = 1;
for (int i = 0; i < len_b; i++) {
f = fa[f][0];
while (1 << start < 1 + i) ++start;
for (int j = start; 1 << j < 1 + i + len_a; j++) {
FOR_EACH_NODE(x, (*tree_a)[(1 << j) - (1 + i)].first) {
int tf = fa[x][j - 1];
fa[x][j] = fa[tf][j - 1];
val[x][j] = min(val[x][j - 1], val[tf][j - 1]);
}
}
}
}
int root = jump(b, len_b - 1);
vector<list> *tree_root = trees[root];
int len_root = tree_root->size;
if (len_a < len_root) {
for (int i = len_b; i < len_root && i - len_b < len_a; i++) {
(*tree_root)[i] = join((*tree_root)[i], (*tree_a)[i - len_b]);
}
for (int i = len_root - len_b; i < len_a; i++) {
tree_root->push_back((*tree_a)[i]);
}
tree_a->clear();
} else {
for (int i = len_b; i < len_root && i - len_b < len_a; i++) {
(*tree_a)[i - len_b] = join((*tree_root)[i], (*tree_a)[i - len_b]);
}
for (int i = len_b + len_a; i < len_root; i++) {
tree_a->push_back((*tree_root)[i]);
}
for (int i = len_b - 1; i >= 0; i--) {
tree_a->push_front((*tree_root)[i]);
}
tree_root->clear();
trees[root] = tree_a;
}
}
void init() {
for (int i = 1; i <= n; i++) {
_trees[i].push_back(new_list(NODE(i)));
trees[i] = _trees + i;
}
}
int main() {
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
scanf("%d%d", &n, &m);
init();
int lastans = 0;
for (int i = 1; i <= m; i++) {
int op, a, b, c;
read(op), read(a), read(b);
a = (a + lastans) % n + 1;
b = (b + lastans) % n + 1;
if (op == 0) {
read(c);
c = (c + lastans) % n + 1;
add(a, b, c);
} else {
write(lastans = query(a, b)), putchar('
');
}
}
}
学姐的LCT
#include <iostream>
#include <cstdio>
template <class T>
void read(T &x){
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x){
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
#define MAXN 1000005
#define ivorysi
typedef long long int64;
using namespace std;
struct node {
node *lc,*rc,*fa;
int siz,val,minv;
void update() {
siz = 1;minv = val;
if(lc) {siz += lc->siz;minv = min(minv,lc->minv);}
if(rc) {siz += rc->siz;minv = min(minv,rc->minv);}
}
}pool[10000005],*tail = pool,*tr[MAXN * 2];
int borrow[MAXN];
bool isRoot(node *u) {
if(!u->fa) return true;
else return u->fa->lc != u && u->fa->rc != u;
}
void rotate(node *u) {
node *v = u->fa,*w = v->fa;
if(!isRoot(v)) (v == w->lc ? w->lc : w->rc) = u;
node *b = (u == v->lc ? u->rc : u->lc);
if(b) b->fa = v;
u->fa = w;v->fa = u;
if(u == v->lc) {u->rc = v;v->lc = b;}
else {u->lc = v;v->rc = b;}
v->update();
}
bool which(node *u) {
return u->fa->rc == u;
}
void Splay(node *u) {
while(!isRoot(u)) {
if(!isRoot(u->fa)) {
if(which(u->fa) == which(u)) rotate(u->fa);
else rotate(u);
}
rotate(u);
}
u->update();
}
void Access(node *u) {
for(node *x = NULL ; u ; x = u , u = u->fa) {
Splay(u);
u->rc = x;
u->update();
}
}
node* FindRoot(node *u) {
Access(u);Splay(u);
node *p = u;
while(p->lc) p = p->lc;
return p;
}
int Depth(node *u) {
Access(u);Splay(u);
return u->siz;
}
node* dfs(node *u,int siz) {
if(!u) return NULL;
if(u->siz < siz) return NULL;
int s = u->lc ? u->lc->siz + 1 : 1;
if(siz == s) return u;
if(siz < s) return dfs(u->lc,siz);
else return dfs(u->rc,siz - s);
}
bool FindPos(node *u,node *v,int d) {
Access(u);Splay(u);
return dfs(u,d) == v;
}
int GetMin(node *u,int siz) {
if(siz == u->siz) return u->minv;
int s = u->rc ? u->rc->siz + 1 : 1;
int t = min(u->val,u->rc ? u->rc->minv : 0x7fffffff);
if(siz == s) return t;
if(siz > s) return min(t,GetMin(u->lc,siz - s));
else return GetMin(u->rc,siz);
}
int Calc(node *u,int d,int t) {
Access(u);Splay(u);
return GetMin(u,d);
}
int N,M,Ncnt;
void Solve() {
int op,a,b,c;
scanf("%d%d",&N,&M);
Ncnt = N;
for(int i = 1 ; i <= N ; ++i) {tr[i] = tail++;tr[i]->siz = 1;tr[i]->val = tr[i]->minv = 0x7fffffff;}
int lastans = 0;
while(M--) {
read(op), read(a), read(b);
if(!op) read(c);
a = (a + lastans) % N + 1;
b = (b + lastans) % N + 1;
c = (c + lastans) % N + 1;
if(!op) {
tr[++Ncnt] = tail++;tr[Ncnt]->siz = 1;tr[Ncnt]->val = tr[Ncnt]->minv = c;
tr[Ncnt]->fa = tr[b];
Access(tr[a]);Splay(tr[a]);
tr[a]->fa = tr[Ncnt];
borrow[a] = c;
}
else {
int d = Depth(tr[b]);
if(!FindPos(tr[a],tr[b],d)) lastans = 0, puts("0");
else {
d = Depth(tr[a]) - d;
write(lastans = Calc(tr[a],d,borrow[b])), putchar('
');
}
}
}
}
int main() {
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
Solve();
return 0;
}