P8666 [蓝桥杯 2018 省 A] 三体攻击 题解

· · 题解

前言：本题解提供了一个做高维差分时，复杂度比容斥更优的解法，详细可以看 囧仙的日报

首先考虑修改操作，相当于在三维空间里每次指定一个立方体，对其内部点加上某个值

容易想到用三维差分维护

可以发现，每艘战舰随时间增加收到的伤害是不减的

故记答案为 m ，则 m 以前的时刻都合法， m 及其后面的时刻都不合法

这个显然可以二分答案

Q1： 为什么不一边暴力操作一边找到 m 呢？

A1： 因为这样复杂度会是立方体边长的立方量级，不太可接受。

Q2： 为什么一定要二分呢？

A2： 因为差分给到的是一个快速修改的手段，前缀和还原再 check 是很低效的。倘若一边修改一边 check，复杂度还不如暴力。差分+二分虽然多次重复了前面的某些修改，但它降低了 check 的次数。对于本题是一个很不错的选择。

（有点像某些分块的思想，都是平衡查询与询问的复杂度，降低整体的复杂度，但有点不一样）

Q3：不能用倍增避开重复吗？

A3：倍增跳过头的话需要一个还原的步骤，还是会"重复"，而且写起来麻烦。

总而言之，我们确定了差分+二分的做法

二分一个时间 T ，把它前面的操作都做了，再做一次 check，看看是否有战舰爆炸

接下来就是差分板子了

但是大多数同学写的都是容斥做差分

记差分维数为 n ，操作数为 m ，立方体边长为 a (假设等边，只看量级)

则容斥做法的复杂度为 O(m \times 2^n+a^n \times2^n)

多次差分的复杂度可以做到 O(m \times 2^n+a^n \times n)

（多项式两项分别为修改和查询复杂度）

（其实在 n 比较小的时候没太大区别）

多次差分的思想大概是对着 z 方向， y 方向， x 方向分别差分一次

最后做三次前缀和就合起来了

避免了容斥系数的讨论，不失为一个兼具效率与好写的做法

（具体内容在日报里有图示，不再过多展开）

贴代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;
int s1[maxn],s2[maxn],s3[maxn],ans[maxn];
int A,B,C;
inline int rd(){
    int x=0;char c=getchar();int f=1;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
inline int getid(int x,int y,int z){
    return ((x-1)*B+(y-1))*C+z;
}
struct node{
    int a1,b1,c1,a2,b2,c2,val;
}at[maxn];
int d[maxn];
int m;
inline void up3(int a1,int b1,int c1,int a2,int b2,int c2,int val){
    s3[getid(a1,b1,c1)]+=val;
    s3[getid(a1,b1,c2+1)]-=val;
    return;
}
inline void up2(int a1,int b1,int c1,int a2,int b2,int c2,int val){
    up3(a1,b1,c1,a1,b1,c2,val);
    up3(a1,b2+1,c1,a1,b2+1,c2,-val);
    return;
}
inline void up1(int a1,int b1,int c1,int a2,int b2,int c2,int val){
    up2(a1,b1,c1,a1,b2,c2,val);
    up2(a2+1,b1,c1,a2+1,b2,c2,-val);
    return;
}
inline bool check(int T){
    memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));memset(ans,0,sizeof(ans));memset(s3,0,sizeof(s3));
    for(int i=1;i<=T;i++)up1(at[i].a1,at[i].b1,at[i].c1,at[i].a2,at[i].b2,at[i].c2,at[i].val);
    for(int i=1;i<=A;i++){
        for(int j=1;j<=B;j++){
            for(int k=1;k<=C;k++)
            s2[getid(i,j,k)]=s2[getid(i,j,k-1)]+s3[getid(i,j,k)];
        }
    }
    memset(s3,0,sizeof(s3));
    for(int i=1;i<=A;i++){
        for(int j=1;j<=B;j++){
            for(int k=1;k<=C;k++){
                s3[getid(i,j,k)]=s3[getid(i,j-1,k)]+s2[getid(i,j,k)];
            }
        }
    }   
    for(int i=1;i<=A*B*C;i++)s2[i]=s3[i];
//  memset(s1,0,sizeof(s1));
//  for(int i=1;i<=A;i++){
//      for(int j=1;j<=B;j++){
//          for(int k=1;k<=C;k++){
//              s1[getid(i,j,k)]=s1[getid(i,j-1,k)]+s2[getid(i,j,k)];
//          }
//      }
//  }
//  for(int i=1;i<=A*B*C;i++)s2[i]=s1[i];
    for(int i=1;i<=A;i++)
        for(int j=1;j<=B;j++)
            for(int k=1;k<=C;k++){
            s2[getid(i,j,k)]+=s2[getid(i-1,j,k)];
    }
    for(int i=1;i<=A;i++){
        for(int j=1;j<=B;j++){
            for(int k=1;k<=C;k++){
                if(s2[getid(i,j,k)]>d[getid(i,j,k)])return 1;
            }
        }
    }
    return 0;
}
int main(){
    A=rd();B=rd();C=rd();m=rd();
    for(int i=1;i<=A*B*C;i++)d[i]=rd();
    for(int i=1;i<=m;i++){
        at[i].a1=rd();at[i].a2=rd();
        at[i].b1=rd();at[i].b2=rd();
        at[i].c1=rd();at[i].c2=rd();
        at[i].val=rd();
    }
    int l=0,r=m+1,mid;
    while(l+1!=r){
        mid=l+r>>1;
        if(!check(mid))l=mid;
        else r=mid;
    }
    printf("%d\n",r);
}

彩蛋：

可能是因为数据的锅或边界问题，数组大小开到 10^7 都会越界访问，所以如果你把 s1,s2 和 ans 数组删掉，那么这份代码就过不了了

或者要把数组开到 4 \times 10^7

但它报的是 WA 而不是 RE ，这玩意我从4月调到现在才知道。。。

ps：

因为函数调用太多的问题，这玩意跑得比容斥慢（笑）

但在高维情况下这个做法优势很大，具体去看 sosdp 相关内容，不多赘述