首页 > 代码库 > bzoj2811 [Apio2012]Guard
bzoj2811 [Apio2012]Guard
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2811
【题解】
首先我们先把没看到忍者的段去掉,可以用线段树做。
如果剩下的就是K,那么特判即可。
我们可以把包含关系去掉然后对于剩下的区间,x单增,y单增。
否则的话,我们有一个结论(挺显然的):只有每个区间的右段点才能成为答案。
我们贪心地填肯定是填右端点。
所以我们判断如果右端点填到了前一个位置是否可行即可,如果不可行那么必须填右端点。
二分出这个位置所覆盖的区间(我们钦定填了这里)
然后我们维护fp[i]表示左边i个区间最少填多少,fs[i]表示右边i个区间最少填多少(前缀、后缀)
然后我们判断fp[l]+fs[r]+1是否大于K即可,如果大于,说明一定要填。
# include <stdio.h> # include <string.h> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, K, m; int x[M]; struct guard { int l, r; guard() {} guard(int l, int r) : l(l), r(r) {} friend bool operator < (guard a, guard b) { return a.l < b.l || (a.l == b.l && a.r > b.r); } }a[M], o[M]; int on; bool del[M]; int new_id[M], idx, old_id[M]; int pre[M], nxt[M]; int fp[M], fs[M]; namespace SMT { int w[M]; # define ls (x<<1) # define rs (x<<1|1) inline void edt(int x, int l, int r, int L, int R) { if(w[x]) return; if(L <= l && r <= R) { w[x] = 1; return ; } int mid = l+r>>1; if(L <= mid) edt(ls, l, mid, L, R); if(R > mid) edt(rs, mid+1, r, L, R); } inline int query(int x, int l, int r, int pos) { if(w[x]) return 1; if(l == r) return 0; int mid = l+r>>1; if(pos <= mid) return query(ls, l, mid, pos); else return query(rs, mid+1, r, pos); } # undef ls # undef rs } int main() { scanf("%d%d%d", &n, &K, &m); for (int i=1; i<=m; ++i) scanf("%d%d%d", &a[i].l, &a[i].r, x+i); for (int i=1; i<=m; ++i) if(x[i] == 0) SMT::edt(1, 1, n, a[i].l, a[i].r); for (int i=1; i<=n; ++i) { if(SMT::query(1, 1, n, i) == 0) { new_id[i] = ++idx, old_id[idx] = i; // printf("i = %d, idx = %d\n", i, idx); } else del[i] = 1; } if(idx == K) { for (int i=1; i<=n; ++i) if(!del[i]) printf("%d\n", i); return 0; } for (int i=1; i<=n; ++i) { if(!del[i]) pre[i] = i; else pre[i] = pre[i-1]; } for (int i=n; i; --i) { if(!del[i]) nxt[i] = i; else nxt[i] = nxt[i+1]; } for (int i=1; i<=m; ++i) { int nl = nxt[a[i].l], nr = pre[a[i].r]; if(nl <= nr) o[++on] = guard(new_id[nl], new_id[nr]); } sort(o+1, o+on+1); m = 0; for (int i=1; i<=on; ++i) { while(m && o[i].l >= a[m].l && o[i].r <= a[m].r) --m; a[++m] = o[i]; } // for (int i=1; i<=m; ++i) // printf("%d %d\n", a[i].l, a[i].r); int cur = 0; for (int i=1; i<=m; ++i) if(a[i].l > cur) fp[i] = fp[i-1] + 1, cur = a[i].r; else fp[i] = fp[i-1]; cur = 1e9; for (int i=m; i; --i) if(a[i].r < cur) fs[i] = fs[i+1] + 1, cur = a[i].l; else fs[i] = fs[i+1]; bool have_ans = 0; for (int i=1, x, l, r, ans1, ans2; i<=m; ++i) { if(fp[i] != fp[i-1]+1) continue; if(a[i].l == a[i].r) { have_ans = 1; // printf("=%d\n", a[i].r); printf("%d\n", old_id[a[i].r]); continue; } // 考察每个区间的右端点是否可行 x = a[i].r-1; l = 1, r = i-1, ans1 = 0; while(1) { if(r-l<=3) { for (int j=r; j>=l; --j) if(a[j].r < x) { ans1 = j; break; } break; } int mid = l+r>>1; if(a[mid].r < x) l = mid; else r = mid; } l = i+1, r = m, ans2 = m+1; while(1) { if(r-l<=3) { for (int j=l; j<=r; ++j) if(a[j].l > x) { ans2 = j; break; } break; } int mid = l+r>>1; if(a[mid].l > x) r = mid; else l = mid; } // printf("%d %d\n", ans1, ans2); if(fp[ans1] + fs[ans2] + 1 > K) { // printf("=%d\n", a[i].r); printf("%d\n", old_id[a[i].r]); have_ans = 1; } } if(!have_ans) puts("-1"); return 0; }
bzoj2811 [Apio2012]Guard
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。