牛客多校第四场 D、E 题题解

D、E Jobs

D、E 题题意：有 $nn$ 家公司，第 $ii$ 家公司有 $m_{i}m\_i$ 个工作，对能力要求为 $(a_j,b_j,c_j)(a\_j,b\_j,c\_j)$，其中 $1\le a_j,b_j,c_j\le 4001\; \backslash leq\; a\_j,b\_j,c\_j\; \backslash leq\; 400$。若候选者能力值为 $(x,y,z)(x,y,z)$ 满足有一个工作符合 $x\ge a_j,y\ge b_j,z\ge c_{j}x\; \backslash geq\; a\_j,y\; \backslash geq\; b\_j,z\; \backslash geq\; c\_j$，则认为该候选者可以被该公司录用。$qq$ 次询问，每次给定一个候选者的能力值，问能被几个公司录用。D 题 $n\le 10n\; \backslash leq\; 10$，E 题 $n\le 1\times 10^{6}n\; \backslash leq\; 1\backslash times\; 10^6$，$q\le 2\times 10^{6}q\; \backslash leq\; 2\backslash times\; 10^6$。

解法：显然一个朴素思路为维护第 $ii$ 家公司对前两个能力要求分别为 $x,yx,y$ 时，最少需要多少的 $zz$ 才能录用。这样进行二维前缀和即可，复杂度 $\mathcal{O}(n{m}^2+q)\backslash mathcal\; O(nm^2+q)$。但是这样无法通过 E 题。

考虑如果只有两维的能力值 $(a_i,b_i)(a\_i,b\_i)$ 要求，考虑二位数点模型。首先根据 $a_{i}a\_i$ 从小到大排序，把完全包络的职位（$a_i\le a_j,b_i\le b_{j}a\_i\; \backslash leq\; a\_j,b\_i\; \backslash leq\; b\_j$）删除，则一定可以得到如下的阶梯状前缀和。

为了让一个公司对前缀和的影响至多只有 $11$——即一个公司如果有多个职位对候选者符合，在前缀和矩阵上的值也只有 $11$，绿点表示增加 $11$，红点表示减少 $11$，下方的矩形右上端点为 $(a_i,b_i)(a\_i,b\_i)$。灰***域表示该公司可以对哪些候选者发出 offer。记录该数组为 $p_{i,j}p\_\{i,j\}$。

考虑插入和删除一个职位会发生什么，以中间的矩形 $(a_i,b_i)(a\_i,b\_i)$ 为例。

1. 插入：$p_{a_i,b_i}p\_\{a\_i,b\_i\}$ 增加，$p_{a_i,b_{i-1}}p\_\{a\_i,b\_\{i-1\}\}$ 减少，$p_{a_{i+1},b_i}p\_\{a\_\{i+1\},b\_i\}$ 减少。
2. 删除：$p_{a_i,b_i}p\_\{a\_i,b\_i\}$ 减少，$p_{a_i,b_{i-1}}p\_\{a\_i,b\_\{i-1\}\}$ 和 $p_{a_{i+1},b_i}p\_\{a\_\{i+1\},b\_i\}$ 补回来。

其操作类似于链表。

接下来考虑第三维的影响。对每个职位按照 $c_{i}c\_i$ 从小到大进行排序，然后考虑分层进行，对于每一层内部和回归到这一二维问题，逐层职位堆叠起来。加入第三维且按从小到大顺序之后，对于第 $ii$ 个职位，考虑类似单调队列的想法：

1. 若已经存在的矩形（职位）满足 $a_j\ge a_{i}a\_j\; \backslash geq\; a\_i$ 且 $b_j\ge b_{i}b\_j\; \backslash geq\; b\_i$，则对于 $z\ge c_{i}z\; \backslash geq\; c\_i$ 的人，$jj$ 工作已经完全被 $ii$ 顶死了，弹出 $jj$；
2. 若存在矩形满足 $a_j\le a_{i}a\_j\; \backslash leq\; a\_i$ 且 $b_j\le b_{i}b\_j\; \backslash leq\; b\_i$，则当前这个职位被 $jj$ 职位顶掉了，不需要加入。

因而对于一家公司，可以 $\mathcal{O}(m\log m)\backslash mathcal\; O(m\; \backslash log\; m)$ 的预处理出 $pp$ 数组，然后进行 $\mathcal{O}(c^3)\backslash mathcal\; O(c^3)$ 的前缀和即可。每次询问可以做到 $\mathcal{O}(1)\backslash mathcal\; O(1)$，总复杂度 $\mathcal{O}(nm\log m+c^3+q)\backslash mathcal\; O(nm\; \backslash log\; m+c^3+q)$。

void dele(multiset<hh>::iterator pos,int h){
    --pre[pos->a][pos->b][h];
    if(pos==st.begin()){
        if(pos!=--st.end()){
            it1=pos,++it1;
            ++pre[it1->a][pos->b][h];
        }
    }
    else if(pos==--st.end()){
        it1=pos,--it1;
        ++pre[pos->a][it1->b][h];
    }
    else{
        it1=it2=pos,--it1,++it2;
        ++pre[pos->a][it1->b][h],
        ++pre[it2->a][pos->b][h],
        --pre[it2->a][it1->b][h];
    }
    st.erase(pos);
}
void ins(hh x){
    it=st.insert(x);
    ++pre[x.a][x.b][x.c];
    if(it==st.begin()){
        if(++it!=st.end()) --pre[it->a][x.b][x.c];
    }
    else if(it==--st.end()){
        if(it!=st.begin()) --it,--pre[x.a][it->b][x.c];
    }
    else{
        it1=it,--it1,it2=it,++it2;
        ++pre[it2->a][it1->b][x.c];
        --pre[it2->a][it->b][x.c];
        --pre[it->a][it1->b][x.c];
    }
}
IL int chk(hh x){
    it=st.upper_bound(x);
    if(it!=st.end()){if(it->b>=x.b){dele(it,x.c);return 0;}}
    if(it!=st.begin()){if((--it)->b<=x.b){flag=0;return 1;}}
    return 1;
}
int main()
{
    n=in(),q=in();
    for(int i=1;i<=n;++i){
        int k=in();
        for(int j=1;j<=k;++j)
          a[j]=(hh){in(),in(),in()};
        st.clear(),sort(a+1,a+k+1,cmp1);
        for(int j=1;j<=k;++j){
            flag=1;while(!chk(a[j]));
            if(flag) ins(a[j]);
        }
    }
    for(int i=1;i<=M;++i)
      for(int j=0;j<=M;++j)
        for(int k=0;k<=M;++k)
          pre[i][j][k]+=pre[i-1][j][k];
    for(int i=0;i<=M;++i)
      for(int j=1;j<=M;++j)
        for(int k=0;k<=M;++k)
          pre[i][j][k]+=pre[i][j-1][k];
    for(int i=0;i<=M;++i)
      for(int j=0;j<=M;++j)
        for(int k=1;k<=M;++k)
          pre[i][j][k]+=pre[i][j][k-1]; 
    int ans=0,lastans=0,seed=in();
    std::mt19937 rng(seed);
    std::uniform_int_distribution<> u(1,400);
    while(q--){
        int IQ=(u(rng)^lastans)%400+1;
        int EQ=(u(rng)^lastans)%400+1;
        int AQ=(u(rng)^lastans)%400+1;
        ans=(1ll*ans*seed%p+(lastans=pre[IQ][EQ][AQ]))%p;
    }
    printf("%d\n",ans);
    return 0;
}