题解 P3397 【地毯】

老K · 2017-11-07 11:15:19 · 题解

首先这题的主要思想很多大佬都讲了：就是差分，但是我的写法和他们的写法又不一样。

本题数据范围为n<=1000,m<=1000。

当n<=1000,m<=1000000甚至m<=10000000怎么办呢？

这时不管是O(n)的修改，还是甚至是O(log^2(n))，都是跑不过的。

而我们有一个O(1)修改的做法：二维差分。

设b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]。

这样每次修改b[i][j]相当于对任意i\le x,j \le y对a[x][y]做同样的修改

然后每次修改就直接++b[x1][y1],--b[x2+1][y1],--b[x1][y2+1],++b[x2+1][y2+1]即可。

也就是用O(1)的复杂度表示O(n^2)的覆盖（原话来自下面那篇题解“用O(1)复杂度来表示O(N)的覆盖”）

最后再直接a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]还原出原序列即可。

/* Author: CNYALI_LK

LANG: C++

PROG: 3397.cpp

*/

#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int a[1024][1024];
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int n,m,xa,ya,xb,yb;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
        ++a[xa][ya];
        --a[xb+1][ya];
        --a[xa][yb+1];
        ++a[xb+1][yb+1];
    }
    for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)printf("%d%c",a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1],j==n?'\n':' ');
    return 0;
}