P11234 题解

考场做法。

题目大意

太复杂，自己看题面吧。

题目分析

直线考虑怎么线性。

先把整个过程看成一个完全二叉树。

一个人能走到最后有两个条件：自己擂主时能力值要够大，别人擂主时别人的能力值要够小。第一个条件很容易，预处理出每个点到根最后一次当擂主的轮数就行。第二个条件则需要预处理出每个子树最小能让能力值多小的人胜出。

实际上每个子树只有两种可能：胜出者固定为某个人，或者胜出者的能力值可以取当前轮数以上的任意值。记 $f_u$ 表示子树 $u$ 的胜出者能力值，$f_u=-1$ 表示可以任取，记 $h_u$ 表示节点 $u$ 的轮数，不妨设左孩子是擂主，则：

$$f_u=\begin{cases}f_{ls}&f_{ls}\ge h_u\\-1&f_{ls}=-1\\f_{rs}&otherwise\end{cases}$$

容易发现在 $n$ 个人逐渐加入的过程中，任意一个点的 $f$ 总是初始是 $-1$，某一时刻变为 $\ge0$ 的值后一直不变。所以在 $n$ 个人逐渐加入时，从对应的叶子节点向上更新 $f$，直到某个点处 $f$ 不变，复杂度是线性的。

那么当一个节点的 $f$ 值变为 $\ge0$ 时，如果下一轮中这个节点是擂主且 $f_u\ge h_{fa}$，那么 $u$ 的兄弟节点的子树中的所有人就再也不可能走到最后。这时候可以再维护一个 $g_u$ 表示加入第几个人之后，子树 $u$ 中的人就再也不可能走到最后了。$n$ 个人都加入后，求出每个点到树根路径上的 $g$ 最小值，即 $g_u=\min(g_u,g_{fa})$，得出叶子节点处的 $g$，也就是每个人在哪个时间前还有可能走到最后。

求出叶子节点的 $g$ 后，一个人对于答案的贡献就是一个前缀加。差分一下可以实现线性求出所有询问的答案。

整个过程是这样的：初始 $f=-1$，从 $1\sim n$ 逐个加入每个人，将 $f_u$ 改为 $a_i$，并向上更新。如果某个点的擂主被确定，则用当前时间更新另一颗子树的 $g$。结束后把 $g$ 推下来，对于每个人做一个前缀加。

人数太少时树的结构会变化，只需要每次人数达到 $2^k$ 时重做一遍就行。

总复杂度线性。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100001;
int n,m,k;
int a[N];
int c[N];
char d[N*2];
int f[N*4],g[N*4],h[N*4],b[N*4];
void dfs(int i,int t){
	f[i]=-1,g[i]=t+1;
	if(i>=(1<<k))return;
	int j=(i<<1)+d[i]-'0';
	h[j]=h[j^1]=h[i]-1;
	if(b[i])b[j]=b[j^1]=b[i];
	else b[j]=h[i],b[j^1]=0;
	dfs(j,t),dfs(j^1,t);
}
void upd(int i,int t){
	if(!i)return;
	if(f[i]!=-1)return;
	int j=(i<<1)+d[i]-'0';
	if(f[j]>=h[i])f[i]=f[j],g[j^1]=min(g[j^1],t);
	else if(f[j]!=-1)f[i]=f[j^1];
	if(f[j]!=-1)upd(i>>1,t);
}
void get(int i){
	if(i>=(1<<k))return;
	int j=(i<<1)+d[i]-'0';
	g[j]=min(g[j],g[i]);
	g[j^1]=min(g[j^1],g[i]);
	get(j),get(j^1);
}
ll s[N*2],res[N*2];
void solve(int t){
	int p=1<<(k-t);
	h[p]=t,b[p]=0;
	dfs(p,1<<t);
	for(int i=1;i<=n;i++){
		int j=i+(1<<k)-1;
		if(a[i]<b[j])g[j]=min(g[j],i);
		f[j]=a[i];
		upd(j>>1,i);
	}
	get(p);
	for(int i=1;i<=(1<<t);i++)s[i]=0;
	for(int i=1;i<=(1<<t);i++){
		int j=i+(1<<k)-1;
		s[g[j]-1]+=i;
	}
	for(int i=(1<<t);i>=1;i--){
		s[i-1]+=s[i];
		res[i]=s[i];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	while((1<<k)<n)k++;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++)cin>>c[i];
	for(int i=k-1;i>=1;i--)
		for(int j=0;j<(1<<i);j++)
			cin>>d[(1<<i)+j];
	cin>>d[1];
	int T;
	cin>>T;
	while(T--){
		int x[4];
		cin>>x[0]>>x[1]>>x[2]>>x[3];
		for(int i=1;i<=n;i++)a[i]^=x[i%4];
		for(int i=k;i>=0;i--)solve(i);
		ll ans=0;
		for(int i=1;i<=m;i++)ans^=i*res[c[i]];
		cout<<ans<<'\n';
		for(int i=1;i<=n;i++)a[i]^=x[i%4];
	}
	return 0;
}

谢谢观看！

GD-S01309李子优深圳中学(高一):

#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair

int read()
{
    int s = 0, f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f ^= (c == '-'); // 将f取反，遇到'-'时f变为-1
    for (; isdigit(c); c = getchar()) s = s * 10 + (c ^ 48); // 字符'0'-'9'的ASCII码差48，异或48相当于减'0'
    return f ? s : -s;
}
template<typename T> T& Fmin(T& x, T y){ return x = x < y ? x : y; }
template<typename T> T& Fmax(T& x, T y){ return x = x < y ? y : x; }
const int MAXN = (1 << 18) + 5, inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
int n, m, a_enc[MAXN], a[MAXN], N, K, R, ht[MAXN];
int dir[MAXN], win[MAXN], nxt[MAXN][20], kk;
bool vld[MAXN], able[MAXN], in[MAXN];
LL ans[MAXN], sum = 0;
std::vector<int> q[MAXN];
std::vector<int> clr[20];
char str[MAXN];
#define out(x) (sum -= (x), in[x] = False)
void erase(int x)
{
    if (!vld[x]) return ;
    vld[x] = False;
    if (x >= N)
    {
        if (in[x - N + 1]) out(x - N + 1);
        return ;
    }
    erase(x << 1), erase(x << 1 | 1);
}
void maintain(int x)
{
    if (x == 1) return ; // 根节点无需维护
    if ((x & 1) != dir[x >> 1]) // 若x是右孩子且与父节点方向不同
    {
        if (x & 1) erase(x ^ 1), win[x >> 1] = win[x], maintain(x >> 1); // 右孩子，删除左兄弟
        return ;
    }
    if (a[win[x]] >= ht[x >> 1]) win[x >> 1] = win[x], erase(x ^ 1), maintain(x >> 1); // 左兄弟值更大，保留左兄弟
    else if (x & 1) win[x >> 1] = win[x ^ 1], erase(x), maintain(x >> 1); // 右孩子值更小，保留左兄弟
}
void mian() // 主函数
{
    int XXX[4]; // 存储四个加密参数
    for (int o = 0; o < 4; o++)
        XXX[o] = read();
    for (int i = 1; i <= n; i++)
    {
        a[i] = a_enc[i] ^ XXX[i % 4]; // 解密a[i]
        if (a[i] < K && nxt[i][a[i] + 1] <= K) 
            clr[nxt[i][a[i] + 1]].push_back(i); // 将i加入对应颜色组
    }
    memset(win, -1, N << 3), R = 0; // 初始化win数组
    memset(vld, 1, N * (1 << 3)), memset(able + 1, 1, N); // 标记有效节点
    memset(in + (1 << 1), 0, N); // 标记节点是否在当前集合
    sum = 1, kk = 0, in[1] = True; // 初始集合包含根节点
    for (int i = 1; i <= n; i++)
    {
        
        if ((1 << kk) < i) // 当i超过当前集合大小，扩展集合
        {
            for (int j = (1 << kk) + 1; j <= (1 << (kk + 1)); j++)
                if (vld[j + N - 1]) sum += j, in[j] = True;
            ++kk;
            for (int j : clr[kk]) // 处理当前层的无效节点
            {
                if (in[j] && j < i) out(j);
                able[j] = False;
            }
        }
        if (vld[i + N - 1]) // 若节点i有效
        {
            if (!able[i] && in[i]) out(i); // 若节点i无效且在集合中，移除
            win[i + N - 1] = i, maintain(i + N - 1); // 更新win值并维护
        }
        for (int id : q[i]) ans[id] = sum; // 记录查询结果
    }
    LL output = 0;
    for (int i = 1; i <= m; i++)
        output ^= i * ans[i];
    printf("%lld\n", output);
    for (int i = 0; i <= K; i++) clr[i].clear(); // 清空颜色组
}
int st[100]; 
int main()
{
    freopen("arena.in", "r', stdin); // 重定向输入输出
    freopen("arena.out", "w', stdout);
    n = read(), m = read();
    for (int i = 1; i <= n; i++) a_enc[i] = read();
    for (int i = 1; i <= m; i++) q[read()].push_back(i); // 存储查询位置
    for (N = 1, K = 0; N < n; N <<= 1, K++) ; // 确定N的大小
    ht[1] = K; // 根节点高度为K
    for (int i = 2; i < N * 2; i++)
        ht[i] = ht[i >> (i & 1)] - 1; // 计算节点高度(2^h)
    for (int i = 1; i <= K; i++)
    {
        scanf("%s", str);
        for (int j = 0; j < (1 << (K - i)); j++) // 读取方向数组
            dir[(1 << (K - i)) + j] = str[j] - '0';
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= K; j++)
            st[j] = (N + i - 1) >> j; // 获取高位
        nxt[i][K + 1] = K + 1;
        for (int j = K; j; j--) // 计算nxt数组
            if ((st[j] << 1 | dir[st[j]]) == st[j - (1 << 1)]) // 左移或方向匹配
                nxt[i][j] = j;
            else nxt[i][j] = nxt[i][j + 1];
    }
    for (int T = read(); T--; ) mian(); // 处理多组测试数据
    return 0;
}

GD-S02955陈可佳广州市铁一中学(高一):

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;template<typename T>
inline void read(T &x) // 快速读入函数
{
    x=0;
    T w=1;
    char c=getchar();
    while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar(); // 处理负号
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); // 读取数字
    x*=w;
}

typedef long long ll;

const int S=200005,BS=25;

int n,m,ap[S],c[S];
char tmp[S];
int K,d[BS][S];
int cntd[BS];
int mxid,tpe[S<<2],dep[S<<<2],idx[S]; // 节点类型、深度、位置
int all,lb[S]; // all为全1掩码，lb为区间左端点
int a[S]; // 解密后的数组
int sta[S<<2],tme[S<<2],rp[S<<2]; // 状态、时间、右边界
ll ans[S]; // 查询结果

void build(int u, int l, int r, int dp) // 构建线段树节点
{
    mxid=max(mxid,u);if(l==r) return idx[l]=u,void(); // 叶子节点
    tpe[u]=d[dp][++cntd[dp]];dep[u]=dp; // 设置节点类型和深度
    int mid=l+r>>1;build(u<<1,l,mid,dp-1);build(u<<1|1,mid+1,r,dp-1); // 递归构建左右子树
}

inline void tmin(int &x, int &y) // 取最小值
{
    if(x>y) x=y;
}

inline void slove() // 处理每组测试数据
{
    int X[4];for(int i=0;i<4;i++) read(X[i]); // 获取加密参数
    for(int i=1;i<=n;i++) a[i]=ap[i]^X[i%4]; // 解密a[i]
    for(int i=1;i<=mxid;i++) sta[i]=all,tme[i]=rp[i]=n; // 初始化状态
    for(int i=1;i<=n;i++)
    {
        int u=idx[i];sta[u]=a[i]>K?0:(1<<a[i]); // 设置叶子节点状态
        int tt=i-1;u>>=1;
        while(u>0) // 向上更新父节点
        {
            int st=(1<<dep[u])-1,invst=all^st; // 当前状态掩码和反掩码
            int tmp=sta[u];sta[u]=0;
            int ls=u<<1|tpe[u],rs=ls^1; // 左右孩子
            if((sta[ls]&st)>0) sta[u]|=sta[rs]; // 左孩子有效，取右孩子状态
            else tmin(tme[u],tt); // 否则更新时间
            sta[u]|=sta[ls]&invst; // 合并状态
            if(sta[u]==tmp) break;u>>=1; // 状态不变，停止更新
        }
    }
    for(int i=1;i<=n;i++) ans[i]=0;rp[1]=n; // 初始化结果数组
    for(int u=2;u<=mxid;u++) // 计算右边界
    {
        int fu=u>>1;rp[u]=rp[fu];
        if(tpe[fu]^(u&1)) tmin(rp[u],tme[fu]); // 若类型不同，更新右边界
    }
    for(int i=1;i<=(1<<K);i++) // 处理每个位置i
    {
        if(i<=n) // 若i是有效位置
        {
            int u=idx[i],fu=u>>1,siz=1,rb=rp[idx[i]],x=a[i];
            while(u>1&&rb>=i&&siz<rb) // 查找有效区间
            {
                if((tpe[fu]^(u&1)^(1))&&x<dep[fu]){rb=siz;break;} // 类型不匹配，缩小右边界
                u>>=1,fu>>=1,siz<<=1;
            }
            if(rb>=i) ans[i]+=i,ans[rb+1]-=i; // 区间加i
        }
        int rb=min(i-1,rp[idx[i]]),l=lb[i]; // 计算左端点
        if(rb>=l) ans[l]+=i,ans[rb+1]-=i; // 区间加i
    }
    for(int i=1;i<=n;i++) ans[i]+=ans[i-1]; // 前缀和
    ll res=0;for(int i=1;i<=m;i++) res^=i*ans[c[i]]; // 计算最终结果
    printf("%lld\n",res);
}

int main()
{
//	printf("%lf\n",sizeof(sta)/(double)1024/1024);return 0;
    freopen("arena.in","r",stdin); // 重定向输入
    freopen("arena.out","w",stdout); // 重定向输出
    read(n),read(m);for(int i=1;i<=n;i++) read(ap[i]); // 读入原始数组ap
    for(int i=1;i<=m;i++) read(c[i]); // 读入查询位置
    K=0;while((1<<K)<n) K++; // 确定K的大小
    for(int i=1;i<=K;i++) // 读入方向数组d
    {
        scanf("%s",tmp+1);for(int j=1;j<=(1<<K-i);j++) d[i][j]=tmp[j]-'0';
    }
    build(1,1,1<<K,K); // 构建线段树
    all=(1<<K+1)-1; // 全1掩码
    for(int i=1;i<=(1<<K);i++) // 计算lb[i]
    {lb[i]=1;while(lb[i]*2<i) lb[i]<<=1;lb[i]++;}
    int T;read(T);while(T--){slove();} // 处理多组测试数据
    return 0;
}

GD-S00550吴同春中山市中山纪念中学(高一):

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i) // 循环宏
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
const int N=262145;
int f[N],g[N],n,m,w,b[N],c[N],a[N],d[N],Xr[4];ll ans[N]; // 全局变量
char S[N];
int gt(int o,int v,int x,int y) // 比较函数
{
    if(d[o]==0) // 类型0：取较大值
    {
        if(x==-1||x>=v) return x; // 左值无效或>=v，取右值
        return y; // 否则取左值
    }
    if(y==-1||y>=v) return y; // 类型1：取较大值，右值无效或>=v
    return x; // 否则取左值
}
void dp(int l,int r,int o,int v) // 构建叶子节点
{
    if(l+1==r) // 叶子节点
    {
        f[o]=a[l];g[o]=l; // 存储值和位置
        return;
    }
    int ls=o+o,rs=o+o+1; // 左右孩子
    if(gt(o,v,f[ls],-1)==-1)g[o]=g[rs]; // 左值无效，取右值位置
    else g[o]=g[ls]; // 否则取左值位置
    f[o]=gt(o,v,f[ls],f[rs]); // 取较大值
}
void calc(int l,int r,int o,int v,int pos,int fr,int mn) // 计算有效区间
{
    if(l+1==r) // 叶子节点
    {
        int wl=(fr?(1<<(fr-1)):0)+1,wr=mn; // 计算区间[wl,wr]
        if(wl<=min(wr,l)) ans[wl]+=l+1,ans[min(wr,l)+1]-=l+1; // 更新结果
        if(a[l]<w) // 若a[l]小于阈值w
        {
            if((1<<(a[l]+1))<=pos) // 若位置在有效范围内
            {
                int u=__builtin_ctz(pos^(pos&((