P3755 [CQOI2017] 老C的任务题解

linjinkun · 2024-12-06 22:30:46 · 题解

前言：这个分块和刚被撤下的不同，因为这个分块时间复杂度正确，能通过所有 hack。

有没有什么可以不用离线都能解决问题的简单算法？答案是分块！！

60pts

首先遇到这个题目，先写一个比较暴力的 O(mn) 的算法，先排序，降掉一维，剩下一维询问时直接两个二分找到左端点和右端点，然后遍历从左端点到右端点有多少个数满足在第二维的范围内，求和即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node
{
    int x;
    int y;
    int p;
}a[N];
int cmp(node x,node y)
{
    return x.x == y.x?x.y<y.y:x.x<y.x;//排序规则
}
signed main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].p);
    }
    sort(a+1,a+n+1,cmp);//排序
    for(int i = 1;i<=m;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int l = 1,r = n,num = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            if(a[mid].x>=x1)//找到左端点
            {
                num = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
        l = 1,r = n;
        int num1 = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            if(a[mid].x<=x2)//找到右端点
            {
                num1 = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        long long sum = 0;//这里得开long long
        for(int i = num;i<=num1;i++)//遍历
        {
            int t = a[i].y;
            if(t>=y1&&t<=y2)//如果满足
            {
                sum+=a[i].p;//加上这个基站
            }
        }
        printf("%lld\n",sum);
    }
    return 0;
}

由于特殊的时间限制，我们获得了 60 分的好成绩。

100pts

遇到这种题，正解并不好想，考虑优化，复杂度瓶颈在于二分完后的遍历，于是我思来想去都没有想出做法，最终在 arrowpoint 这位大佬的指点下茅塞顿开，AC 了此题，他是怎么想的呢，分块！我们依旧将块长调整为 \sqrt{n}，新建两个块长数组 s 和 s1，s 处理的是散块，s1 处理的是整块，为什么要这样呢？因为我们首先要明白，分块为什么比暴力快？原因很简单，它对于整块有整体处理，这样的话对于每次询问区间 [l,r] 内的各种信息，都可以遍历 [l,r] 内的整块，最坏时间为 O(\sqrt{n})，因为最多只会有 \sqrt{n} 个块，而每个块都有现成的信息，这样一来每个块都只需要 O(1) 的时间就能知道这个块的信息，那总时间就是 O(1 \times \sqrt{n}) = O(\sqrt{n})，然后剩下的就是散块，由于散块最多两个，而散块的遍历每个块需要 O(\sqrt{n}) 的时间求信息，所以总时间就是 O(2 \times \sqrt{n}) = O(\sqrt{n})，那么整个程序整体复杂度为 O(m\sqrt{n})。这里的时间复杂度是忽略常数，所以 O(2 \times \sqrt{n}) = O(\sqrt{n})。知道了分块速度快的原因，所以说这里为什么要搞两个分块数组？因为散块不需要什么处理，不需要任何辅助加快时间的东西，自然就啥也不用动，但是整块就不一样了，它需要预处理出一些信息，对于这个题，arrowpoint 认为可以将整块处理的基本信息先排个序，因为反正都要算整个块，块里面的数怎么排序都无所谓，然后对于每个整块按照询问中的第二维二分出左右端点，然后求和就行，求和用前缀和优化，这样一来，与处理时间复杂度为 O(\sqrt{n} \times (\sqrt{n} \times \log \sqrt{n}))=O(n \log \sqrt{n})，\log \sqrt{n} 是个常数，大约为 9，所以说可以默认预处理时间复杂度为 O(n)。上面说完整块后，散块也就很简单了，直接将两个或一个散块全部遍历一遍，判断是否满足询问条件就行了。

所有的流程大概说了一遍，但这题的细节很多，仅根据上面说的写代码是 A 不了的，现在大概说一下分块的一些公式和注意事项（个人原创）：

求第 x 个块的左端点和右端点，设 len 为块长，n 为区间长度，则第 x 个块的左端点为 (x-1) \times len+1，右端点为 \min(x \times len,n)。这里重点说为什么右端点不是 x \times len，而是 \min(x \times len,n)，因为当 n 并不是完全平方数时，那这时就会发生 len<\sqrt{n}，k>\sqrt{n}，k 指的是最大的块编号，这个时候第 k 个块的长度绝对小于 len，所以使用 k \times len 是有可能发生越界行为的。
求编号为 x 的数在块长为 len 时所在的块编号为 \lfloor \frac{x+len-1}{len} \rfloor。它其实等价于 \lceil \frac{x}{len} \rceil 的，如果不懂就在草稿本上分类讨论一下就能明白了。
处理散块时当询问的左端点 l 和右端点 r 所在同一个块时，直接从 l 遍历到 r，否则把 l 这个块从 l 到 l 当前这个块结尾的编号全部遍历一遍，和从 r 当前这个块的开头的编号到 r 全部遍历一遍。

说完这些之后，再说本题的注意事项：

十年 OI 一场空，不开 long long 见祖宗！
程序里的二分（对于这道题），可能会有左端点找不到，或者右端点找不到，再或者左端点虽然满足大于等于询问的左端点，但却大于询问的右端点，也或者右端点虽然满足小于等于询问的右端点，但却小于询问的左端点，这些情况都说明对于这个询问，找不到满足询问要求的数，此时这次询问（或求值）答案（或贡献）已经确定为 0，无需继续查下去。

讲这么详细，写代码应该没问题了，这里直接放代码了（当然，会有注释）：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
struct node
{
    int x;
    int y;
    int p;
}a[N];
int cmp(node x,node y)
{
    return x.x == y.x?x.y<y.y:x.x<y.x;//照样排序
}
struct node1
{
    int y;
    int p;
}s[N],s1[N];
long long sum[N];//前缀和得开long long
int id[N];
int cmp1(node1 x,node1 y)//这个是整块的排序
{
    return x.y<y.y;
}
signed main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int len = sqrt(n);//记录块长
    for(int i = 1;i<=n;i++)
    {
        scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].p);
        id[i] = (i+len-1)/len;//计算所在块编号
    }
    sort(a+1,a+n+1,cmp);
    for(int i = 1;i<=n;i++)
    {
        s[i].y = a[i].y;//设置
        s[i].p = a[i].p;//设置
        s1[i] = s[i];//设置
    }
    for(int i = 1;i<=id[n];i++)
    {
        sort(s1+(i-1)*len+1,s1+min(i*len,n)+1,cmp1);//排个序
    }
    for(int i = 1;i<=n;i++)
    {
        sum[i] = sum[i-1]+s1[i].p;//求个前缀和
    }
    for(int i = 1;i<=m;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int l = 1,r = n,num = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            if(a[mid].x>=x1)//这边寻找第一维的左端点
            {
                num = mid;
                r = mid-1;
            }
            else
            {
                l = mid+1;
            }
        }
        if(!num||a[num].x>x2)//如果找不到或者不满足条件
        {
            printf("0\n");
            continue;
        }
        l = 1,r = n;
        int num1 = 0;
        while(l<=r)
        {
            int mid = l+r>>1;
            if(a[mid].x<=x2)//找第一维右端点
            {
                num1 = mid;
                l = mid+1;
            }
            else
            {
                r = mid-1;
            }
        }
        if(!num1||a[num1].x<x1)//如果找不到或者不满足条件
        {
            printf("0\n");
            continue;
        }
        long long ss = 0;//得开long long
        for(int i = id[num]+1;i<=id[num1]-1;i++)//求整块
        {
            int l = (i-1)*len+1,r = i*len,num2 = 0;
            while(l<=r)
            {
                int mid = l+r>>1;
                if(s1[mid].y>=y1)//在整块中二分找到第二维的左端点
                {
                    num2 = mid;
                    r = mid-1;
                }
                else
                {
                    l = mid+1;
                }
            }
            if(!num2||s1[num2].y>y2)//同上
            {
                continue;
            }
            l = (i-1)*len+1,r = i*len;
            int num3 = 0;
            while(l<=r)
            {
                int mid = l+r>>1;
                if(s1[mid].y<=y2)//在整块中二分找到第二维的右端点
                {
                    num3 = mid;
                    l = mid+1;
                }
                else
                {
                    r = mid-1;
                }
            }
            if(!num3||s1[num3].y<y1)//同上
            {
                continue;
            }
            ss+=sum[num3]-sum[num2-1];//求左端点到右端点的和
        }
        if(id[num] == id[num1])//如果在同一个块
        {
            for(int i = num;i<=num1;i++)//直接遍历
            {
                if(s[i].y>=y1&&s[i].y<=y2)
                {
                    ss+=s[i].p;
                }
            }
        }
        else
        {
            for(int i = num;i<=id[num]*len;i++)//分两次，第一次
            {
                if(s[i].y>=y1&&s[i].y<=y2)
                {
                    ss+=s[i].p;
                }
            }
            for(int i = (id[num1]-1)*len+1;i<=num1;i++)//第二次
            {
                if(s[i].y>=y1&&s[i].y<=y2)
                {
                    ss+=s[i].p;
                }
            }
        }
        printf("%lld\n",ss);//输出
    }
    return 0;
}

时间复杂度：O(n \log \sqrt{n}+m \sqrt{n} \times \log \sqrt{n})。在 3s 内通过绰绰有余。

效率还是不错的，估计卡常一下应该能在一秒内卡过，不过懒得弄了。

如果还有不会的地方，欢迎私信！！

附分块学习网址：这里。

P3755 [CQOI2017] 老C的任务 题解

60pts

100pts

P3755 [CQOI2017] 老C的任务题解