CodeForces 1000C如何用差分算法高效计算区间线段覆盖的覆盖点数？

本文共计702个文字，预计阅读时间需要3分钟。

题目：有n个线段，覆盖[l+i, r+i]，最后依赖输出覆盖层数为1的点的个数。

思路：区间线段覆盖问题，可以使用树状数组或线段树解决。具体做法如下：

1. 使用树状数组或线段树存储每个点的覆盖次数。

2.遍历线段，对每个线段进行更新。

3.遍历所有点，找出覆盖次数为1的点，统计个数。

代码示例（使用树状数组）：

python

def update(arr, index, val, n): while index <=n: arr[index] +=val index +=index & -index

def query(arr, index): res=0 while index > 0: res +=arr[index] index -=index & -index return res

def solve(n, intervals): max_val=max(r for _, r in intervals) arr=[0] * (max_val + 1) count=0

for l, r in intervals: update(arr, l, 1, max_val) update(arr, r + 1, -1, max_val)

for i in range(1, max_val + 1): if query(arr, i)==1: count +=1

return count

测试n=5intervals=[(1, 2), (3, 4), (2, 5), (1, 3), (4, 5)]print(solve(n, intervals))

以上代码中，`update` 函数用于更新树状数组，`query` 函数用于查询树状数组中某个点的值，`solve` 函数用于解决题目。

codeforces.com/problemset/problem/1000/C

题意：

有n个线段，覆盖[l_i,r_i]，最后依次输出覆盖层数为1~n的点的个数。

思路：

区间线段覆盖问题，第一反应树状数组、线段树，看了看数据规模，开不了这么大的空间。

只能用差分了

代码如下：

1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <math.h> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 #define Bug cout<<"---------------------"<<endl 17 const int maxn=2*1e5+10; 18 using namespace std; 19 20 pair<LL,int> p[2*maxn];//注意要开两倍空间 21 LL ans[maxn]; 22 23 int main() 24 { 25 int n; 26 scanf("%d",&n); 27 int cnt = 0; 28 for(int i = 0;i < n;i++) 29 { 30 LL l,r;//注意是long long 31 scanf("%lld %lld",&l,&r); 32 p[i*2] = make_pair(l,1); 33 p[i*2+1] = make_pair(r+1,-1); 34 } 35 sort(p,p+n*2); 36 LL now = 0;//当前点的覆盖层数 37 for(int i = 0;i < n*2;i++) 38 { 39 now += p[i].second; 40 if(p[i].first == p[i+1].first) continue;//叠加差分 41 ans[now] += p[i+1].first - p[i].first; 42 } 43 for(int i=1;i<=n;i++) 44 printf("%lld ",ans[i]); 45 return 0; 46 }