题目链接：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
转载于:https://www.cnblogs.com/H-Vking/p/4297275.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109543.html原文链接：https://javaforall.net
