洛谷 P4231 三步必杀

题目链接

Solution

\(n,m≤10^5\) 考虑差分（设公差为 \(d\) ）：\(a[l]+=s, a[r+1]-=s+(r-l)*d\)，中间 \((l,r]\) 部分区间加 \(d\)，使当前位置的值等于其前缀和。可以使用线段树或者树状数组维护。

\(n≤10^7\) 再次使用差分，维护区间加法：\(b[l+1]+=d, b[r+1]-=d\)，使 \(ans[i]=sum_b[i]+a[i]+ans[i-1]\)。注意内存限制。

Code

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int N = 10000010;
 int n, m;
 long long a[N], b[N], l, r, s, e, d, a1 = 0, a2 = 0, n1 = 0, n2 = 0;
 
 int main()
 {
     scanf("%d%d", &n, &m);
     memset(a, 0, sizeof(a)), memset(b, 0, sizeof(b));
     for(int i = 1; i <= m; i++)
     {
         scanf("%lld%lld%lld%lld", &l, &r, &s, &e);
         d = (e - s) / (r - l), b[l + 1] += d, b[r + 1] -= d;
         a[l] += s, a[r + 1] -= s + (r - l) * d;
     }
     for(int i = 1; i <= n; i++)
     {
         n1 += b[i], n2 += a[i] + n1;
         a1 ^= n2; if(a2 < n2) a2 = n2;
     }
     printf("%lld %lld", a1, a2);
     return 0;
 }

洛谷 P4231 三步必杀

原文：https://www.cnblogs.com/Andy-park/p/12667939.html