题目大意
需要支持在一个序列中插入等差数列
需要插入\(O(1)\) 最终统计答案\(O(n)\)
\(1\leq n\leq 1e7\)
Sol
对于一个序列如下:
| 0 | 0 | 4 | 6 | 8 | 10 | 12 | 0 | 0 |
|---|
我们将其进行一次差分,可以得到:
| 0 | 0 | 4 | 2 | 2 | 2 | 2 | -12 | 0 |
|---|
可以发现中间出现了一串公差,在差分一次:
| 0 | 0 | 4 | -2 | 0 | 0 | 0 | -14 | 12 |
|---|
应该可以看出来,给定的四个数 \(l\),\(r\),\(s\),\(e\)以及公差\(d=\frac{e-s}{r-l}\)
其实就是在差分数组\(d\)中将
- \(d_l\) 加 \(s\)
- \(d_{l+1}\) 加 \(d-s\)
- \(d_{r+1}\) 减 \(d+e\)
- \(d_{r+2}\) 加 \(e\)
最后进行两次差分即可
Code
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;const int N = 1e7+10;int n , m;
LL sum1[N] , sum2[N];int main() {scanf("%d%d" , &n , &m);for(int i = 1 ; i <= m ; i ++) {LL l , r , s , e , d = 0;scanf("%lld%lld%lld%lld" , &l , &r , &s , &e);if(r != l) d = (e-s)/(r-l);sum1[l] += s; sum1[l+1] += d-s;sum1[r+1]-=d+e; sum1[r+2]+=e;}LL res1 = 0 , res2 = 0;for(int i = 1 ; i <= n ; i ++) {sum1[i] += sum1[i-1];sum2[i] = sum2[i-1] + sum1[i];res1 ^= sum2[i];if(sum2[i] > res2) res2 = sum2[i];}printf("%lld %lld\n" , res1 , res2);return 0;
}