题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3577
代码风格:http://www.notonlysuccess.com/index.php/segment-tree-complete/
题目大意:买火车票问题,一辆火车最多有1000000个站点,站点最多能容下Q个人,一共有k个乘客
每个乘客需要从第a站坐到第b站,所以要保证火车到任何站台,人数都不会超过Q个人,让我看输出哪几个乘客能上车
算法:线段树 离散化
思路:求[a, b]区间的最小值是不是为零
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define lson l, m, rt << 1 #define rson m+1, r, rt << 1 | 1 #define mid int m = (l+r) >> 1 int mn[4000000], cover[4000000], w[454545], ri[223232], li[232323]; void build(int l, int r, int rt, int k) { mn[rt] = k; if(l == r) return ; mid ; build(lson, k); build(rson, k); } int minz(int a, int b) { return a < b ? a : b; } void PushUp(int rt) { mn[rt] = minz(mn[rt << 1], mn[rt << 1 | 1]); } void PushDown(int rt) { cover[rt << 1] += cover[rt]; cover[rt << 1 | 1] += cover[rt]; mn[rt << 1] -= cover[rt]; mn[rt << 1 | 1] -= cover[rt]; cover[rt] = 0; } void update(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { cover[rt] ++; mn[rt] --; return ; } mid ; cover[rt << 1] += cover[rt]; cover[rt << 1 | 1] += cover[rt]; mn[rt << 1] -= cover[rt]; mn[rt << 1 | 1] -= cover[rt]; cover[rt] = 0; if(L <= m) update(L, R, lson); if(m < R) update(L, R, rson); mn[rt] = minz(mn[rt << 1], mn[rt << 1 | 1]); } int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) { if(mn[rt] != 0) return 1; else return 0; } mid ; cover[rt << 1] += cover[rt]; cover[rt << 1 | 1] += cover[rt]; mn[rt << 1] -= cover[rt]; mn[rt << 1 | 1] -= cover[rt]; cover[rt] = 0; int ret1=1, ret2=1; if(L <= m) ret1 = query(L, R, lson); if(m < R) ret2 = query(L, R, rson); return ret1 & ret2; } int bin(int key, int n) { int l = 0, r = n; while(l <= r) { mid ; if(w[m] == key) return m; if(key < w[m]) r = m - 1; else l = m+1; } return -1; } int main() { int n, m; int T; scanf("%d", &T); int ica = 1; while(T --) { printf("Case %d:\n", ica ++); memset(cover, 0, sizeof(cover)); int i; int maxn = 0; scanf("%d%d", &n, &m); int k = 0; for(i = 1; i <= m; i ++) { scanf("%d%d", &li[i], &ri[i]); w[k ++] = li[i]; w[k ++] = ri[i]; } sort(w, w+k); int u = 1; for(i = 1; i < k; i ++) if(w[i] != w[i-1]) w[u ++] = w[i]; build(0, u-1, 1, n); for(i = 1; i <= m; i ++) { int ll = bin(li[i], u-1 ); int rr = bin(ri[i], u-1 )-1; int flag = query(ll, rr, 0, u-2, 1); if(flag && ll <= rr) { update(ll, rr, 0, u-2, 1); printf("%d ", i); } } printf("\n\n"); }return 0; }