题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3577 ，普通的线段树区间更新题目，较简单。
相当于一个区间覆盖问题，有一点要注意的就是叶子节点是一个长度为1的区间，而不是一个离散的点，两种叶子节点的具体区别我在这篇博客里提到过。
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF INT_MAX
#define lson l , m , rt << 1
#define rson m , r , rt << 1 | 1
const int MOD = 10000007;
const int maxn = 1000000 + 5;
const int N = 100000 + 5;
int cnt[maxn << 2] , col[maxn << 2];
int ans[N];
void build()
{
memset(cnt , 0 , sizeof(cnt));
memset(ans , 0 , sizeof(ans));
memset(col , 0 , sizeof(col));
}
void PushUp(int rt)
{
cnt[rt] = max(cnt[rt << 1] , cnt[rt << 1 | 1]);
}
void PushDown(int rt)
{
if(col[rt]) {
col[rt << 1] += col[rt];
col[rt << 1 | 1] += col[rt];
cnt[rt << 1] += col[rt];
cnt[rt << 1 | 1] += col[rt];
col[rt] = 0;
}
}
void update(int L , int R , int l , int r , int rt)
{
if(L <= l && R >= r) {
cnt[rt]++;
col[rt]++;
return;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L >= m)
update(L , R , rson);
else if(R <= m)
update(L , R , lson);
else {
update(L , R , lson);
update(L , R , rson);
}
PushUp(rt);
}
bool query(int L , int R , int k , int l , int r , int rt)
{
if(L <= l && R >= r) {
return cnt[rt] < k;
}
PushDown(rt);
int m = (l + r) >> 1;
if(L >= m)
return query(L , R , k , rson);
else if(R <= m)
return query(L , R , k , lson);
else
return query(L , R , k , lson) && query(L , R , k , rson);
}
int main()
{
int T , i , n , m , k , a , b;
cin >> T;
for(int j = 1 ; j <= T ; j++)
{
build();
scanf("%d %d" , &k , &m);
for(i = 1 ; i <= m ; i++) {
scanf("%d %d" , &a , &b);
if(query(a , b , k , 1 , maxn , 1)) {
update(a , b , 1 , maxn , 1);
ans[i]++;
}
}
printf("Case %d:\n" , j);
for(i = 1 ; i <= m ; i++)
if(ans[i])
printf("%d " , i);
printf("\n\n");
}
return 0;
}
提供几组测试数据：
4
3 6
1 6
1 6
3 4
1 5
1 2
2 4
3 10
2 4
4 6
6 8
2 8
1 8
1 2
1 10
2 9
3 7
9 10
3 10
4 5
5 6
6 7
7 8
9 10
1 4
1 10
2 9
4 6
3 8
3 8
4 6
6 8
9 10
1 4
1 10
2 9
4 6
3 8
Case 1:
1 2 3 5
Case 2:
1 2 3 4 5 6 10
Case 3:
1 2 3 4 5 6 7 8
Case 4:
1 2 3 4 5 6