在java中将嵌套的"for"循环转换为单个"for"循环

Question

for(i=0;i<k;i++)
{
l=sc.nextLong();
r=sc.nextLong();
v=sc.nextLong();
for(j=l-1;j<r;j++)
{
m=(int)j;
ar[m]=ar[m]+(long)v;
}
}

我正在解决一个竞争性编程问题，我需要将此嵌套的 for 循环优化为单个 for 循环。代码的执行时间应低于 2 秒，这需要 2 秒。这里 k，l，r，v 可以是 0 到 10^9 范围内的整数值。

Answer 1

我不认为你可以避免两个循环，但你可以让它按顺序排列，而不是嵌套。

long[] delta = new long[ar];
for(i=0;i<k;i++)
{
l=sc.nextLong();
r=sc.nextLong();
v=sc.nextLong();
if (l-1 < r) {
m=(int)(l-1);
delta[m] = v;
m=(int)r;
if (m < delta.length) {
delta[m] = -v;
}
}
}
long cumulative = 0;
for (int a = 0; a < ar.length; ++a) {
cumulative += delta[a];
ar[a] += cumulative;
}

这不是继续递增每个l,r范围delta的值，而是只存储一个"增量"数组：这将一个+v存储在索引处，您将开始将数组递增v;-v在停止的索引处存储。 因此，记录l和r之间的范围应递增v现在是一个 O(1) 操作，而不是 O(r-l) 操作。

因此，此数组的某些部分如下所示：

2    
0 0   0 0 0 0 0   0 0 0
-2

(我只是垂直移动 2s 以使其更清晰)

如果计算这些元素的累积总和：

2 2 2 2 2 2  
0 0             0 0 0 0

换句话说，您可以通过仅存储此范围的开始和结束位置来显示要递增 2 的范围。

这就是cumulative变量存储的内容：它只是当前位置左侧(包括当前位置)的delta数组中所有元素的总和。这就是增加相应元素的量ar增加。