admin LV 10 SU @ 2026-4-23 21:48:46

考场上和队友

luogu://user/747879

树形态分析

先看一张示意图。

节点 $n$ 的最小儿子编号应为 $2+1+2+3+\dots+(n-1)=\dfrac{n(n-1)}2+2$ ，最大儿子编号是 $1+1+2+3+\dots+n=\dfrac{n(n+1)}2+1$ 。分别记为 $ls_n,rs_n$ 。

接着观察一个性质：树的层数非常小。

深度	最大节点编号
$1$
$2$	$rs_1=2$
$3$	$rs_2=4$
$4$	$rs_4=11$
$5$	$rs_{11}=67$
$6$	$rs_{67}=2279$

以此类推，得到下表：

深度	最大节点编号
$7$	$2598061$
$8$	$\approx3.374\times10^{12}$
$9$	$>10^{24}$

因此题目中的奇树最多 $9$ 层。

算法

考虑把一个节点的子树节点编号拆分成若干连续区间。注意到子树每一层都是一个连续区间，所以每个子树可以拆成至多 $9$ 个区间，例如 $3$ 的子树可以拆成 $[3,3],[5,7],[12,29],\dots$ ，直到超过 $n$ 。

现在只需要做如下问题：

给定序列 $a$ ，维护区间按位或和区间异或和查询。

这个不需要拆位，可以直接用线段树维护。操作时直接在需要操作的位使用 bitmask，按区间长度奇偶性修改异或和即可。

~~其实是队友写的线段树我也不知道细节。~~

为了减少空间损耗，我离散化了，需要注意离散化细节，不离散化不知道空间够不够。

代码实现

考场上写了一段时间，调了几下还卡了会空间，封榜后一发过了。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 9e6+9;
const int Q = 1e6+9;
ll n,q,p,u,c,nOp,pos[Q],nQ,po[N],nPo;
struct Operation {ll l,r,c;} op[N];
namespace Seg_Tree {
	#define int long long
	int tag[18000005], val[18000005];
	void pushdown(int p, int l, int r) {
		if (!tag[p]) return;
		if((po[(l + r) / 2 + 1] - po[l]) % 2 == 0) {
			val[p << 1] = (val[p << 1] ^ (val[p << 1] & tag[p]));
		}
		else {
			val[p << 1] = ((val[p << 1] ^ (val[p << 1] & tag[p])) | tag[p]);
		}
		if((po[r + 1] - po[(l + r) / 2 + 1]) % 2 == 0) {
			val[p << 1 | 1] = (val[p << 1 | 1] ^ (val[p << 1 | 1] & tag[p]));
		}
		else {
			val[p << 1 | 1] = ((val[p << 1 | 1] ^ (val[p << 1 | 1] & tag[p])) | tag[p]);
		}
		tag[p << 1] |= tag[p];
		tag[p << 1 | 1] |= tag[p];
		tag[p] = 0;
	}
	void modify(int p, int l, int r, int cl, int cr, int c) {
		if(l >= cl && r <= cr) {
			if((po[r + 1] - po[l]) % 2 == 0) {
				val[p] = (val[p] ^ (val[p] & c));
			}
			else {
				val[p] = ((val[p] ^ (val[p] & c)) | c);
			}
			tag[p] |= c;
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) / 2;
		if(mid >= cl) {
			modify(p << 1, l, mid, cl, cr, c); 
		}
		if(mid + 1 <= cr) {
			modify(p << 1 | 1, mid + 1, r, cl, cr, c);
		}
		val[p] = val[p << 1] ^ val[p << 1 | 1];
	}
	int query(int p, int l, int r, int cl, int cr) {
		if(l >= cl && r <= cr) {
			return val[p];
		}
		pushdown(p, l, r);
		int mid = (l + r) / 2, res = 0;
		if(mid >= cl) {
			res ^= query(p << 1, l, mid, cl, cr);
		}
		if(mid + 1 <= cr) {
			res ^= query(p << 1 | 1, mid + 1, r, cl, cr);
		}
		return res;
	}
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    while (q--)
    {
    	cin >> p >> u;
    	if (p == 2) c = 0;
    	else cin >> c;
    	__int128_t l = u,r = u;
		while (l <= n)
		{
			op[++nOp] = (Operation){l, r + 1, c};
			po[++nPo] = l;
			po[++nPo] = r + 1;
			l = l * (l - 1) / 2 + 2;
			r = r * (r + 1) / 2 + 1;
			r = min(r, (__int128_t)n);
		}
		if (!c) pos[++nQ] = nOp;
	}
	sort(po + 1, po + nPo + 1);
	nPo = unique(po + 1, po + nPo + 1) - po - 1;
	ll ans = 0;
	for (ll i = 1,j = 1; i <= nOp; ++i)
	{
		op[i].l = lower_bound(po + 1, po + nPo + 1, op[i].l) - po;
		op[i].r = lower_bound(po + 1, po + nPo + 1, op[i].r) - po - 1;
		if (op[i].c) Seg_Tree::modify(1, 1, nPo, op[i].l, op[i].r, op[i].c);
		else ans ^= Seg_Tree::query(1, 1, nPo, op[i].l, op[i].r);
		if (j <= nQ && i == pos[j]) cout << ans << endl,ans = 0,++j;
	}
    return 0;
}

0
admin LV 10 SU @ 2026-4-23 21:46:31
题意

定义一棵无限大的树，设其 bfs 序为 $1, 2, \dots$ ，则 $1$ 有 $1$ 个子节点， $2$ 有 $2$ 个子节点， $i$ 有 $i$ 个子节点。

我们只保留其中的前 $n$ 个点，然后给每个点赋一个初始 $=0$ 的值。要求支持 $q$ 次两种操作：
- 给定 $x, c$ ，将 $x$ 子树内所有点的值都二进制或上 $c$ 。
- 给定 $x$ ，求 $x$ 子树内所有点的值的二进制异或和。
$n \le 10^{18}$ ， $q \le 10^6$ ， $c \lt 2^{60}$ 。

Part 1

经过打表可以发现，前 $n$ 个点的树高最多为 $9$ 。具体的，以下是每一层的编号最小的点的编号：
```
1             // 1
2             // 2
3             // 3
5             // 4
12            // 5
68            // 6
2280          // 7
2598062       // 8
3374961778893 // 9
```
并且前 $7$ 层的点数只有 $2.6 \times 10^6$ 左右。

接下来的运算我们可能需要两个核心函数：
- 求点 $p$ 的父节点。对前 $7$ 层的节点进行预处理，后面的可以二分。
  
  具体的，设 $S_2(x) = \frac{x(x+1)}{2}$ ，则 $x$ 的直系儿子中编号最大的点编号为 $S_2(x) + 1$ 。依此就可以在 $O(\log n)$ 的复杂度内完成二分。
- 求点 $p$ 的子树大小（的奇偶性）。可以发现，这个子树在每一层都占据了连续的一段编号。因此，我们维护 $[l, r]$ ，转移到下一层即 $[l, r] \gets [S_2(l - 1) + 2, S_2(r) + 1]$ 。
  
  注意判断这个区间和 $[1, n]$ 的关系，并且注意运算过程中可能会爆 long long，需要使用 __int128_t。
Part 2

考虑 $c = 1$ 怎么做。那么，对于一个点 $x$ ，如果其到根路径上有任意一个点被操作了，那么它此时的子树异或和就是子树大小的奇偶性。

否则，因为树高很小，我们可以尝试在操作 $x$ 的时候，更新对它的所有祖先的答案的影响。具体的，设 $s_x$ 表示子树的异或和，那么，在更新 $x$ 时，我们先求出原来的 $s_x$ ，然后再求出新的 $s'_x$ （在这里就是子树大小奇偶性），那么我们要对 $x$ 到根上的所有 $s_i$ 都异或上 $s_x \oplus s'_x$ 。

注意一个 $s_x$ 在“ $x$ 到根路径上有点操作过”的时候的值是无意义的。

可以发现这个过程可以做到 $O(\log n + h)$ ，其中 $h$ 为树高。

Part 3

回到原题，如果直接拆位的话那复杂度会多一个 $\log V$ ，不太能过。

仍然用 Part 2 的做法。另设 $t_x$ 表示在 $x$ 应用过的所有 $c$ 的或和（不是异或和）。那么此时 $x$ 的子树和可以表述为：（不太会用 $\LaTeX$ 打这个东西）
```
(s[x] & ~t[x]) | (t[x] * siz(x))
```
其实就是将操作过的位置忽略掉，然后再用子树大小把真正的值赋上。具体存的时候只会存直接应用的值 $t'_x$ ，要求定义的 $t_x$ 只需将到根路径上的所有 $t'_x$ 或起来即可。

对于一个 $c$ ，我们可以直接忽略那些已经操作过的位。那么，剩下的位处理就和 Part 2 一模一样了。此时的 $s_x \oplus s'_x$ 可以表示为：
```
(query(x) & c) ^ (c * siz(x))
```
因此也可以做到 $O(\log n + h)$ 。

因为要存 $t, s$ ，实现过程可能需要用到 umap，反正没卡就过了。
```
#include <unordered_map>
#include <iostream>
using namespace std;

#define MAXN 5000006

using ll = long long;

ll n;

int fa[MAXN];
ll dl[10] = {
    0,
    1, // 1
    2, // 2
    3, // 3
    5, // 4
    12, // 5
    68, // 6
    2280, // 7
    2598062, // 8
    3374961778893, // 9
};

ll qfa(ll p) // 获得父节点
{
    if (p < dl[8])
    {
        return fa[p];
    }
    int cd = p < dl[9] ? 7 : 8;
    ll l = dl[cd], r = dl[cd + 1] - 1;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
        if ((__int128_t)mid * (mid + 1) / 2 >= p)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return l;
}

unordered_map<ll, int> mp;
int mid = (int)dl[8] - 1;
int id(ll p)
{
    if (p < dl[8])
    {
        return (int)p;
    }
    else if (!mp.count(p))
    {
        return mp[p] = ++mid;
    }
    return mp[p];
}

ll tag[MAXN], sum[MAXN];

bool siz(ll p) // 子树大小的奇偶性
{
    bool res = 1;
    __int128_t l = p, r = p;
    while (true)
    {
        l = l * (l - 1) / 2 + 2;
        r = r * (r + 1) / 2 + 1;
        if (r >= n)
        {
            if (l > n)
            {
                return res;
            }
            return res ^ ((n - l + 1) & 1);
        }
        res ^= (r - l + 1) & 1;
    }
    return 0;
}

ll query(ll p)
{
    ll res = sum[id(p)], ta = 0;
    for (ll q = p; q; q = qfa(q))
    {
        ta |= tag[id(q)];
    }
    return (res & ~ta) | (ta * siz(p));
}

void modi(ll p, ll c)
{
    ll ta = 0;
    for (ll q = p; q; q = qfa(q))
    {
        ta |= tag[id(q)];
    }
    c &= ~ta;
    ll nv = (c * siz(p)) ^ (query(p) & c);
    tag[id(p)] |= c;
    for (ll q = p; q; q = qfa(q))
    {
        sum[id(q)] ^= nv;
    }
}

int main()
{
    int q;
    cin >> n >> q;
    int cur = 1;
    for (int i = 1; i < dl[8]; i++)
    {
        bool end = false;
        for (int j = 1; j <= i; j++)
        {
            fa[++cur] = i;
            if (cur == dl[8] - 1)
            {
                end = true;
                break;
            }
        }
        if (end)
        {
            break;
        }
    }
    while (q--)
    {
        int o;
        ll x, c;
        cin >> o >> x;
        if (o == 1)
        {
            cin >> c;
            modi(x, c);
        }
        else
        {
            cout << query(x) << '\n';
        }
    }
    return 0;
}
```

ID

9684

时间

3000ms

内存

700MiB

难度

标签

递交数

已通过

上传者

admin

2 条题解

树形态分析

算法

代码实现

题意

Part 1

Part 2

Part 3

「THUPC 2026 初赛」庭中有奇树

信息

状态

开发

支持

关于

2 条题解

树形态分析

算法

代码实现

题意

Part 1

Part 2

Part 3

「THUPC 2026 初赛」庭中有奇树

信息

状态

开发

支持

关于

还没有账户？

登录