image frame

彁

375的养老院

F - Trees and XOR Queries Again

上课闲着无聊娱乐看了一眼，太典了，没忍住写了下

本质上就是问树上一条链上能不能xor出一个给定值，2e5级别

众所周知，线性基可以解决任意个数能不能xor出给定值

众所周知，线性基可以通过B^2的复杂度合并，所以你甚至可以上树剖，每个线段树的节点维护一个线性基，那么这样是O(nlogn^2B^2)，可能也能过吧，IDK

当然其实这个问题非常老套，有一个也许稍微冷门一点但是依旧广为人知的事情就是线性基是可以替换的，把问题退化到序列上的区间查询，对于一个以r为右端点的线性基，我们肯定希望基里面的元素尽可能靠右，所以我们可以通过替换一直更新线性基，让线性基更“优秀”，那么迁移到树上其实就是希望元素的深度尽可能深，对于一个查询，我们把（u，v）两个节点的线性基O(B^2）合并，那么我们真正的基就是合并后的基中深度不比LCA小的那些元素，然后就直接查询就行了，O(nlogn + nB^2）

可能这个是最优做法，如果你写点分治啥的遇到在线就不行了，复杂度也是最低了感觉

为什么突然想写了，因为感觉真的太典了，感觉出了好几次了，但是竟然在CF还是见到了，心血来潮写了

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
#include <bits/stdc++.h>
#include <random>

#define MP make_pair
#define pb push_back
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

using namespace std;
using LL = long long;
using ULL = unsigned long long;

const int maxn = 4e5 + 5;
const int maxk = 22;

int n;
int A[maxn];
int dep[maxn];
int fa[maxn][maxk];
vector<int> E[maxn];

struct linear_base{
    int base[maxk];
    int dep[maxk];

    void insert(int x, int d){
        for(int i = maxk - 1; i >= 0; --i){
            int b = ((x >> i) & 1);
            if(b){
                if(!base[i]){
                    base[i] = x;
                    dep[i] = d;
                    return;
                }
                else{
                    if(dep[i] < d){
                        swap(dep[i], d);
                        swap(base[i], x);
                    }
                }
                x ^= base[i];
            }
        }
    }

    void operator = (const linear_base &rhs){
        for(int i = 0; i < maxk; ++i){
            base[i] = rhs.base[i];
            dep[i] = rhs.dep[i];
        }
    }

    int query(int x, int d){
        for(int i = maxk - 1; i >= 0; --i){
            int b = ((x >> i) & 1);
            if(b && dep[i] >= d) 
                x ^= base[i];
        }
        return (x == 0);
    }

}B[maxn], tmp_base;

void merge(linear_base &a, linear_base &b)
{
    tmp_base = a;
    for(int i = 0; i < maxk; ++i){
        tmp_base.insert(b.base[i], b.dep[i]);
    }
}

void dfs(int x, int fr)
{
    B[x] = B[fr];
    B[x].insert(A[x], dep[x]);
    for(auto &v : E[x]){
        if(v == fr) continue;
        dep[v] = dep[x] + 1;
        fa[v][0] = x;
        dfs(v, x);
    }

    
}

int lca(int x, int y)
{
    if(dep[x] < dep[y])  swap(x, y);
    int d = dep[x] - dep[y];
    for(int i = maxk - i; i >= 0; --i){
        if(((d >> i) & 1)){
            x = fa[x][i];
        }
    }
    if(x == y)  return x;
    for(int i = maxk - 1; i >= 0; --i){
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i], y = fa[y][i];
        }
    }
    return x == y ? x : fa[x][0];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> A[i];
    }
    for(int i = 1; i <= n - 1; ++i){
        int a, b;
        cin >> a >> b;
        E[a].pb(b), E[b].pb(a);
    }

    dfs(1, 0);
    for(int j = 1; j <= maxk - 1; ++j){
        for(int i = 1; i <= n; ++i){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        }
    }

    int Q = 0;
    cin >> Q;
    while(Q--){
        int a, b, c;
        cin >> a >> b >> c;
        merge(B[a], B[b]);
        int l = lca(a, b);
        int ans = tmp_base.query(c, dep[l]);
        if(ans) cout << "YES\n";
        else cout << "NO\n";
    }

	return 0;
}

一些自用的东西

记忆力不太好啊，老是忘记，只能记一下了

排序

带索引排序

1
index = np.argsort(list)

vscode:justmycode:false 无效

添加设置

1
"purpose":["debug-in-terminal"]

模板

开个坑写一下一些模板

树

长链剖分

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>

#define pb emplace_back

using namespace std;
typedef long long LL;

const int maxn = 1e6 + 5;
const int INF = 1e9 + 7;

LL *now;
LL *F[maxn];
LL buf[maxn << 1];


int n;
vector<int> E[maxn];
int A[maxn], mi[maxn][21];
int son[maxn], dep[maxn], mx[maxn];
int lg[maxn];

template<typename T>
void read(T &x)
{
	x = 0;
	int fl = 1;
	char ch = getchar();
	while(!isdigit(ch) && ch != '-')
		ch = getchar();
	if(ch == '-')
		fl = -1, ch = getchar();
	while(isdigit(ch))
		x = x * 10 + ch - '0', ch = getchar();
	x *= fl;
}

void dfs1(int x, int fr)
{
	for(auto &v : E[x]){
		if(v == fr)
			continue;
		dep[v] = dep[x] + 1;
		dfs1(v, x);
		if(mx[v] > mx[son[x]])
			son[x] = v;
		mx[x] = max(mx[x], mx[v]);
	}
	mx[x] += 1;
}

int ask(int l, int r)
{
	int t = lg[r - l + 1];
	return min(mi[l][t], mi[r - (1 << t) + 1][t]);
}

void dp(int x, int fr)
{
	F[x][0] = A[0];
	if(son[x]){
		F[son[x]] = F[x] + 1;
		dp(son[x], x);
	}

	int _mx = 0;
	for(auto &v : E[x]){
		if(v == fr || v == son[x])
			continue;
		F[v] = now;
		now += mx[v];
		_mx = max(_mx, mx[v] + 1);
		dp(v, x);
		for(int j = 0; j < mx[v]; ++j){
			F[x][j + 1] += F[v][j]; 
		}
			
	}
	for(int j = 0; j <= _mx; ++j)
		F[x][j] = min(F[x][j], 1LL * ask(j, dep[x] + j));
}

int main()
{
	int T;
	read(T);
	while(T--){
		read(n);		
		for(int i = 0; i <= now - buf; ++i)
			buf[i] = 0;
		for(int i = 2; i <= n; ++i)
			lg[i] = lg[i >> 1] + 1;
		for(int i = 1; i <= n; ++i)
			E[i].clear(), son[i] = dep[i] = mx[i] = 0;
		for(int i = 0; i <= n - 1; ++i){
			read(A[i]);
			mi[i][0] = A[i];
		}

		for(int j = 1; j <= lg[n]; ++j)
			for(int i = 0; i + (1 << j) - 1 <= n - 1; ++i)
				mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);

		for(int i = 1; i <= n - 1; ++i){
			int u, v;
			read(u), read(v);
			E[u].pb(v), E[v].pb(u);
		}

		dfs1(1, 0);


		now = buf;
		F[1] = now;
		now += mx[1];
		dp(1, 0);

		LL ans = 0;
		for(int i = 0; i < mx[1]; ++i)
			ans += F[1][i];
		cout << ans << endl;
	}
}

笛卡尔树

算法笔记

笛卡尔树

用处

复建，连简单的数据结构都不记得了

笛卡尔树维护的是树最右边的一条链

常用于有限制条件下的求极值

代码

简单来说，对于小根堆形式的笛卡尔树，就是维护的增的单调栈

1
2
3
4
5
6
7
8

for(int i=1;i<=n;++i){
    while(tp&&A[stk[tp]]>A[i])
    	L[i]=stk[tp--];
    if(tp)
    	R[stk[tp]]=i;
    stk[++tp]=i;
}

题目

不记得之前写过什么题了，有遇到再更新

  • Copyrights © 2015-2023 0375w