上一篇题解我们讲解了SCOI 2006（DAY 1）的题目，这篇博客就让我们走进更加奇幻迷离的SCOI 2006（DAY 2）的题目吧！

T1 数字立方体

题目描述：

有一个立方体被分成nnn的单位，坐标用(X,Y,Z)表示（1<=X,Y,Z<=n）。每个单位立方体内有一个绝对值不超过109的整数。统计有多少个子立方体的所有数之和是m的倍数。子立方体即满足x1<=X<=x2, y1<=Y<=y2, z1<=Z<=z2的所有单位立方体集合，其中1<=x1,x2,y1,y2,z1,z2<=n。

【输入】
输入文件cube.in第一行有两个整数n, m，表示立方体的边长和作除数的正整数。以下n*n行，每行有n个整数。首先是X=1, Y=1的n个单位立方体，然后是X=1, Y=2的n个, …最后是X=n, Y=n-1的n个和X=n和Y=n的n个，共n3个整数。

【输出】
输出文件cube.out仅包含一个数，即所有整数和为m的倍数的子立方体的个数。

【样例输入】
2 5
1 2
3 4
5 6
7 8

【样例输出】
5

AC思路：

练前缀和的一道经典好题【起码在我看来】。

首先可以考虑暴力做法。直接先算前缀和（然而三维前缀和我也推了好久），然后枚举立方体体对角线的两个坐标（x，y，z）和（xx，yy，zz）就可以了，然而在你欣喜地提交了这个复杂度为O(n^6)的程序后，你会发现，这样是的不能过的，会TLE大概一半的点。于是可以考虑优化。

然后可以发现，如果一个立方体为所求的立方体【即所有点的和是m的倍数】的话，那么它的最高平面以下的方块数字和与它最低平面-1以下的方块数字和在对m取余的条件下应该是相等的【只有这样才能保证中间那一块立方体对m取余为0】。

所以可以考虑记录后快速加减。这样的话我们只需要先枚举两个点对（x，y）和（xx，yy），不枚举z和zz，转而去枚举平面与高度就可以了。时间复杂度O(n^5)，这样就能过全部点了。

程序部分：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[50][50][50],f[50][50][50];
int pd[1100000],g[1100000];
int i,j,k,m,n,o,p,js,jl,xx,yy,zz,ans,tot;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    {
        scanf("%d",&a[i][j][k]);
        f[i][j][k]=a[i][j][k]+f[i-1][j][k]+f[i][j-1][k]+f[i][j][k-1]-f[i-1][j-1][k]-f[i][j-1][k-1]-f[i-1][j][k-1]+f[i-1][j-1][k-1];
    }//计算前缀和
    ans=0;tot=0;
    for(int x=1;x<=n;x++)
    for(int y=1;y<=n;y++)
    for(int xx=x;xx<=n;xx++)
    for(int yy=y;yy<=n;yy++)//枚举x，y，xx，yy
    {
        while(tot>0)pd[g[tot--]]=0;//清空上一轮的记录
        for(int k=1;k<=n;k++)
        {
            int s=(f[xx][yy][k]-f[xx][y-1][k]-f[x-1][yy][k]+f[x-1][y-1][k])%m;
            if(pd[s]==0)g[++tot]=s;
            ans=ans+pd[s];
            pd[s]++;
        }//枚举高度
        ans=ans+pd[0];//最后要再直接加上%m=0的数
    }
    printf("%d",ans);
    return 0;
}

T2 动态最值

有一个包含n个元素的数组，要求实现以下操作：
DELETE k：删除位置k上的数。右边的数往左移一个位置。
QUERY i j：查询位置i~j上所有数的最小值和最大值。
例如有10个元素：
位置 1 2 3 4 5 6 7 8 9 10
元素 1 5 2 6 7 4 9 3 1 5
QUERY 2 8的结果为2 9。依次执行DELETE 3和DELETE 6（注意这时删除的是原始数组的元素7）后数组变为：
位置 1 2 3 4 5 6 7 8
元素 1 5 6 7 4 3 1 5
QUERY 2 8的结果为1 7。

【输入】
输入文件minmax.in第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示删除操作，为2表示询问操作。

【输出】
输出文件minmax.out对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。

【样例输入】
10 4
1 5 2 6 7 4 9 3 1 5
2 2 8
1 3
1 6
2 2 8

【样例输出】
2 9
1 7

【限制】
50%的数据满足1<=n, m<=104，删除操作不超过100个
100%的数据满足1<=n, m<=106, 1<=m<=106
对于所有的数据，数组中的元素绝对值均不超过109

AC思路：

也是一个很经典的题目，要求我们实现带修改的线段树。

其实线段树也可以支持删除节点，只需要在原来的存储方式上变化一下就好了。

具体做法：把原来的每个点用l，r存区间左右边界变成用一个数字sum类似平衡树那样的存节点size，也就是子节点还有多少个没有被删除，然后查询的时候比较左右节点的num和当前要查询的点号就行：
查询分三种情况：

1. 查询区间左端点比当前左节点的num小，右端点比做节点num大，证明区间在左右子树中，分别查询。
2. 查询区间左端点比左子节点num小，右端点比左子节点num小，查左子树。
3. 查询区间左端点比左子节点num大，右子节点也比它大，查右子树。

删除分两种：

1. 删除number比左num小，递归左；
2. 删除number比左num大，递归右；

和主席树的修改有一点相同QwQ

程序实现：

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int i,j,k,m,n,o,p,js,jl,jk,x,y,minn,maxx;
int a[4000000];
struct node
{
    int l,r,min,max,num;
}tree[4000000];

int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}

int my_min(int x,int y)
{
    if(x<y)return(x);
    else return(y);
}

void pre()
{
    memset(tree,0,sizeof(tree));
    for(int i=1;i<=1000000;i++)
    {
        tree[i].min=214748364;
        tree[i].max=-214748364;
    }
}

void build(int l,int r,int root)
{
    tree[root].l=l;
    tree[root].r=r;
    if(l==r)
    {
        tree[root].min=a[l];
        tree[root].max=a[r];
        tree[root].num=1;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,root*2);
    build(mid+1,r,root*2+1);
    tree[root].num=tree[root*2].num+tree[root*2+1].num;
    tree[root].min=my_min(tree[root*2].min,tree[root*2+1].min);
    tree[root].max=my_max(tree[root*2].max,tree[root*2+1].max);
}

void del(int x,int root)
{
    if(tree[root].l==tree[root].r)
    {
        tree[root].min=214748364;
        tree[root].max=-214748364;
        tree[root].num=0;
        return;
    }
    int n1=tree[root*2].num,n2=tree[root*2+1].num;
    if(x<=n1)del(x,root*2);
    else del(x-n1,root*2+1);
    tree[root].num=tree[root*2].num+tree[root*2+1].num;
    tree[root].min=my_min(tree[root*2].min,tree[root*2+1].min);
    tree[root].max=my_max(tree[root*2].max,tree[root*2+1].max);

}

void query(int l,int r,int root)
{
    if(l==1 && r==tree[root].num)
    {
        minn=my_min(minn,tree[root].min);
        maxx=my_max(maxx,tree[root].max);
        return;
    }
    int n1=tree[root*2].num,n2=tree[root*2+1].num;
    if(l<=n1 && r>n1)
    {
        query(l,n1,root*2);
        query(1,r-n1,root*2+1);
    }
    else if(l<=n1 && r<=n1)query(l,r,root*2);
    else if(l>n1 && r<=n1+n2)query(l-n1,r-n1,root*2+1);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    pre();
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&o);
        if(o==1)
        {
            scanf("%d",&p);
            del(p,1);
        }
        else 
        {
            scanf("%d%d",&x,&y);
            minn=214748364;
            maxx=-214748364;
            query(x,y,1);
            printf("%d %d\n",minn,maxx);
        }
    }
    return 0;
}

结语

【不要问我为什么没有T3，T4，因为不会做！！！】
T3大体应该是计算几何，但我还没想到如何处理那个圆，T4就……，我哇的一声哭出来，希望有一天能把这两个√补上吧！