（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-/sum_{j=1}^ip_jb_j
/]
后面那项确定，我们只需最小化 /(/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行以内的。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/278706.html