P11234

· · 题解

树大小会变是很麻烦的事情，所以我们首先假设树大小固定，因为实际上我们可以枚举所有可能的树大小，复杂度也是线性的。

定义“时刻 i”表示第 1\sim i 个人的能力值确定时的答案，h_x 表示 x 子树的高度，即擂主获胜需要的能力值。

一个显然的 O(n \log^2 n) 做法是，由于每个人的能力值只有不超过 \log_2 n 的部分是有效的，所以我们可以逐个确定能力值，对每个子树维护这个子树可能的胜者集合。具体来讲，我们可以对一个子树维护 c_i 表示有多少个能力值为 i 的人可能成为这个子树的胜者。

但是这太慢了。所以我们来观察一些性质。

首先，一个人可能会成为最终胜者计入答案中，当且仅当他在所有比赛中都没有确定地被打败。

我们观察到一个人似乎是在某一个时刻之后被确定地打败的......也就是说，这个人会在一段时刻前缀被计入答案。我们尝试具体描述一下这个前缀到底长什么样。如果可以描述清楚，这个题就做完了。

具体分析一下可以看出，一个人在一次比赛中确定地被打败只有以下两种情况：

我们发现第二个条件是容易的：在这个人的能力值尚未确定的时候，他不会受到这个条件的限制；在这个人的能力值确定之后，他的能力值就需要至少是所有他参加的他是擂主的比赛的最大值。这个容易线性处理出所有限制，而且和时刻无关。

要想考虑第一个条件，我们就仔细考虑一下子树确定胜者相关的事情。

对于一个子树 x 而言，存在一个时刻 t_x，在这个时刻之后，这个子树会有一个唯一确定的胜者 f_x，并且这个胜者不会改变。

也就是说，在 t_x 这个时刻，这个子树内的除了 f_x 之外的所有人（无论其能力值是否确定），都已经确定会被打败。故显然 f_x 不会改变。

那么，假如当前时刻为 T，这个人不是擂主而且他的兄弟子树是 u，他会被第一个条件打败就当且仅当 T \ge t_u 并且 a_{f_u} 足够赢下当前比赛。也就是说，假如 a_{f_u} 够大，他就只能贡献在 t_u-1 或更早的时刻。

好的！看来每个人贡献到答案的时刻确实是一个前缀（因为是很多个前缀的交），但是我们还不知道 f_x 和 t_x 怎么求。

我们考虑在树上 dp，那么 f_x 和 t_x 就可以由孩子节点的 f 和 t 值分类讨论一下得到了。值得一提的是，一个子树的胜者确定的时间不一定是其两个孩子确定时间的最大值：在左孩子是擂主的情况下，有可能左孩子确定之后直接赢了，就没有右孩子什么事了。

获胜的人是谁直接根据题意判一判就好。

因为一个人会参加 O(\log n) 场比赛，所以要做到线性的话，我们不能对每个人大力枚举所有的比赛，而是可以用类似线段树标记下传的方式把所有限制传到叶子上。

实现上，我们一遍 dfs 预处理出每个子树的 f 和 t，第二遍 dfs 计算所有限制并下传，然后再差分一下就可以求出所有时刻的答案了。

时间复杂度 O(T(n+m))。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N ((1<<17)+5)
ll diff[N];
int fc[N<<1],tc[N<<1];
int a[N];
int n,m,Tc;
char tmp[N];
int D[N];
int A[N],c[N];
int K;
void dfs1(int x,int h){
    if(!h){
        fc[x]=a[x-(1<<K)+1];
        tc[x]=x-(1<<K)+1;
        return;
    }
    dfs1(x<<1,h-1);
    dfs1(x<<1|1,h-1);
    if(!D[x] && fc[x<<1]>=h)tc[x]=tc[x<<1];
    else tc[x]=tc[x<<1|1];
    fc[x]=fc[x<<1|(D[x]^(fc[(x<<1)|D[x]]<h))];
}
void dfs2(int x,int hi,int h,int L,int R){
    if(L>R)return;
    if(!h){
        int v=x-(1<<K)+1;
        if(L<min(R,v))diff[L]+=v,diff[min(R,v)]-=v;
        if(a[v]>=hi && max(v,L)<R)diff[max(v,L)]+=v,diff[R]-=v;
        return;
    }
    if(!D[x]){
        dfs2(x<<1,max(hi,h),h-1,L,R);
        dfs2(x<<1|1,hi,h-1,L,fc[x<<1]>=h?min(R,tc[x<<1]):R);
    }
    else{
        dfs2(x<<1,hi,h-1,L,fc[x<<1|1]>=h?min(R,tc[x<<1|1]):R);
        dfs2(x<<1|1,max(hi,h),h-1,L,R);
    }
}
int main(){
    freopen("arena.in","r",stdin);
    freopen("arena.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]);
    for(int i=1;i<=m;i++)scanf("%d",&c[i]);
    K=__lg(n-1)+1;
    for(int d=K-1;d>=0;d--){
        scanf("%s",tmp);
        for(int i=0;i<(1<<d);i++)D[i+(1<<d)]=tmp[i]-'0';
    }
    scanf("%d",&Tc);
    while(Tc--){
        int X[4];
        scanf("%d%d%d%d",&X[0],&X[1],&X[2],&X[3]);
        for(int i=1;i<=n;i++)a[i]=A[i]^X[i&3];
        dfs1(1,K);
        for(int i=0;i<=n;i++)diff[i]=0;
        for(int d=0;d<=K;d++)dfs2(1<<(K-d),0,d,d==0?1:(1<<(d-1))+1,(1<<d)+1);
        for(int i=1;i<=n;i++)diff[i]+=diff[i-1];
        ll ans=0;
        for(int i=1;i<=m;i++)ans^=i*diff[c[i]];
        printf("%lld\n",ans);
    }
    return 0;
}