50分二维差分模板求助

senak @ 2023-12-26 22:38:14

#include<iostream>
#define int long long
using namespace std;
int a[1001][1001];
int d[1001][1001];
signed main()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        d[x1][y1]++;
        d[x1][y2 + 1]--;
        d[x2 + 1][y1]--;
        d[x2 + 1][y2 + 1]++;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            d[i][j] += d[i][j - 1] + d[i - 1][j] - d[i - 1][j - 1];
            cout << d[i][j] << " ";
        }cout << endl;
    }
    return 0;
}

by shb20111113 @ 2023-12-26 22:42:29

@senak 我的代码是暴力：

#include <iostream>
#define int long long 
using namespace std;
int c[1010][1010];
int n,m,x1,x2,y1,y2;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x1>>y1>>x2>>y2;
        for(int ii=x1;ii<=x2;ii++){
            for(int jj=y1;jj<=y2;jj++){
                c[ii][jj]++;
            }
        } 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<c[i][j]<<" "; 
        }
        cout<<endl;
    }
    return 0;   
}

by senak @ 2023-12-26 22:43:11

@shb20111113可是我就想用二维差分做呜呜呜

by senak @ 2023-12-26 22:50:42

emm把数组开大一点就过了

by cyt123bc @ 2024-02-24 09:27:51

@senak 这道题可以用暴力做

by name1ess_0123210 @ 2024-03-11 21:53:11

@senak 确实，因为模板中g[x2+1][y2+1]+=c;（各自找代码中的对应位置谢谢），开到1002就能AC但1001不行，原因在此。

by wangderui111 @ 2024-05-30 21:03:14

#include<bits/stdc++.h>
using namespace std;
int ans[1005][1005];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        for(int x=x1;x<=x2;x++){
            for(int y=y1;y<=y2;y++){
                ans[x][y]++;
            }
        }
    }for(int x=1;x<=n;x++){
        for(int y=1;y<=n;y++){
            cout<<ans[x][y]<<" ";
        }cout<<endl;
    }return 0;
}

来自萌新的疑问，为什么要用差分

O(mnn)才1000000000（最坏）