三步必杀

wjh15101051's space

卧薪尝胆，厚积薄发。

三步必杀

Date: Sun Oct 28 16:19:51 CST 2018

In Category: NoCategory

Description：

区间加等差数列，最后询问每个位置的值。

$1\leqslant n\leqslant 10^7$

Solution：

一眼差分，设公差为 $k$ ，可以看成先区间加一个 $s-k$ ，然后每个位置分别加 $k,2k,3k,\dots$ ，这个可以看成先把差分数组区间加，这个可以查分差分数组，最后加一下就行了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 10000010

typedef long long ll;

ll c[MAXN];

ll t[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int l,r;

	ll s,e;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%lld%lld",&l,&r,&s,&e);

		ll p = (e - s) / (r - l);

		c[l] += s - p;c[r + 1] -= e;

		t[l] += p;t[r + 1] -= p;

	}

	ll cur = 0;

	for(int i = 1;i <= n;++i)

	{

		c[i] += c[i - 1];

		cur += t[i];

		c[i] += cur;

	}

	ll ans1 = 0,ans2 = 0;

	for(int i = 1;i <= n;++i)

	{

		ans1 ^= c[i];

		ans2 = max(ans2,c[i]);

	}

	cout << ans1 << " " << ans2 << endl;

	return 0;

}

In tag: 技巧-差分

wjh15101051