CF1051G 题解

本文主要是介绍CF1051G 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

（Link，Div2，2900）

考场上看到这道题：哇！这个操作好神奇！哇！样例这个操作方案太妙了！卧槽？为什么总费用还能是负数？（花30min模拟样例）什么阴间操作，毫无规律可循，跑路跑路。……

笔者赛场上的思维能力仅限于此。言归正传，提升观察的高度，发现每个 \(a_i\) 操作前或操作后总有一个 \(a_j\) 与之相邻，于是往 \(a\) 值域上的连续段上去想。设初始的 \(a\) 序列为 \(p\)，下文的 \(a\) 均指若干次操作后得到的 \(a\)。跳出出题人挖的思维陷阱，从结果出发，先上两个很重要的 Lemma：

1.每加入一个 \(p_i\) 后经操作得到的满足要求（两两不同）的 \(a_1,\cdots,a_{i}\) 组成的集合是确定的，不确定性仅在于如何分配这个集合中的 \(i\) 个数到 \(1,\cdots,i\) 中去；

2.答案与操作过程无关而仅与最终的序列 \(a\) 有关，对于一种 \(a\) 我们的答案为 \(\sum_{j=1}^i (a_j-p_j)\times b_j=\sum_{j=1}^ia_jb_j-\sum_{j=1}^i p_jb_j\)。

第二个较为浅显，一次让 \(a_j\gets a_j+1\) 的操作花费为 \(b_j\)，让 \(a_j\gets a_j-1\) 的操作花费为 \(-b_j\)，所以对于这个 \(j\)，从 \(p_j\) 转移到 \(a_j\) 的费用便一定是 \((a_j-p_j)\times b_j\)。

对于第一个，数学归纳。\(i=1\) 时显然；若 \(a_1,\cdots,a_{i-1}(i>1)\) 组成的集合确定，设其为 \(S_{i-1}\)，将其排序后形成的连续段为 \([l_1,r_1],\cdots,[l_s,r_s](r_k<l_{k+1})\)，分情况讨论：

• \(\not\exists k,p_i\in[l_k-1,r_k+1]\)，那么任何 \(j<i\) 都不可能和 \(i\) 发生操作，\(a_i\) 动弹不得只能成为 \(p_i\)，集合仍然确定；

• 否则，方便起见设 \(l_0=r_0=-\infty,l_{s+1}=r_{s+1}=\infty\)，找到 \(\min\{k:l_k>p_i\}\)，则初始状态下 \(a_i=p_i\) 会就近加入一个连续段，可能的情况有：

  • Ⅰ.只加入 \([l_k,r_k]\)，当且仅当 \(r_{k-1}+1<p_i=l_k-1\)；
  • Ⅱ.只加入 \([l_{k-1},r_{k-1}]\)，当且仅当 \(p_i\le r_{k-1}+1\)；
  • Ⅲ.同时加入 \([l_{k-1},r_{k-1}]\) 和 \([l_k,r_k]\)（即把它们合并起来），当且仅当 \(r_{k-1}+1=p_i=l_k-1\)。

  无论如何初始时 \(a_i=p_i\) 总会加入一个连续段。接下来 \(a_i\) 会和这个连续段内的数进行各种乱七八糟的操作，其中我们发现一种可以维持集合满足要求的操作方案：

  • 在 \(\exists x\in S_{i-1},x=a_i\) 时，让 \(a_i\) 与之进行操作，得到 \(a_i\gets a_{i+1}\)。

  这个操作方案会得到什么结果呢？

  • Ⅰ.（只加入 \([l_k,r_k]\)）\(a_i\) 不动，得到 \(a_i=l_k-1\)；
  • Ⅱ.（只加入 \([l_{k-1},r_{k-1}]\)） \(a_i\gets r_{k-1}+1\)；
  • Ⅲ.（合并两个连续段）\(a_i\) 仍然不动，\(a_i=l_k-1\)。

  综合以上三种情况的结果找出共性：

  • 通过该操作我们得到一个插入 \(a_i\) 后的数字互不相同的新连续段，该连续段与 \(S_{i-1}\) 包含着的 除了被 \(a_i\) 加入/合并的段 的其它连续段不接。

  在 \(S_{i-1}\) 的基础上删掉被 \(a_i\) 加入/合并的连续段后插入这个新连续段就得到了一种 \(S_i\)。为什么它是唯一确定的呢？

  因为任何一个操作都只能和同连续段的数字进行，进一步地，对一个数 \(x\) 进行一次操作不会使其脱离所在连续段，顶多就是让它挂在连续段两边而已（\(l-1\) 或 \(r+1\)）。特别地，对于一个数字互不相同的连续段，无论怎么操作 \(x\) 其值都会严格保持在连续段左右端点 \([l,r]\) 间。①（这个结论可以手动模拟，是比较易懂的）

  另外的一个点是，题设两个操作互为逆运算，也即，既然在加入 \(p_i\) 后 \(a_i=p_i\) 的状态可以导向如上操作方案得出的结果，那么这个结果也可以导回去。由 ① 对 按如上方案操作 \(a_i\) 后得到的新连续段 任意操作不会使这个连续段的值域发生改变，所以在初始 \(a_i=p_i\) 的状态下进行任何操作也都一定会导向这一个值域上的新连续段。

  值域确定下来后内部数字互不相同的连续段只有一个，所以这个新连续段是板上钉钉一定要加到 \(S_i\) 里面的，同时这个连续段把被 \(a_i\) 加入/合并的连续段（们）全部覆盖了，于是它（们）也一定会被删除。我们在定集合 \(S_{i-1}\) 的基础上改变的只有被 \(a_i\) 加入/合并的连续段以及插入后的新连续段，所以 \(S_i\) 被唯一确定。于是证完了。

以上所有讨论都是在忽略费用的情况下进行的，却能够使接下来的分析轻松许多。我们加进 \(b_i\) 的限制看看会发生什么。

上面我们分析了“可行性”，现在我们来谈“最优性”。我们已经把讨论范围缩减到了一个一个一个一个的连续段，连续段们的操作相互独立；由 Lemma2 我们完全不用管操作过程而只注重结果（@JustKevinXie(现名Destroyer_Garing)）；由 Lemma1 无论怎么操作得到的最终 \(a_{1,\cdots,i}\) 集合确定。这启发我们对每一个连续段进行乱搞（我们也只能对每个连续段分别乱搞），把它翻个底朝天都没问题，只需要达到最优费用即可。重新看向 Lemma2 的式子：

后面那项确定，我们只需最小化 \(\sum_{j=1}^i a_jb_j\)。对于每一个连续段我们可以随便镐镐鑐鑐，准确来说就是我们可以任意改变一个连续段中 \(a_i\) 的排列，即若一个连续段（其中数两两不同）是 \(a_{q_1},a_{q_2},\cdots,a_{q_s}\) 经操作得出的结果的集合，那么这个连续段中的数可以任意分配给 \(a_{q_1},\cdots,a_{q_s}\)。问题来了，如何分配才能使得 \(\sum a_jb_j\) 最小呢？

这是个经典问题，我们会发现重排后最小的 \(b_j\) 对应最大的 \(a_j\)、次小的 \(b_j\) 对应次大的 \(a_j\)、…… 、最大的 \(b_j\) 对应最小的 \(a_j\) 一定是最优方案。证明也很简单，随便交换两个 \(a_j\) 都只会使答案变劣。

于是这道题做完了。我们要做的便是维护每个连续段（可以用 std::set 或者各种奇怪的东西），对每个连续段分别开一个平衡树/动态开点线段树维护单调的 \(b_j\)，加入 \(p_i\) 时直接按照我们证明 Lemma1 时给出的操作方案不断让 \(a_i\gets a_i+1\) 然后分三种情况讨论、加上贡献即可，合并连续段时用启发式合并。总复杂度 \(O(n\log^2 n)\)。

参考实现：

#include <cstdio>
#include <random>
#include <vector>
#include <set>
#define ll long long

using namespace std;

namespace fIO{
    bool f;char c;void re(int &x){
        x=0;f=0;c=getchar();
        while(c<'0'||c>'9') f|=c=='-',c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(f) x=-x;
    }
    void re(char &c){
        c=getchar();while(c==' '||c=='\n'||c=='\r') c=getchar();
    }
    template<class tp,class ...Tp>void re(tp &x,Tp &...y){re(x);re(y...);}
    char st[20];int tp;
    void wr(int n){
        if(!n) return putchar('0'),void();
        if(n<0) putchar('-'),n=-n;
        while(n) st[++tp]=n%10+48,n/=10;
        while(tp) putchar(st[tp--]);
    }
    inline void wr(char c){putchar(c);}
    template<class tp,class ...Tp>void wr(tp x,Tp ...y){wr(x);wr(y...);}
}using fIO::re;using fIO::wr;

mt19937 rnd;

const int N=4e5+5.14114;

int memo[N],tp;

struct info{
	int c;ll s;
	info operator+(const info &x)const{
		return (info){c+x.c,s+x.s};
	}
};

vector<int> vals;

namespace BLT{
	struct node{
		int v,ls,rs;unsigned int pr;info s;
		#define v(x) t[x].v
		#define ls(x) t[x].ls
		#define rs(x) t[x].rs
		#define pr(x) t[x].pr
		#define s(x) t[x].s
	}t[N];
	void updata(int x){s(x)=s(ls(x))+s(rs(x))+(info){1,v(x)};};
	void div(int now,int &x,int &y,int k){
		if(!now) return x=y=0,void();
		if(v(now)<=k) x=now,div(rs(now),rs(now),y,k);
		else y=now,div(ls(now),x,ls(now),k);
		updata(now);
	}
	int merge(int x,int y){
		if(!x||!y) return x|y;
		if(pr(x)<pr(y)){
			rs(x)=merge(rs(x),y);
			updata(x);return x;
		}else{
			ls(y)=merge(x,ls(y));
			updata(y);return y;
		}
	}
	int newnod(int k){
		int nwn=memo[tp--];t[nwn]=(node){k,0,0,rnd(),(info){1,k}};return nwn;
	}
	void ins(int &rt,int k){
		int x,y;div(rt,x,y,k);
		rt=merge(merge(x,newnod(k)),y);
	}
	info qryles(int &rt,int k){
		int x,y;div(rt,x,y,k-1);info res=s(x);
		rt=merge(x,y);return res;
	}
	info qrygrt(int &rt,int k){
		int x,y;div(rt,x,y,k);info res=s(y);
		rt=merge(x,y);return res;
	}
	void breakdown(int now){
		if(!now) return ;
		breakdown(rs(now));
		vals.push_back(v(now));
		breakdown(ls(now));
		memo[++tp]=now;
	}
}using namespace BLT;

struct itv{
	int l,r,rttr;
	bool operator<(const itv &x)const{
		return l<x.l;
	}
};

set<itv> sa;

ll saftz;

enum position{lft,rht};

set<itv>::iterator addtoitv(set<itv>::iterator p,int b,position po){
	int l=p->l,r=p->r,rttr=p->rttr;
	if(po==lft){
		--l;info x=BLT::qrygrt(rttr,b);
		saftz-=x.s-1ll*(l+x.c)*b;
	}else{
		++r;info x=BLT::qryles(rttr,b);
		saftz+=x.s+1ll*(r-x.c)*b;
	}
	BLT::ins(rttr,b);sa.erase(p);
	return sa.insert((itv){l,r,rttr}).first;
}

int main()
{
	while(tp<N) memo[tp]=N-tp,++tp;--tp;
	int n;re(n);ll sorgn=0;
	for(int i=1;i<=n;++i){
		int a,b,flg=0;re(a,b);sorgn+=1ll*a*b;
		auto py=sa.upper_bound((itv){a});
		auto px=py;if(px!=sa.begin()) --px;
		if(py!=sa.begin()&&px->r+1>=a) flg=1,a=px->r+1,px=addtoitv(px,b,rht);
		if(py!=sa.end()&&a==py->l-1){
			if(py!=sa.begin()&&a==px->r){
				vals.clear();
				int szx=px->r-px->l+1,szy=py->r-py->l+1,rttr;
				if(szx<szy){
					BLT::breakdown(px->rttr);
					int pl=px->l;sa.erase(px);
					for(int i=vals.size()-1;~i;--i) saftz-=1ll*vals[i]*(pl+i),
													py=addtoitv(py,vals[i],lft);
				}else{
					BLT::breakdown(py->rttr);
					int pl=py->l;sa.erase(py);
					for(int i=0;i<vals.size();++i) saftz-=1ll*vals[i]*(pl+i),
													px=addtoitv(px,vals[i],rht);
				}
			}
			else addtoitv(py,b,lft);
			flg=1;
		}
		if(!flg) sa.insert((itv){a,a,BLT::newnod(b)}),saftz+=1ll*a*b;
		printf("%lld\n",saftz-sorgn);
	}
}

所以说碰到这种题还是要提升观察高度、多从结果出发找共性，单单盯着样例看有时是不一定有结果的。

本题思维难度大码量也比较大（个人观点），反正我是不算快读写了130多行。很不理解同机房dalao是如何不压行的情况下写进60行以内的。

这篇关于CF1051G 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！