?? pku2528.cpp
字號:
#include <stdio.h>
#include <stdlib.h>
#define SZ 100010
typedef struct
{
int l;
int m;
int r;
int s;
} Node;
typedef struct
{
int l, r;
} Edge;
Node nd[SZ * 2];
Edge e[SZ];
int node_sum;
int a[SZ * 2], b[SZ * 2];
int cp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
void Creat(int s, int l, int r)
{
int m;
if (node_sum < s)
{
node_sum = s;
}
m = (l + r) / 2;
nd[s].l = a[l];
nd[s].r = a[r];
nd[s].m = a[m];
nd[s].s = 0;
if (l < r)
{
Creat(s * 2, l, m);
Creat(s * 2 + 1, m + 1, r);
}
}
int Insert(int s, int l, int r)
{
int ll, rr;
ll = 0;
rr = 0;
if (s > node_sum)
{
return 0;
}
if (nd[s].s == 1)
{
return 0;
}
if (l <= nd[s].l && r >= nd[s].r)
{
nd[s].s = 1;
return 1;
}
if (r <= nd[s].m)
{
ll = Insert(s * 2, l, r);
}
else if (l > nd[s].m)
{
rr = Insert(s * 2 + 1, l, r);
}
else
{
ll = Insert(s * 2, l, r);
rr = Insert(s * 2 + 1, l, r);
}
if (s * 2 < node_sum && nd[2 * s].s && nd[2 * s + 1].s)
{
nd[s].s = 1;
}
return ll || rr;
}
int main()
{
int T, n, i, siz, cnt;
scanf("%d", &T);
while (T--)
{
node_sum = 0;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d %d", &e[i].l, &e[i].r);
b[2 * i] = e[i].l;
b[2 * i + 1] = e[i].r;
}
qsort(b, 2 * n, sizeof(b[0]), cp);
siz = 1;
a[0] = b[0];
for (i = 1; i < 2 * n; i++)
{
if (b[i] != b[i - 1])
{
a[siz++] = b[i];
}
}
Creat(1, 0, siz - 1);
for (i = siz - 1, cnt = 0; i >= 0; i--)
{
cnt += Insert(1, e[i].l, e[i].r);
}
printf("%d\n", cnt);
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -