P4243 [JSOI2009]等差数列

标签：down   需要   query   printf   端点   建议   维护   tip   i+1   

好题。

我们的两种操作均是等差数列，那就来挖掘一下等差数列的性质。

那还用说，当然是相邻两项差相等啦。

发现其实就是求该序列的一个 差分序列 ，那么我们就搞出这个序列，这里令 \(s_{i}=a_{i+1}-a_{i}\) 。回头看操作一：

• 在原序列上一个区间 \([l, r]\) 加上一个等差数列。

求差分后，它就变成了：

1. 在差分数列 l-1 位置处加上首项 a ；

2. 对区间中每一项都加上公差 d ；

3. 在差分数列 r+1 位置处减去 (r-l+1)*d+a 。

再看操作二（在原数列上）：

• 求最少的划分段，使得每段均为一个等差数列。

其等价于（在差分数列上）：

• 求最少的划分段，使得每一段内的数都相等。

然鹅问题并没有变得容易。

几经思索后，我们发现只需要维护四个值即可：

• 分割区间 \([l,\ r]\) 的最少划分段；

• 分割区间 \([l,\ r)\) 的最少划分段；

• 分割区间 \((l,\ r]\) 的最少划分段；

• 分割区间 \((l,\ r)\) 的最少划分段。

为了方便，顺便维护区间左右端点的值。

那么容易推出以下 pushup 函数：

void pushup(int k, int lc, int rc){
		st(k)=st(lc), ed(k)=ed(rc);int tmp=ed(lc)==st(rc);
        l(k)=man(l(lc)+lr(rc)-tmp, ulr(lc)+lr(rc), l(rc)+l(lc));
        r(k)=man(lr(lc)+r(rc)-tmp, lr(lc)+ulr(rc), r(rc)+r(lc));
        lr(k)=man(lr(lc)+lr(rc)-tmp, r(lc)+lr(rc), l(rc)+lr(lc));
		ulr(k)=man(l(lc)+r(rc)-tmp, ulr(lc)+r(rc), ulr(rc)+l(lc));
	}

其它部分不难实现。

Tip：

1. 如果你是以区间 \([1,\ n-1]\) 去直接建树的，建议特判操作一中 l, r 的越界情况

2. 计算答案时仍需合并，所以多开亿些结点备用。

Code

#include 
#include 
#include 
#define ls k>1;
		build(ls, l, mid);build(rs, mid+1, r);
		pushup(k, ls, rs);
	}
	void add(int k, int l, int r, int x, int y, int v){
		if(x>1;pushdown(k);
		if(x>1, tmp1=0, tmp2=0;pushdown(k);
		if(x

大常数选手喜提最优解。

P4243 [JSOI2009]等差数列

标签：down   需要   query   printf   端点   建议   维护   tip   i+1   

原文地址：https://www.cnblogs.com/sizeof127/p/14614492.html