I 题解

首先考虑一个朴素dp。

我们将节目按照时刻排序，令 表示时刻 时，在位置 的最小不满值。

显然可以得到状态转移方程：

其中 表示时刻 时，位置 对当前时刻所有节目的不满值之和，即：

可以把状态转移方程写成：

容易观察到，如果用一个数组 来记录当前时刻的 值，那么 在时刻 的更新方式可以写成下面的两步：

1. 对 前缀取 ，即 。
2. 对每个满足 的 ，更新 。

那么 在时刻 的更新方式可以写成下面的两步：

1. 对 的所有位置和 取 ，即 。
2. 对每个满足 的 ，更新 ，对 ，更新 ，对 ，更新 。

下面证明第一步的正确性。

由于 是关于 的下凸函数，如果假定 在时刻 之前是下凸的，所以完成第二步之后， 仍然是下凸的。

我们发现如果观察 的差分数组 ，一定是一个单调不下降的数组。那么对 的所有位置取 之后， 受到影响的位置对 的影响一定是正确的。（这里可以感性理解一下）

我们可以维护一个线段树，支持区间加和全局对一个数取 的操作。最后答案就是 的最小值。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define N 100005
int n,l,m;vector<int>pos[N];
ll mn[N*4],tg1[N*4],tg2[N*4];bool istg2[N*4];
ll get()
{
	ll x=0;int f=1;char c=getchar();
	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return x*f;
}
void addval1(int k,ll v)
{
	mn[k]+=v;
	tg1[k]+=v;
	if(istg2[k])tg2[k]+=v;
}
void addval2(int k,ll v)
{
	mn[k]=min(mn[k],v);
	if(istg2[k])tg2[k]=min(tg2[k],v);
	else tg2[k]=v,istg2[k]=1;
}
void pushdown(int k)
{
	addval1(k<<1,tg1[k]);
	addval1(k<<1|1,tg1[k]);
	tg1[k]=0;
	if(istg2[k])
	{
		addval2(k<<1,tg2[k]);
		addval2(k<<1|1,tg2[k]);
		istg2[k]=0;
	}
}
void upd(int k,int l,int r,int x,int y,ll v)
{
	if(l>=x&&r<=y)return addval1(k,v);
	pushdown(k);
	int mid=l+r>>1;
	if(x<=mid)upd(k<<1,l,mid,x,y,v);
	if(y>mid)upd(k<<1|1,mid+1,r,x,y,v);
	mn[k]=min(mn[k<<1],mn[k<<1|1]);
}
ll query(int k,int l,int r)
{
	if(l==r)return mn[k];
	pushdown(k);
	int mid=l+r>>1;
	return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
void solve()
{
	n=get(),l=get();
	For(i,1,n)
	{
		int t=get(),p=get();
		m=max(m,t);
		pos[t].push_back(p);
	}
	ll sum=0;
	For(i,1,m)if(!pos[i].empty())
	{
		for(auto j:pos[i])
		{
			sum+=j;
			upd(1,1,l,1,j,-1);
			upd(1,1,l,j+1,l,1);
		}
		addval2(1,0);
	}
	cout<<sum+query(1,1,l)<<'\n';
}
int main()
{
	int t=1;
	//t=get();
	while(t--)solve();
	return 0;
}