求助关于时间复杂度的验证

RT，在“维护区间绝对值之和”这个问题中（操作有区间加、区间查询两种），我的思路是开两个线段树，一个维护正数的和以及最大值，一个维护负数的和以及最大值。每次在区间加的时候，每个负数最多只会变成正数一次，所以理论上均摊是

O(n \log n)

的，但是我自己造了一个 1e6 的数据却 T 飞了。

CPP

scanf("%lld",&k);
upd1(1,1,n,l,r,k); //给正数有效的东西都 +k
while(query1(1,1,n,l,r).first+k>=0)
{
	pair<int,int> tmp=query1(1,1,n,l,r); // 记录下来当前的信息（first 表示最大值，second 表示最大值的位置）
	upd1(1,1,n,tmp.second,tmp.second,INF+tmp.first+k); // 在正数中加上这个点
	upd2(1,1,n,tmp.second,tmp.second,INF); // 从负数中删去这个点
}
upd2(1,1,n,l,r,k);  // 给负数有效的点都 +k

以上是我的代码。我认为我的代码保证了一个负数最多只会计算一次，但是它 T 飞了，求大佬帮忙看一下是不是写出了问题。

求助关于时间复杂度的验证

讨论操作

回复

相关推荐

求助关于时间复杂度的验证