点数很多,坐标值很大,然后离散化一下用一个点表示一小块的面积对应的颜色,然后更新的时候一块一块更新,查询的时候一块一块查询
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = ;
const int maxm = ;
const int mod = 1e9+;
using namespace std; int n, m;
int T, tol;
struct Node {
int x1, y1;
int x2, y2;
int w;
};
Node node[maxn];
int X[maxn];
int Y[maxn];
int maps[maxn][maxn];
int ans[maxn]; void init() {
memset(X, , sizeof X);
memset(Y, , sizeof Y);
memset(ans, , sizeof ans);
memset(node, , sizeof node);
memset(maps, , sizeof maps);
} int main() {
int cas = ;
while(scanf("%d%d", &n, &m), n||m) {
if(cas != ) printf("\n");
init();
int q;
scanf("%d", &q);
int cx = , cy = ;
int x1, y1, x2, y2, w;
int mw = ;
for(int i=; i<=q; i++) {
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &w);
X[cx++] = x1, Y[cy++] = y1;
X[cx++] = x2, Y[cy++] = y2;
node[i].x1 = x1, node[i].y1 = y1;
node[i].x2 = x2, node[i].y2 = y2;
node[i].w = w;
mw = max(mw, w);
}
sort(X, X+cx);
sort(Y, Y+cy);
cx = unique(X, X+cx) - X;
cy = unique(Y, Y+cy) - Y;
// for(int i=0; i<cx; i++) printf("%d%c", X[i], i==cx-1 ? '\n' : ' ');
// for(int i=0; i<cy; i++) printf("%d%c", Y[i], i==cy-1 ? '\n' : ' ');
// printf("\n");
for(int i=; i<=q; i++) {
x1 = lower_bound(X, X+cx, node[i].x1) - X;
x2 = lower_bound(X, X+cx, node[i].x2) - X;
y1 = lower_bound(Y, Y+cy, node[i].y1) - Y;
y2 = lower_bound(Y, Y+cy, node[i].y2) - Y;
// printf("%d %d %d %d\n", x1, y1, x2, y2);
for(int x=x1; x<x2; x++) {
for(int y=y1; y<y2; y++) {
maps[x][y] = node[i].w;
}
}
}
// printf("\n");
// for(int i=0; i<cx; i++) for(int j=0; j<cy; j++) printf("%d%c", maps[i][j], j==cy-1 ? '\n' : ' ');
for(int i=; i<cx; i++) {
for(int j=; j<cy; j++) {
if(!maps[i][j]) continue;
w = maps[i][j];
int area = (X[i+] - X[i]) * (Y[j+] - Y[j]);
ans[w] += area;
}
}
tol = ;
printf("Case %d:\n", cas++);
for(int i=; i<=mw; i++) {
if(ans[i]) {
printf("%d %d\n", i, ans[i]);
tol++;
}
}
if(tol <= ) printf("There is %d color left on the wall.\n", tol);
else printf("There are %d colors left on the wall.\n", tol);
}
return ;
}