前缀和（三）

题目：激光炸弹

1 链接

P2280 [HNOI2003] 激光炸弹 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2.大体思路

先开辟一个全局变量的 s 二维数组，这个二维数组开成 s [ 5010 ] [ 5010 ] ，这个是为了，能够将它所给的所有有价值的目标都包含进去（注意看数据 xi yi 的范围）

• 为了等下构建前缀和数组方便，我们会空出第一行和第一列-->为了避免处理边界问题，那么由于前缀和数组是从（1，1）这个点开始的，那么考虑到我们的数据会出现（0，0），那么我们让所有输入的坐标x坐标+1，y坐标+1
• 然后去构建前缀和数组
• 最后去遍历这个前缀和数组，但从（m,m)这个点开始遍历，（因为从这个点开始，爆炸刚好覆盖最多，如果从（m-1,m-1）开始它会覆盖到一下无效区域，那么从这个点开始，根本不可能会是毁灭最多价值的点）
• 定义一个res变量，赋值为1，那么爆炸的区域就是：左上角为：(  i - m , j - m )，右下角为（  i ，j ）,那么则此刻爆炸的总价值为 s[ i ] [ j ]-s[ i ][ j-m ]-s[ i-m ][ j ]+s[ i-m ][ j-m ]
• 每次遍历一个子矩阵，并更新res=max(res,s[i][j]-s[i][j-m]-s[i-m][j]+s[i-m][j-m])

3.代码实现

#include<iostream>
#include<algorithm>
using namespace std;

const int N=5010;
int s[N][N];

int main()
{
    int n,m;
    cin>>n>>m;
    while(n--)
    {
        int x1,y1,v;
        cin>>x1>>y1>>v;
        s[x1+1][y1+1]+=v;//处理多个目标在同一位置上
    }
    for(int i=1;i<N;i++)
    {
        for(int j=1;j<N;j++)
        {
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+s[i][j];
        }
    }
    int res=0;
    for(int i=m;i<N;i++)
    {
        for(int j=m;j<N;j++)
        {
            res=max(res,s[i][j]-s[i][j-m]-s[i-m][j]+s[i-m][j-m]);
        }
    }
    cout<<res;
    return 0;
    
}

题目：递增三元组

1 链接

1236. 递增三元组 - AcWing题库

2.大体思路

 由于 ai  bi , ci 的数据都会出现从0开始这种情况，那么我们则就让所有输入数据都自增 1（原因和上面一样）

 本题的核心思路就是：一个一个去遍历B数组，b[ i ]，我们在A数组中去找小于b[ i ]的有多少，在C数组去找大于b[ i ]的有多少

 法一：排序+二分查找

• 先将 A B C 三个数据排一个升序
• 然后再去遍历B数组，通过二分查找，在A数组中去找第一个大于等于b[ i ]的数的下标，在C数组里去找第一个大于b[ i ]的数的下标，这里我们调用lower_bound和upper_bound函数去实现
• 定义一个ans变量去统计每一个b[ i ]所能组成的三元组的个数

 法二：前缀和

• 创建cnt1，cnt2 数组来分别统计A,C数组中每个元素出现的次数
• 然后对cnt1 ,cnt2 数组分别进行求前缀和，这里求的前缀和是从0到1e5的，（这个是因为cnt1[ a[ i ] ] ++，这个a[ i ]可能很大，根据它的数据范围，那么这就意味着cnt1数组本身就应该开到1e5）
• 去遍历B数组，b[ i ]，我们在A数组中去找小于b[ i ]的有多少，在C数组去找大于b[ i ]的有多少，那么我们可以直接通过前缀和数组进行查询，时间复杂度为O( 1 )

3.代码实现

法一：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
typedef long long ll;
int a[N],b[N],c[N];
unsigned long long ans=0;

int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    sort(c+1,c+n+1);
    
    for(int i=1;i<=n;i++)
    {
        ll k=lower_bound(a+1,a+n+1,b[i])-a-1,l=n-(upper_bound(c+1,c+n+1,b[i])-c-1);
        ans+=k*l;
    }
    cout<<ans;
    return 0;
 
    
}

法二：

#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e5+10;
typedef long long ll;
int a[N],b[N],c[N];
unsigned long long ans=0;
int cnt1[N],cnt2[N];
ll s1[N], s2[N];//-->用来统计cnt1,cnt2的前缀和，这样去查询时，只要O(1)的时间，就可以查询
//统计cnt1,cnt2的前缀和-->就是统计次数的前缀和
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        a[i]++;
        cnt1[a[i]]++;//-->统计每个数出现的次数
    }
    for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]++;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&c[i]);
        c[i]++;
        cnt2[c[i]]++;
    }
    
    for(int i=1;i<N;i++)
    {
        s1[i]=s1[i-1]+cnt1[i];
        s2[i]=s2[i-1]+cnt2[i];
    }
    
    //然后在cnt1中去查询有多少小于b[i],在cnt2中去查询有多少大于于b[i]
    //由于我们创建了关于cnt1，cnt2，的前缀和数组，那么我们只要直接访问前缀和数组就可以
    
    for(int i=1;i<=n;i++)
    {
        ll k=s1[b[i]-1],m=s2[N]-s2[b[i]];
        ans+=k*m;
    }
    cout<<ans;
  
}