题目大意是说给你N个矩形，让你求被覆盖k次以上的点的总个数(x,y<1e9)
首先这个题有一个转化，吧每个矩形的x2,y2+1这样就转化为了求N个矩形被覆盖k次以上的区域的面积
由于坐标很大，首先考虑的就是将坐标离散化，然后建立线段树tree[][K]，表示x的某个区间被覆盖了K次（大于K次算K次）的实际长度，在计算时把矩形转化为一系列横线段（就是说将一个矩形拆开为两条线段，下面的标记为1,上面的标记为-1（这里的标记很有技巧）），然后将这些线段按照y值的从小到达排序（y值相同的按照标记为-1的排在前，为1的排在后）
然后考虑从下往上依次拿出第一条线段(x1, x2, y, flag)，将x1, x2整个区间tree[x1,x2][1]更新为x1到x2覆盖了1次的实际长度，之后每取出一条线段先计算与上一条线段的高度差，乘上整个区间被覆盖K次的总长度，便的到了当前覆盖K次的结果，然后按照当前线段的flag值更新线段树
若flag=1说明它是一条起始边，说明后面的x1,x2这个区间被覆盖的次数加1，更新线段树x1,x2区间被覆盖k次(0<k<=K)的总长+[x1, x2]的实际长度
若flag=-1说说明这是一条结束边，x1,x2这个区间的被覆盖次数应当-1,所以与上面相反，减去这个区间的实际长度即可
同时由于y相同的是先算的-1的线段，保证了这个矩形没有继续和后方的矩形继续相交，所以结果是准确的
不理解时可以按照思路画一个图模拟一下，便可以很好理解
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1e9
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T CMP_MIN(T a, T b) { return a < b; }
template<class T> T CMP_MAX(T a, T b) { return a > b; }
template<class T> T MAX(T a, T b) { return a > b ? a : b; }
template<class T> T MIN(T a, T b) { return a < b ? a : b; }
template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }
template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b; } //typedef __int64 LL;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-;
const int MOD = ; int N, K, T;
LL Hash[MAXN<<], cntHash;
int cnt[MAXN<<], len[MAXN<<][];
struct Line {
LL x1, x2, y;
int flag;
Line(){}
Line(LL _x1, LL _x2, LL _y, int _flag)
{
x1 = _x1;
x2 = _x2;
y = _y;
flag = _flag;
}
bool operator < (const Line& A)const
{
if(y != A.y) return y < A.y;
return flag < A.flag;
}
}line[MAXN<<]; int bsearch(int low, int high, int num)
{
while(low <= high)
{
int mid = (low + high) >> ;
if(Hash[mid] == num) return mid;
if(Hash[mid] > num) high = mid - ;
else low = mid + ;
}
return ;
} void buildTree(int k, int L, int R)
{
cnt[k] = ; mem0(len[k]); len[k][] = Hash[R+] - Hash[L]; if(L == R) return ; int mid = (L + R) >> ; buildTree(lson); buildTree(rson);
} void updateCur(int k, int L, int R)
{
mem0(len[k]);
if(cnt[k] >= K)
len[k][K] = Hash[R+] - Hash[L];
else if(L == R)
len[k][cnt[k]] = Hash[R+] - Hash[L];
else {
for(int i=cnt[k];i<=K;i++)
len[k][i] += len[k<<][i-cnt[k]] + len[k<<|][i-cnt[k]];
for(int i=K-cnt[k]+;i<=K;i++)
len[k][K] += len[k<<][i] + len[k<<|][i];
}
} void update(int k, int L, int R, int l, int r, int flag)
{
if(R < l || r < L) return ; if(l<=L && R<=r) { cnt[k] += flag; updateCur(k, L, R); return ; } int mid = (L + R) >> ; update(lson, l, r, flag); update(rson, l, r, flag); updateCur(k, L, R);
} void init()
{
int x1, x2, y1, y2;
scanf("%d %d", &N, &K);
for(int i=;i<=N;i++)
{
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
++ x2; ++ y2;
line[i] = Line(x1, x2, y1, );
line[i+N] = Line(x1, x2, y2, -);
Hash[i] = x1;
Hash[i+N] = x2;
}
sort(line + , line + *N + ); sort(Hash + , Hash + *N + );
cntHash = ;
for(int i = ; i <= N*; i ++ )
if(i== || Hash[i-] != Hash[i])
Hash[++cntHash] = Hash[i]; buildTree(, , cntHash-);
} int main()
{
//FOPENIN("in.txt");
scanf("%d", &T);
for(int t = ; t <= T; t ++ )
{
init();
LL ans = ;
for(int i = ; i <= * N; i ++ )
{
if(i != )
{
ans += (line[i].y - line[i-].y) * len[][K];
}
int l = bsearch(, cntHash, line[i].x1);
int r = bsearch(, cntHash, line[i].x2);
update(, , cntHash-, l, r-, line[i].flag);
} printf("Case %d: %lld\n", t, ans);
}
return ;
}