526互联

如何处理一类多区间问题

发布时间 2023-10-07 14:07:36作者: 颈流推进

形如 \(\sum_{i=l}^r M(L+i,R+i,x)\) 一类问题

不难发现这个东西实际上就是一堆等差数列，考虑这样高维差分

我们在 \(i\) 处放一个 1 ，就相当于在这里生成了一个公差为 1 等差数列，先在 \(L+l\) 处 生成一个数列

1 1 1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1 1
	1 1 1 1 1 1 1 1 1 
	  1 1 1 1 1 1 1 1
		1 1 1 1 1 1 1
		  1 1 1 1 1 1
			1 1 1 1 1
			  1 1 1 1
				1 1 1
				  1 1 
					1

再在\(R+l+1\)处放一个 -1

1 1 1 1 1 1 0 0 0 0 0 0
  1 1 1 1 1 1 0 0 0 0 0
	1 1 1 1 1 1 0 0 0 0
	  1 1 1 1 1 1 0 0 0
		1 1 1 1 1 1 0 0
		  1 1 1 1 1 1 0
			1 1 1 1 1 1
			  1 1 1 1 1
				1 1 1 1
				  1 1 1
					1 1
					  1

再在 \(L+r+1\) 处加一个 -1

1 1 1 1 1 1 0 0 0 0 0 0
  1 1 1 1 1 1 0 0 0 0 0
	1 1 1 1 1 1 0 0 0 0
	  1 1 1 1 1 1 0 0 0
		1 1 1 1 1 1 0 0
		  0 0 0 0 0 0 -1
			0 0 0 0 0 0
			  0 0 0 0 0
				0 0 0 0
				  0 0 0
					0 0
					  0

然后在 \(R+r+2\) 处加一个 1

1 1 1 1 1 1 0 0 0 0 0 0
  1 1 1 1 1 1 0 0 0 0 0
	1 1 1 1 1 1 0 0 0 0
	  1 1 1 1 1 1 0 0 0
		1 1 1 1 1 1 0 0
		  0 0 0 0 0 0 0
			0 0 0 0 0 0
			  0 0 0 0 0
				0 0 0 0
				  0 0 0
					0 0
					  0