企业官网建设流程全解析

D

计数

给一个完全二叉树形成的区间max线段树，给一些约束，每个约束给线段树上一个点赋值v，表示这个点所在的子树，对应的叶子区间的max=v。叶子上是一个排列，问有多少种方案

首先是一些无解的情况

• 一个点被赋值多次且值不同，也就是一个子树有多个最大值
• 一个值x作为最大值，只能在线段树上的一条链内出现，如果在两个不是祖先-后代关系的点上都出现，则无解。这可以通过把每种值的所有点收集起来，检查是否在同一条链上。

还有一些无解是构造过程中点不够用了，这留到算方案数的时候处理。

考虑每一种值x出现的最浅和最深的点umn,umx。x一定在umx子树内，同时umn子树内的所有叶子不能超过x。

考虑把后一个约束做一次dfs下放到所有叶子，具体来说树上每个点约束au=xa_u=xau​=x的话，我们在dfs自顶向下的过程中，维护一个叶子，从根走到这个叶子过程中遇到的aua_uau​最小值（有多个约束都形如≤x,≤y\le x,\le y≤x,≤y的话应该取≤min⁡(x,y)\le \min(x,y)≤min(x,y)），最后到了叶子，如果约束为x的话，认为得到一个叶子，可以赋≤x\le x≤x的值，累加到容量数组v

对于第一个约束，也就是x一定在umx子树内，umx子树内的叶子不一定都能用来放x，要看前一步dfs下放下来的结果≤y\le y≤y，如果x≤yx\le yx≤y则可以把x放到这个叶子。因此对于每个第一种约束，要检查umx子树内的叶子有多少满足要求，可以用来放x，也累加到一个容量数组c里

最后我们有两个容量数组v,c。cic_ici​表示iii这个值能放到多少个位置里，viv_ivi​表示能放≤i\le i≤i的元素的叶子有多少。

到这一步是经典计数了，我们从大到小枚举值，对于一个值iii，首先考虑到所有能放≤i\le i≤i的叶子，可用容量tot增加viv_ivi​。然后考虑iii这个值放在哪，

• 如果iii曾被约束过，那么iii只能放到约束的cic_ici​个位置里，当然也消耗了一个可用容量tot。
• 如果iii没出现在约束中，那么iii可以在对当前可用的容量tot个位置里随便选一个，选完也会消耗一个tot里的位置

这类问题可以抽象为，每个元素都有个可放的区间[1,x][1,x][1,x]，给n个这样的约束，问所有元素放置的方案数？考虑从大到小确定每个元素放在哪，维护当前可放位置的容量，一个元素放完之后我们不用管它放在哪了，只要把容量-1

#include<iostream>#include<vector>#include<algorithm>using namespace std;constintMOD=998244353;// 数据范围：N <= 18，节点数最多 2^19 - 1 = 524287constintMAXN=1<<19;intn,q;intlimit_val[MAXN];// 记录题目给出的节点限制值，0 表示无限制vector<int>leaves;// 存储所有叶子节点的索引intleaf_limit[MAXN];// 每个叶子节点的值上限intv_cnt[MAXN];// v[x]：最大能填 x 的叶子数量intc_cnt[MAXN];// c[x]：数值 x 的候选叶子数量bool has_constraint[MAXN];// 标记数值 x 是否在限制中出现过// 第一步：自顶向下 DFS，计算每个叶子节点的上限，并统计 v[x]voiddfs_v(intu,intcurrent_limit){if(limit_val[u]!=0){current_limit=min(current_limit,limit_val[u]);}// 如果是叶子节点（索引 >= 2^n）if(u>=(1<<n)){leaf_limit[u]=current_limit;v_cnt[current_limit]++;return;}dfs_v(u*2,current_limit);dfs_v(u*2+1,current_limit);}// 第二步：自底向上/局部遍历，统计每个受限数值 x 的候选叶子数 c[x]intcount_c(intu,intx){// 如果该叶子的上限小于 x，说明它被更小的数卡死了，不能填 xif(u>=(1<<n)){return(leaf_limit[u]>=x)?1:0;}returncount_c(u*2,x)+count_c(u*2+1,x);}intmain(){ios_base::sync_with_stdio(false);cin.tie(NULL);if(!(cin>>n>>q))return0;intnum_leaves=1<<n;inttotal_nodes=(1<<(n+1))-1;// 读入限制条件for(inti=0;i<q;++i){intu,x;cin>>u>>x;if(limit_val[u]!=0&&limit_val[u]!=x){// 同一个节点被赋予了不同的值，无解cout<<0<<endl;return0;}limit_val[u]=x;}// 检查同一条祖先链上的限制是否冲突 (即同一个数值 x 是否出现在非祖先链的节点上)// 由于 N 很小，我们可以直接遍历所有限制节点，判断它们是否在同一条链上vector<vector<int>>nodes_with_val(num_leaves+1);for(intu=1;u<=total_nodes;++u){if(limit_val[u]!=0){nodes_with_val[limit_val[u]].push_back(u);}}for(intx=1;x<=num_leaves;++x){if(nodes_with_val[x].empty())continue;has_constraint[x]=true;// 检查是否都在同一条祖先链上// 找到最深的节点 u_max，然后看其他节点是否都是它的祖先intu_max=nodes_with_val[x][0];for(intu:nodes_with_val[x]){if(u>u_max)u_max=u;// 索引越大，深度越深}for(intu:nodes_with_val[x]){// 判断 u 是否是 u_max 的祖先bool is_ancestor=false;inttemp=u_max;while(temp>0){if(temp==u){is_ancestor=true;break;}temp/=2;}if(!is_ancestor){// 不在同一条祖先链上，无解cout<<0<<endl;return0;}}}// 计算 v[x]dfs_v(1,num_leaves);// 计算 c[x]for(intx=1;x<=num_leaves;++x){if(!has_constraint[x])continue;// 找到最深的限制节点 u_maxintu_max=nodes_with_val[x][0];for(intu:nodes_with_val[x]){if(u>u_max)u_max=u;}c_cnt[x]=count_c(u_max,x);if(c_cnt[x]==0){// 没有合法的候选位置，无解cout<<0<<endl;return0;}}// 第三步：从大到小贪心计算答案longlongans=1;longlongS=0;// 当前可用的叶子坑位数量for(intx=num_leaves;x>=1;--x){// 先解锁所有上限为 x 的叶子S+=v_cnt[x];if(has_constraint[x]){// 受限的数：方案数为候选位置数 c[x]ans=(ans*c_cnt[x])%MOD;// 消耗一个坑位，净变化为 +v[x] - 1S=S-1;}else{// 自由的数：方案数为当前可用坑位数 Sif(S<=0){// 没有坑位可填了，无解cout<<0<<endl;return0;}ans=(ans*S)%MOD;// 消耗一个坑位S=S-1;}}cout<<ans<<endl;return0;}

K

mex 贪心

一个数组，对于一个k，每个元素的值有ai,k−aia_i,k-a_iai​,k−ai​两种选择，q次询问每次给一个k，问每个元素都操作后，数组元素的mex最大值？

q很大，O(nq)O(nq)O(nq)可能超时。不能对于每个q来了再贪心计算。考虑预处理所有操作后mex可能变大的k，map保存起来。如果询问k不在这个map中，则答案就是初始不操作的mex，否则检查map保存的答案

实际上可能让mex变大的k，必须满足原数组a中至少存在一个x，mex=k−xmex=k-xmex=k−x，也就是和k操作后，能变为mex，这样才可能把整个数组的mex变大，那么这样的k只有O(n)O(n)O(n)个，对这O(n)O(n)O(n)个k贪心计算最大mex即可。

注意这题有点卡常，因此对每个k计算最大mex必须是严格O(n)O(n)O(n)的，如果是O(nlog⁡n)O(n\log n)O(nlogn)或者用哈希表查询都会超时，必须是用静态数组的O(n)O(n)O(n)

对于一个k，考虑a中每个x变不变，为了让mex尽量大，显然可以直接贪心，设变和不变的两个值，较小的是u较大的是v，如果u还不存在，一定变成u，否则才变成v。并且由于n个数的mex最大才n，可以只记录不超过n的uv，更大的忽略。最后检查记录的所有uv，跑一次mex，即为这个k的最大mex。

注意询问q有点大，因此保存所有候选k不能用哈希表，查询要严格不超过O(log⁡n)O(\log n)O(logn)，考虑map。

#include<bits/stdc++.h>using namespace std;#defineintlonglongvoidsolve(){intn;cin>>n;vector<int>a(n);for(inti=0;i<n;i++)cin>>a[i];// 原数组 mexvector<int>cnt(n+1,0);for(intx:a){if(x>=0&&x<=n)cnt[x]++;}intmex=0;while(mex<=n&&cnt[mex]>0)mex++;// 枚举候选 kmap<int,int>memo;for(intx:a){intk=mex+x;if(memo.count(k))continue;vector<bool>vis(n+2,false);for(inti=0;i<n;i++){intu=min(a[i],k-a[i]);intv=max(a[i],k-a[i]);// 优先尝试填补合格且未出现的 uif(u>=0&&u<=n&&!vis[u]){vis[u]=true;}elseif(v>=0&&v<=n){// u < 0，或者 u > n，或者 u 已经被占用，转而填补 vvis[v]=true;}}intcur_mex=0;while(cur_mex<=n&&vis[cur_mex])cur_mex++;memo[k]=cur_mex;}intq;cin>>q;intans=0;while(q--){intk;cin>>k;if(memo.count(k))ans^=memo[k];elseans^=mex;}cout<<ans<<'\n';}signedmain(){ios::sync_with_stdio(0);cin.tie(0);intT=1;cin>>T;while(T--)solve();return0;}