本文主要是介绍hdu5372（2015多校7）--Segment Game（树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：存在一个横轴，有n此操作，0代表在横轴上新增加一条边，1代表删除1条边，其中0 x代表在从x位置开始增加一条边，当第i次加边时，边的长度为i，1 x代表删除第x次加的边。问每当新加入一条边是，这条边能完整的包含几条边。
为什么当时没做这个题，，，已经泪奔，，，
问的是新加的那条边能覆盖多少条边，统计已加入的边的左端点大于或等于新边左端点的个数x，统计已加入的边的右端点大于新边的右端点的个数y。那么新编能覆盖的边也就是x-y，，，，，
用树状数组分别维护一左端点的个数和右端点的个数。然后计算。因为端点位置比较大，所以先对所有端点离散化一下，然后直接统计。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define maxn 200010
struct node{int k , s , e ;
}p[maxn] , que[maxn] ;
int n , m , cnt ;
int c[maxn<<1][2] ;
int a[maxn<<1] ;
int search1(int x) {int low = 1 , mid , high = m ;while( low <= high ) {mid = (low + high) / 2 ;if( a[mid] == x ) return mid ;if( a[mid] < x ) low = mid + 1 ;else high = mid - 1 ;}
}
int lowbit(int x) {return x & -x ;
}
void add(int i,int j,int k) {while( i ) {c[i][j] += k ;i -= lowbit(i) ;}
}
int sum(int i,int j) {int ans = 0 ;while( i <= m ) {ans += c[i][j] ;i += lowbit(i) ;}return ans ;
}
int main() {int step = 0 ;int i , j ;while( scanf("%d", &n) != EOF ) {cnt = m = 1 ;for(i = 1 ; i <= n ; i++) {scanf("%d %d", &p[i].k, &p[i].s) ;if( !p[i].k ) {a[m++] = p[i].s ;a[m++] = p[i].e = p[i].s+cnt ;cnt++ ;}}sort(a+1,a+m) ;m = unique(a+1,a+m) - a ;for(i = 1 ; i <= n ; i++) {if( p[i].k ) continue ;p[i].s = search1(p[i].s) ;p[i].e = search1(p[i].e) ;}memset(c,0,sizeof(c)) ;cnt = 1 ;printf("Case #%d:\n", ++step) ;for(i = 1 ; i <= n ; i++) {if( p[i].k ) {add(que[ p[i].s ].s,0,-1 ) ;add(que[ p[i].s ].e,1,-1 ) ;}else{que[cnt++] = p[i] ;printf("%d\n", sum(p[i].s,0) - sum(p[i].e+1,1) ) ;add(p[i].s,0,1) ;add(p[i].e,1,1) ;}}}return 0 ;
}
这篇关于hdu5372（2015多校7）--Segment Game（树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
