---

title: 牛客練習賽34 - C little w and Segment Coverage(思維、樹狀數組)
date: 2018-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 3 1 3 4 5 3 4

輸出

3 0

說明

若丟失第1條線段，1和2沒被線段覆蓋到。
若丟失第2條線段，5沒被線段覆蓋到。
若丟失第3條線段，所有點都被線段覆蓋到了。

輸入

6 2 1 2 4 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(思维、树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。