题意：

给n个线段，我们需要保证每个点(只考虑整数点)的重复不超过k次，让我们找出要剔除的线段，并输出这些线段的位置。

D1. Too Many Segments (easy version)

思路：

没有思路，要说思路就是暴力！（哈哈）真的是纯暴力

就是将一个线段分别以每个整数点为起点，右端点为终点，分为len个线段，都存起来。并且按照新的左端点升序，左端点相同线段长度降序排序。然后遍历一遍所有的线段，如果有不符合条件的就把这个子线段所在的原线段删掉【因为是按照长度降序排序的，所以贪心删掉最长的】。然后再存一下删掉线段的序号即可。 #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <set> #include <stack> #include <list> #include <map> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxN = 2e5 + 5; struct node{ int l, r, len, id; friend bool operator < (node n1, node n2) { if(n1.l == n2.l) return n1.len > n2.len; return n1.l < n2.l; } }info[maxN]; int num[maxN] ,vis[maxN], ans[maxN]; void init() { memset(num, 0, sizeof(num)); memset(vis, 0, sizeof(vis)); memset(ans, 0, sizeof(ans)); } int main() { int n, k; while(~scanf("%d%d", &n, &k)) { int cnt = 0; init(); for(int i = 1; i <= n; i ++ ) { int a, b; scanf("%d%d", &a, &b); for(int j = a; j <= b; j ++ ) { info[cnt ++ ] = node{j, b, b - j + 1, i}; num[j] ++; } } sort(info, info + cnt); int pos = 0; for(int i = 0; i < cnt; i ++ ) { if(vis[info[i].id]) continue; if(num[info[i].l] > k) { for(int j = info[i].l; j <= info[i].r; j ++ ) num[j] -- ; vis[info[i].id] = 1; ans[pos ++ ] = info[i].id; } } sort(ans, ans + pos); printf("%d\n", pos); for(int i = 0; i < pos; i ++ ) printf("%d%c", ans[i], " \n"[i == pos - 1]); } return 0; }

D2. Too Many Segments (hard version)

思路

记录下输入的最左和最右的端点，跑for( i = L, i <= R )循环，以 i 为右端点，将左端点在 i 之前的线段都 insert，然后我们从这些线段里剔除右端点最靠右的几个，使得该点的出现频率 == k.【这里用到了贪心的思想，越往右，覆盖的点越多】在剔除线段之前，我们需要将右端点小于 i 的线段踢出去，因为前边的已经满足出现频率在 k 之内了【维护整数点的频率】用到了树状数组的区间更新，单点查询。【差分思想】

差分_树状数组

D[maxN]: D[ i ]表示 A[ i ] - A[ i - 1 ]求A[ i ] = D[ i ] + D[ i - 1 ] + D[ i - 2 ] + … + D[ 1 ] #include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <cstring> #include <string> #include <vector> #include <set> #include <stack> #include <list> #include <map> #define INF 0x3f3f3f3f #define lowbit(x) x & (- x) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxN = 2e5 + 5; int n, k; struct node{ int l, r, id; node(int a = 0, int b = 0, int c = 0) : l(a), r(b), id(c) {} friend bool operator < (node n1, node n2) { return n1.r > n2.r ; } }info[maxN]; bool cmp(node n1, node n2) { return n1.l < n2.l; } int L, R; int D[maxN]; void add(int x, int val) { while(x <= R) { D[x] += val; x += lowbit(x); } } int getsum(int x) { int ans = 0; while(x > 0) { ans += D[x]; x -= lowbit(x); } return ans; } int main() { scanf("%d%d", &n, &k); L = INF, R = 0; for(int i = 1; i <= n; i ++ ) { scanf("%d%d", &info[i].l, &info[i].r); info[i].id = i; L = min(L, info[i].l); R = max(R, info[i].r); } for(int i = 1; i <= n; i ++ ) { add(info[i].l, 1); add(info[i].r + 1, -1); } sort(info + 1, info + n + 1, cmp); multiset<node>st; set<int>ans; int pos = 1; for(int i = L; i <= R; i ++ ) { if(getsum(i) <= k) continue; while(info[pos].l <= i && pos <= n) { st.insert(info[pos]); pos ++; } while(!st.empty() && (*st.rbegin()).r < i) st.erase(*st.rbegin()); while(st.size() > k) { node tmp = *st.begin(); ans.insert(tmp.id); st.erase(st.begin()); add(tmp.l, -1); add(tmp.r + 1, 1); } } int cnt = ans.size(); printf("%d\n", cnt); while(!ans.empty()) { int tmp = *ans.begin(); printf("%d ", tmp); ans.erase(tmp); } printf("\n"); return 0; }