牛客NOIP暑期七天营-普及组2-D线段
线段
https://ac.nowcoder.com/acm/contest/926/D
题目大意:已知n条线段的左右端点与颜色,现有m个循环,问区间中被完全包含的线段有多少种颜色?
36分,普及组该拿的分数:对于每个区间,暴力枚举每条线段,统计颜色数——只有颜色恰好加到1,才算增加一种颜色的线段。
for(i=1; i<=m; i++){ ans = 0; for(j=1; j<=n; j++){ if(x[i]<=l[j] && r[j]<=y[i]){ if(++f[c[j]] == 1) ans++; } } printf("%d\n", ans); for(j=1; j<=n; j++){ if(x[i]<=l[j] && r[j]<=y[i]) --f[c[j]]; } }
满分:树状数组,感觉超过普及组范围了。
这是离线做法,将线段和循环一起排序;保存在同一个结构体,注意标记好,便于后面区分。如线段有颜色c,询问有编号i。
贪心1:线段问题,通常都按某端点排序,这里也不例外。
按照右端点排序,询问排在线段后面。这样的好处是,查询的时候不需要管右端点了,查询区间内左端点的数量就是覆盖的线段数量。因为之前的线段右端点都小,要么在区间内,左端点也在就算;要么不在区间内,左端点肯定也不在。(颜色各不相同的数据提示统计线段数)
贪心2:同一种颜色只算1次,对于“排在前面”的两根同色线段,左端点越靠右越好,靠左边的可以删除。对于后面的询问来说,如果左边的被包含,右边的也必会被包含,右边的做代表就可以了。开个数组记录每种颜色最靠右的位置,如果出现更靠右的,删除之前的左端点,增加当前的左端点。
#include <bits/stdc++.h> #define N 1000005 using namespace std; int n, m, i, j, k, l, r, c; int s[N], f[N], ans[N>>2]; struct LR{ int l, r, c, i; bool operator < (const LR &A) const{ if(r != A.r) return r < A.r; return c > A.c; } } d[N*5]; void jia(int i, int x){ while(i < N) s[i] += x, i += -i&i; } int he(int i){ int c = 0; while(i) c += s[i], i -= -i&i; return c; } int main(){ scanf("%d%d", &n, &m); for(i=1; i<=n; i++){ scanf("%d%d%d", &d[i].l, &d[i].r, &d[i].c); } for(n+=m; i<=n; i++){ scanf("%d%d", &d[i].l, &d[i].r); d[i].i = i + m - n; } sort(d+1, d+n+1); for(i=1; i<=n; i++){ l = d[i].l, r = d[i].r, c = d[i].c, j = d[i].i; if(j){ ans[j] = he(r) - he(l-1); } else{ if(!f[c]) jia(f[c]=l, 1); else if(l > f[c]){ jia(f[c], -1); jia(f[c]=l, 1); } } } for(i=1; i<=m; i++){ printf("%d\n", ans[i]); } return 0; }