这道题就是区间加一个等差数列,然后最后求每一个数的值。
O(n)做法:二阶差分。
其实就是差分两遍。举个例子 0 0 0 0 0 0 0,变成了 0 2 4 6 8 0 0。第一遍差分:0 2 2 2 2 -8 0,然后在这个差分数组上在进行差分,得到 0 2 0 0 0 10 8,完事。
我们在用通项搞一遍:等差数列的首项是s,末项是e,公差是d,则
最终的样子:0 s s+d s+2d e 0 0,
第一遍差分:0 s d d d -e 0,
第二遍差分:0 s d-s 0 0 -e-d e 。
所以我们只用维护四个值就行了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e7 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, m;
ll dif[maxn], sum = , Max = -INF; int main()
{
n = read(); m = read();
for(int i = ; i <= m; ++i)
{
int L = read(), R = read(), s = read(), e = read();
int d = (e - s) / (R - L);
dif[L] += s; dif[L + ] += d - s;
dif[R + ] -= e + d; dif[R + ] += e;
}
for(int i = ; i <= n; ++i) dif[i] = dif[i - ] + dif[i];
for(int i = ; i <= n; ++i)
{
dif[i] = dif[i - ] + dif[i];
sum ^= dif[i];
Max = max(Max, dif[i]);
}
write(sum); space; write(Max); enter;
return ;
}