当前位置：首页 > news >正文

模拟赛2026

news 2026/5/12 16:54:38

模拟赛 2026

新一年新气象，戒 P 从我做起！

1.2 NOIP 模拟赛二五

97+100+0+0=197 pts

HHHOJ 爆炸硬控我 3h，导致 T3 无法上交。最后让 zzx 帮我交了一发。

T1

正解 cout<<0; 是个啥？

T2

lg-P4551

经典题，没什么好讲的。

T3

初始有一个大小为 \(n\) 的整数集合 \(\{a_1,a_2,\dots,a_n\}\)。

规定在集合中的元素 \(x,y\) 之间建立起一个双向联系的花费为 \(|x−y|\)，并定义一个集合 \(S\) 的代价为让 \(S\) 中每个元素都与至少一个其他元素建立联系的最小花费总和。（特殊地，对于大小小于 \(2\) 的集合，代价为 \(0\)）

现在有 \(q\) 次操作，每次向集合内添加一个元素或从集合中删去一个元素，要求在每次操作后求出当前集合的代价。

对于 \(100\%\) 的数据，\(1\le n,q\le 2\times 10^5,0\le a_i,x\le 10^9\)。

先考虑不修改怎么做。

可以先将集合 \(a\) 从小到大排序，会发现对于每一个元素都是将其与相邻的两个元素其中 \(1\) 个或 \(2\) 个建立联系时最优。

考虑 dp，设 \(f_{i,0/1}\) 表示前 \(i\) 个数，除了 \(i\) 之外已经建立联系，\(i\) 是否与前一个数建立联系。有 \(f_{i,0}=f_{i-1,1},f_{i,1}=\min(f_{i-1,0},f_{i-1,1})+|a_i-a_{i-1}|\)。

若加上修改，考虑用权值线段树维护。

先离散化，需要考虑如何合并两个区间。

由于中间的数肯定是已经建立联系的，只需要考虑一个区间 \(P\) 在集合中的数的左右的值，为 \(ls_p,rs_p\)。设为 \(f_{p,0/1,0/1}\)，\(0/1\) 的定义同上。

有

pre(p,i,j)=min({pre(p<<1,i,0)+pre(p<<1|1,0,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,0)+pre(p<<1|1,1,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,1)+pre(p<<1|1,0,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,1)+pre(p<<1|1,1,j)
});

\(pre\) 表示 \(f\)，\(p<<1,p<<1|1\) 分别代表左右节点，\(ct(x,y)\) 表示离散化后为 \(x,y\) 的值建立联系的代价。

在注意分讨一下特殊情况就行了。

点击查看代码

#define ll long long
#define MC(x,y) memcpy(x,y,sizeof(x))
const int N=4e5+20,M=1e5+20;
const ll INF=1ll<<60,mod=998244353;
namespace H_H{int n,m,tot,a[N],v[N];struct qry{int op,x;}q[N];bool vis[N];struct Tree{int l,r,ls,rs;ll pre[2][2];#define l(p) t[p].l#define r(p) t[p].r#define ls(p) t[p].ls#define rs(p) t[p].rs#define pre(p,x,y) t[p].pre[x][y]}t[N<<2];inline ll ct(int x,int y){return abs(v[x]-v[y]);}inline void up(int p){//无左右节点 while(!ls(p<<1) && !ls(p<<1|1)) return ls(p)=rs(p)=0,pre(p,0,0)=0,pre(p,0,1)=pre(p,1,0)=pre(p,1,1)=INF,void();//无左节点while(!ls(p<<1)) return ls(p)=ls(p<<1|1),rs(p)=rs(p<<1|1),MC(t[p].pre,t[p<<1|1].pre),void();//无右节点while(!ls(p<<1|1)) return ls(p)=ls(p<<1),rs(p)=rs(p<<1),MC(t[p].pre,t[p<<1].pre),void();//左右节点都只有 1 个节点while(ls(p<<1)==rs(p<<1) && ls(p<<1|1)==rs(p<<1|1)){ls(p)=ls(p<<1);rs(p)=rs(p<<1|1);pre(p,0,0)=0,pre(p,0,1)=pre(p,1,0)=INF,pre(p,1,1)=ct(ls(p),rs(p));return ;}//左只有一个while(ls(p<<1)==rs(p<<1)){ls(p)=ls(p<<1),rs(p)=rs(p<<1|1);pre(p,0,0)=pre(p<<1|1,1,0);pre(p,1,0)=min({pre(p<<1|1,1,0),pre(p<<1|1,0,0)})+ct(rs(p<<1),ls(p<<1|1));pre(p,0,1)=pre(p<<1|1,1,1);pre(p,1,1)=min({pre(p<<1|1,1,1),pre(p<<1|1,0,1)})+ct(rs(p<<1),ls(p<<1|1));return ;}//右只有一个while(ls(p<<1|1)==rs(p<<1|1)){ls(p)=ls(p<<1),rs(p)=rs(p<<1|1);pre(p,0,0)=pre(p<<1,0,1);pre(p,0,1)=min({pre(p<<1,0,1),pre(p<<1,0,0)})+ct(rs(p<<1),ls(p<<1|1));pre(p,1,0)=pre(p<<1,1,1);pre(p,1,1)=min({pre(p<<1,1,1),pre(p<<1,1,0)})+ct(rs(p<<1),ls(p<<1|1));return ;}//一般for(int i=0;i<=1;i++){for(int j=0;j<=1;j++){pre(p,i,j)=min({pre(p<<1,i,0)+pre(p<<1|1,0,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,0)+pre(p<<1|1,1,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,1)+pre(p<<1|1,0,j)+ct(rs(p<<1),ls(p<<1|1)),pre(p<<1,i,1)+pre(p<<1|1,1,j)});}}ls(p)=ls(p<<1),rs(p)=rs(p<<1|1);}void Build(int p=1,int l=1,int r=tot){l(p)=l,r(p)=r;if(l==r){pre(p,0,0)=0;pre(p,0,1)=pre(p,1,0)=pre(p,1,1)=INF;return ;}int mid=(l+r)>>1;Build(p<<1,l,mid);Build(p<<1|1,mid+1,r);up(p);}void update(int p,int op,int d){if(l(p)==r(p)){if(op==1) ls(p)=rs(p)=d;if(op==2) ls(p)=rs(p)=0;return ;}int mid=(l(p)+r(p))>>1;if(d<=mid) update(p<<1,op,d);else update(p<<1|1,op,d);up(p);}int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];v[++tot]=a[i];}sort(a+1,a+1+n);for(int i=1;i<=m;i++){cin>>q[i].op>>q[i].x;v[++tot]=q[i].x;}sort(v+1,v+1+tot);tot=unique(v+1,v+1+tot)-v-1;for(int i=1;i<=n;i++){a[i]=lower_bound(v+1,v+1+tot,a[i])-v;}for(int i=1;i<=m;i++){q[i].x=lower_bound(v+1,v+1+tot,q[i].x)-v;}Build();for(int i=1;i<=n;i++) update(1,1,a[i]);int tt=n;for(int i=1;i<=m;i++){update(1,q[i].op,q[i].x);if(q[i].op==2) tt--;else tt++;if(tt<2) cout<<0<<"\n";else cout<<t[1].pre[1][1]<<"\n";}return 0;}
}