title: 牛客练习赛34 - C little w and Segment Coverage(思维、树状数组)
date: -12-15 16:36:55
tags: [树状数组,思维]
categories: ACM
题目链接
题目描述
小w有m条线段，编号为1到m。
用这些线段覆盖数轴上的n个点，编号为1到n。
第i条线段覆盖数轴上的区间是L[i]，R[i]。
覆盖的区间可能会有重叠，而且不保证m条线段一定能覆盖所有n个点。
现在小w不小心丢失了一条线段，请问丢失哪条线段，使数轴上没被覆盖到的点的个数尽可能少，请输出丢失的线段的编号和没被覆盖到的点的个数。如果有多条线段符合要求，请输出编号最大线段的编号（编号为1到m）。
输入描述:
第一行包括两个正整数n，m(1≤n，m≤10^5)。
接下来m行，每行包括两个正整数L[i]，R[i](1≤L[i]≤R[i]≤n)。
输出描述:
输出一行，包括两个整数a b。
a表示丢失的线段的编号。
b表示丢失了第a条线段后，没被覆盖到的点的个数。
输入
5 31 34 53 4
输出
3 0
说明
若丢失第1条线段，1和2没被线段覆盖到。
若丢失第2条线段，5没被线段覆盖到。
若丢失第3条线段，所有点都被线段覆盖到了。
输入
6 21 24 5
输出
2 4
说明
若丢失第1条线段，1，2，3，6没被线段覆盖到。
若丢失第2条线段，3，4，5，6没被线段覆盖到。
AC
删除一条边影响到的是这个区间内，只被覆盖一次的点
问题是怎么对着M条边进行处理，如果是暴力真个区间都加1可能会超时，线段树能写但是麻烦，这里有个trick：
将区间的左端点+1，右端点的下一个点-1。这样对只每个线段的端点处理然后对于每个点，它被覆盖的次数 = 左端点覆盖的次数 - 以左端点结束的次数最后遍历每个线段，找到影响最少的线段，记得加上原来就没有覆盖的点可以用树状数组维护前缀和，也可以一个for
#include <iostream>#include <stdio.h>#include <map>#include <unordered_map>#include <vector>#include <set>#include <queue>#include <stack>#include <cstring>#include <cmath>#include <iomanip>#include <algorithm>#define N 100005#define lowbit(x) (x & (-x))#define mem(a, b) memset(a, b, sizeof(a))#define REP(i, n) for (int i = 1; i <= (n); ++i)#define rep(i, n) for (int i = 0; i < (n); ++i)typedef long long LL;using namespace std;int num[N], cnt, c[N], n, m;struct ac{int l, r;}a[N];void update(int x) {while (x <= n) {c[x] += 1;x += lowbit(x);}}int getsum(int x) {int sum = 0;while (x > 0) {sum += c[x];x -= lowbit(x);}return sum;}int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endifwhile (scanf("%d %d", &n, &m) != EOF) {mem(num, 0);mem(c, 0);cnt = 0;REP(i, m) {scanf("%d %d", &a[i].l, &a[i].r);num[a[i].l] ++;num[a[i].r + 1] --;}REP(i, n) {num[i] += num[i - 1];if (num[i] == 0) cnt ++;if (num[i] == 1) update(i);// if (num[i] == 1) c[i] = 1;// c[i] += c[i - 1];}int ans = 1e9, flag;REP(i, m) {// int cha = c[a[i].r] - c[a[i].l - 1];int cha = getsum(a[i].r) - getsum(a[i].l - 1);if (cha <= ans) {flag = i;ans = cha;}}ans += cnt;printf("%d %d\n", flag, ans);}return 0;}
如果觉得《牛客练习赛34 - C little w and Segment Coverage(思维 树状数组)》对你有帮助，请点赞、收藏，并留下你的观点哦！
