区间合并 (差分处理)
模拟n == 1;
四个角初始:(1,-1,-1,1)
-1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0 -1
从 0开始出发到本行-1
-1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 1 1 1 1 -1
-1关键点差分为0,继续到下一个-1
0 -1 1
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
到关键点1;
0 0 0 0 0 1
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
处理点1为0;
0 0 0 0 0 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
0 1 1 1 1 0
#include<iostream>
using namespace std;
const int N=15;
int p[N*5][N*10];
int n;
int main(){
cin>>n;
while(n--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
x1++,y1++;
p[x1][y1]+=1;
p[x2+1][y1]-=1;
p[x1][y2+1]-=1;
p[x2+1][y2+1]+=1;
}
int ans=0;
for(int i=1;i<=51;i++)
for(int j=1;j<=101;j++){
p[i][j]+=p[i-1][j]+p[i][j-1]-p[i-1][j-1];
if(p[i][j]) ans++;
}
cout<<ans;
return 0;
}