自动搬运

查看原文

来自洛谷，原作者为

	Terrible 没错，这家伙还真的是很懒惰，真的什么都没留下！！

搬运于2025-08-24 22:42:16，当前版本为作者最后更新于2023-07-26 22:48:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们尝试用堆解决这个问题。

由于处理的核心是冰山两头，于是有了一个大根堆和一个小根堆，由于两个堆需要统一删除某些值，所以我们只在堆内记录下标，在堆外记录具体数据以及它是否被删除了。

考虑每次的修改操作，修改值后不改变堆内结点的相对大小关系，不需要重构堆，但不可能每次修改所有的值，我们得想个办法规避一下。每次修改，只是整体发生了朝某个方向偏移，只需要将整体的偏移表示出来就行。

修改偏移之后还需要处理冰山消融和碎裂的情况，对着大根堆和小根堆的头部结点依次操作即可，注意到一个冰山可能产生 $10^9$ 个碎片，而多个冰山只有体积大小的区别，所以可以考虑同等体积的冰山打包处理。但是我们也不必把所有同等体积的冰山都放到一块处理，只需要把碎片们打包就行了，当然考虑到一个顶级冰山能反复碎裂，自然也要把顶级冰山也打包处理。一个顶级冰山可以碎出来 $10^9$ 个小块，这 $10^9$ 个小块还能在一天成长成顶级冰山，然后每个顶级冰山又都可以碎出来 $10^9$ 个小块，循环下去总的数量轻而易举地就可以超过 __int128 的范围，考虑对打包的数量也进行模处理，总的冰山数量也要进行模处理。

这样所有要点都考虑完了，开始实现吧！

用 STL 实现

众所周知 std::priority_queue 第三个模板参数可以塞一个结构体，这个结构体可以用来确定堆内各个结点的大小关系，但是具体如何操作呢？我们有时候用到小根堆可以把第三个模板参数换成 std::greater，我们打开库文件，可以看到它的实现：

  template<typename _Tp>
    struct greater : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
    };

我们只需要仿照这个样子写一下就行了！

具体代码

不开 long long 见祖宗！模拟的部分不再多说了，如果有细节处搞不清楚可以看看下面代码：

#include<queue>
#include<cstdio>
#include<vector>
const int N=400009,mod=998244353;
//根据下面的实现，数组大小是 n+3m，也就是 4e5 左右
long long val[N],cnt[N],_n;bool notexist[N];
//val 只允许添加不允许修改，_n 表示目前添加到的地方
//cnt 是每个 val 配套的数量，取模下的意义
//notexist 是判断是否被删除的核心依据
struct valgreater
{//STL 小根堆配套比较运算
	bool operator()(const int&i1,const int&i2)
	{return val[i1]>val[i2];}//根据下标比较对应的值
};
struct valless
{//STL 大根堆配套比较运算
	bool operator()(const int&i1,const int&i2)
	{return val[i1]<val[i2];}//根据下标比较对应的值
};
std::priority_queue<int,std::vector<int>,valless>    max_heap;//下标大根堆
std::priority_queue<int,std::vector<int>,valgreater> min_heap;//下标小根堆
int main()
{
	int n,m,k;scanf("%d%d%d",&n,&m,&k);
	//或许修改具体值比较难，不妨逆向修改标志这些值偏移量的标准，毕竟运动是相对的
	long long minval=0,maxval=k,total=0,num=0;
	//要求 minval<val<=maxval 否则会消融或分裂，val[i]-minval 才是原本的指标
	//total 记录冰山体积之和，num 记录冰山数量 
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&val[++_n]),num+=cnt[_n]=1;
		total=(total+val[_n])%mod;
		max_heap.push(_n),min_heap.push(_n);
	}
	while(m--)
	{
		int x,y;scanf("%d%d",&x,&y);
		minval-=x,maxval-=x;//修改标准，相对地看相当于修改了所有的数值
		if(x<0)//冰山减小
		{
			x=-x;
			while(!min_heap.empty())
			{
				int i=min_heap.top();
				if(notexist[i])/*什么也不做*/;
				else if(val[i]<=minval)//消融的标准水涨船高
				{
					notexist[i]=1;num=(num+mod-cnt[i])%mod;
					total=(total+mod-cnt[i]*(val[i]-minval+x)%mod)%mod;
				}
				else break;
				min_heap.pop();
			}
			total=(total+mod-num*x%mod)%mod;
		}
		else if(x>0)//冰山增大
		{
			long long ceiling=0,debris=0;
			//ceiling 顶级冰山数量，debris 生成碎片数量（模意义下）
			while(!max_heap.empty())
			{
				int i=max_heap.top();
				if(notexist[i])/*什么也不做*/;
				else if(val[i]>maxval)//分裂的标准下降了
				{
					notexist[i]=1;ceiling=(ceiling+cnt[i])%mod;
					debris=(debris+cnt[i]*(val[i]-maxval)%mod)%mod;
				}
				else break;
				max_heap.pop();
			}
			total=(total+num*x)%mod;
			if(ceiling)//如果有冰山裂开来，裂开新建两项打包处理
			{
				val[++_n]=maxval,cnt[_n]=ceiling;
				min_heap.push(_n),max_heap.push(_n);
				val[++_n]=minval+1,cnt[_n]=debris;
				min_heap.push(_n),max_heap.push(_n);
				num=(num+debris)%mod;
			}
		}
		if(y)
		{
			total=(total+y)%mod,num=(num+1)%mod;
			val[++_n]=y+minval,cnt[_n]=1;//需要根据现在的标准记录大小
			min_heap.push(_n),max_heap.push(_n);
		}
		printf("%lld\n",total);
	}
	return 0;
}