題目鏈接：點擊查看

題目大意：給出一個n*m的矩陣，開始全部初始化為0，然后給出一系列的小矩陣的范圍，小矩陣中的格子全部變?yōu)?，最后再給出一些查詢，查詢矩陣范圍內(nèi)是否所有的格子都是1，是的話輸出yes，否則輸出no

題目分析：二維差分+二維前綴和，

這里放一篇個人覺得不錯的差分博客：點擊查看

然后二維前綴和不多贅述了，很早之前就已經(jīng)掌握了的知識了。

因為初始化全部為0，我們在將一系列的小矩陣變?yōu)?的過程中，并不需要全部變?yōu)?，只需要將對角線上的點分別賦值表示差分即可，等操作完畢后，對差分的數(shù)組求一下前綴和，這個時候每個點(i,j)所表示的值，是該點相對于0來說變化了多少，在這個題目中，我們可以保證每個點的值都是大于等于零的，因為在區(qū)間內(nèi)的操作都是只加不減，隨后將每個點的值都改成0或1，原先大于等于1的全部變?yōu)?即可，再求一次前綴和，這個時候輸入?yún)^(qū)間后只需要判斷區(qū)間的大小（即面積）和前綴和是否相等就好了

代碼簡潔，直接上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e7+100;int a[N];int n,m;int getid(int i,int j) {if(i==0||j==0||i>n||j>m)//考慮越界情況，如果越界返回0，因為a[0]正常情況下是訪問不到的，所以讓他一直等于0即可return 0;return (i-1)*m+j; }void update(int i,int j,int val) {if(getid(i,j)==0)//如果越界就不需要更新了return;a[getid(i,j)]+=val; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[getid(i,j)]=0;int t;scanf("%d",&t);while(t--){int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);//維護差分區(qū)間update(x,y,1);update(xx+1,yy+1,1);update(x,yy+1,-1);update(xx+1,y,-1);}for(int i=1;i<=n;i++)//前綴和for(int j=1;j<=m;j++)a[getid(i,j)]+=a[getid(i-1,j)]+a[getid(i,j-1)]-a[getid(i-1,j-1)];for(int i=1;i<=n;i++)//轉(zhuǎn)換為0和1for(int j=1;j<=m;j++)a[getid(i,j)]=a[getid(i,j)]?1:0;for(int i=1;i<=n;i++)//前綴和for(int j=1;j<=m;j++)a[getid(i,j)]+=a[getid(i-1,j)]+a[getid(i,j-1)]-a[getid(i-1,j-1)];scanf("%d",&t);while(t--){int x,y,xx,yy;scanf("%d%d%d%d",&x,&y,&xx,&yy);int temp1=(xx-x+1)*(yy-y+1);//區(qū)間大小int temp2=a[getid(xx,yy)]-a[getid(xx,y-1)]-a[getid(x-1,yy)]+a[getid(x-1,y-1)];//前綴和大小if(temp1==temp2)cout<<"YES"<<endl;elsecout<<"NO"<<endl; }}return 0; }

?

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的HDU - 6514 Monitor(二维差分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。