AT1011题解

Grisses · 2022-01-27 13:30:45 · 题解

题面

这题是一道 差分 的模板题。

差分

差分是一种可以在 O(1) 的时间复杂度内完成区间修改的东西。

对于一个数组 a_1,a_2 \cdots a_n，它的差分数组是 a_1-0,a_2-a_1\cdots a_n-a_{n-1}。

如果我们需要将 [l,r) 区间全部加上 x，那么我们只需要将差分数组 b 的 b_l 加上 x，将 b_r 减去 k 即可。

代码：

  #include<bits/stdc++.h>
  using namespace std;
  int n,a,b,ans,x[1000005];//x是差分数组
  signed main()
  {
      scanf("%d",&n);
      while(n--){
          scanf("%d%d",&a,&b);
          x[a]++;
          x[b+1]--;//修改
      }
      ans=x[0];
      for(int i=1;i<=1000000;i++)x[i]+=x[i-1],ans=max(ans,x[i]);//求值，去max
      printf("%d\n",ans);
      return 0;
  }