二维前缀和,差分

include<bits/stdc++.h>

using namespace std;
namespace{
template<typename t="">
inline void read(T &s){
T f=1;s=0;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s<<3)+(ch^48);
s*=f;
}
}
int n,m;
int a[1005][1005];</typename>

int main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        int a2,b,c,d;
        read(a2);read(b);
        read(c);read(d);
//二维差分操作
        a[a2][b]+=1;
        a[a2][d+1]-=1;
        a[c+1][b]-=1;
        a[c+1][d+1]+=1;
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
//二维前缀和
            a[i][j]+=(a[i-1][j]+a[i][j-1]-a[i-1][j-1]);
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
} 
全部评论

相关推荐

07-23 15:05
门头沟学院 Java
熊大不大:不好意思KPI数据刚刚刷新,刚刚达标
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务