首先膜一下VFK的A+B problem，虽然那是网络流，但是是相通的嘛。

关于主席树的优化，其实是一个很好地想法，在网络流上的点要向一个连续的段连边时，该优化可以很好地把相同的点整合起来，然后大大减少边的条数，提升效率。

期中考试复习时无聊，把曾经做过的三题整合了一下，出了一道题

=====================================简要题意==================================

在一条数轴上有n个人，m个操作

一个操作有两个信息x[i],y[i]

x[i]表示你要派一个人去x[i]这个位置。

y[i]表示这个被派去的人不能响应接下来的y[i]个操作。

初始n个人都在0点。最小化所有人走的路程的sigma。

数据范围n*m<=10W，时限5s

===============================================================================

先说m^2建图

对m个操作，每个操作建两个点，把两个对应点称呼为入点和出点，入点向出点连边，流量1，费用0，表示该点被选了。

然后对操作i的出点，向操作j满足j>i+y[i]的入点连边，费用是两点间的距离。（表示i干完干j）

每个出点再向T连边，费用0。（表示干完收工）S向s连边，流量为n，s向每个i的入点连边，费用0。（表示第一次干）

s向T连边，费用0。（表示这个人不用干）

看上去好像没有什么问题。但是如果要最小化的话，所有的流量都是S->s->T，因为这样不用任何费用。

但是这样显然是错的，那怎么办呢？

考虑造成这种情况的原因。也就是不走比走更优，所以谁都不走了。

怎么办呢？

单独考虑一个人。我们可以给他规定，每跳过一个人就要收取一定的费用，这个费用比最大的走的路程还要大很多，使他能不跳即不跳。

然后对于n个人而言，一共跳过的人是固定的=(n-1)*m，所以只要最后减去这个值就好了。

这就是所谓的加权想法，其实在许多费用流中都会用到。比如取反求最大的思路其实也是这样的。

所以，建图就变成了这样。INF为跳过收的费用。

对m个操作，每个操作建两个点，把两个对应点称呼为入点和出点，入点向出点连边，流量1，费用-INF，表示该点被选了，要把跳过的费用减去。

然后对操作i的出点，向操作j满足j>i+y[i]的入点连边，费用是两点间的距离+(j-i+1)*INF。（表示i干完干j，中间跳过了若干点。因为后面j的费用还会再减去，所以这边先加上）

每个出点再向T连边，费用是(m-i)*INF。（表示干完收工，跳过了m-i个点）S向s连边，流量为n，s向每个i的入点连边，费用i*INF。（表示第一次干，跳过了若干点）

s向T连边，费用m*INF。（表示这个人不用干）

最后再减去(n-1)*m*INF就好了。

===============================================================================

现在来说标算

问题的关键在于出点和入点之间的连边是m^2级别的，这很不友好。

先抛开跳过的费用，观察边权。对于i的出点向j的入点连边，如果x[i]<x[j]，边权就是x[j]-x[i]，否则就是x[i]-x[j]

然后我们可以把这个差的两个值分开。比如只考虑x[i]<x[j]

那么我们要弄一个点，他连向所有的满足x[j]>x[i]并且j>i+y[i]的入点。

然后只要x[i]连向这个点的点权是-x[i]，这个点连出去的点权是x[j]就达到了效果。

但是因为有两个限制，所以比较麻烦。

因此考虑主席树。离散化x[i]后，建立主席树，那么就可以找出logn个能表示出x[j]>x[i]并且j>i+y[i]的点了。

然后在主席树上，同一个root的点之间由上至下连费用0流量oo的边，叶子节点向对应的j连边权是x[j]的边。

同时，一个点还向他对应的 曾经 连边，边权一会再说。

然后对于一个i，只要向那logn个表示出x[j]>x[i]并且j>i+y[i]的点连边权是-x[i]的边就好了。

x[i]>x[j]同理，只要建立两棵主席树就可以搞定了。关于s和S和T的不变，可以把s也当成一个x=y=i=0的操作的出点。

现在来考虑跳过的费用。

这个只要在主席树上对应点连边的时候考虑进去就行了。

===============================================================================

由于对于主席树上的一些对应名词不太清楚，所以口述很难说清，下面上代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 10010
#define M 310010
#define H 1400010
#define np 10000000ll	//这个就是跳过的费用 
#define INF 1e9			//这个是无限大 
using namespace std;
int n,m,x[N],y[N],xx[N],newp,l,i,ln,S,T,j,q[M],pre[M],lld,u;
int head[M],lc[M],rc[M],root[N],lab[M],root1[N];
int ne[H],v[H],flow[H],wz[M],len;
long long cost[H],dis[M];
//root、root1表示主席树的根，lc、rc表示主席树上每个点的左右儿子
//lab表示主席树上一个点所在的root的编号。比如lab[root[i]]=i。这个是用来算跳过时用的 
void add(int x,int y,long long c,int f)//这个是连边 
{
	if(!x||!y)return;//由于主席树上一些点可能是空的所以要跳过 
	v[++l]=y;ne[l]=head[x];head[x]=l;cost[l]=c;flow[l]=f;
	v[++l]=x;ne[l]=head[y];head[y]=l;cost[l]=-c;flow[l]=0;
}
void add(int &cur,int cur1,int l,int r,int x,int y)//这是建立x[i]<x[j]的主席树
{
	cur=++newp;add(cur,cur1,np*(lab[cur1]-y),INF);//对应点连边 
	lab[cur]=y;lc[cur]=lc[cur1];rc[cur]=rc[cur1];
	if(l==r){add(cur,y,xx[x],INF);return;}int mid=(l+r)>>1;
	if(x<=mid)add(lc[cur],lc[cur1],l,mid,x,y),add(cur,lc[cur],0,INF);//向儿子连边 
	else add(rc[cur],rc[cur1],mid+1,r,x,y),add(cur,rc[cur],0,INF);//向儿子连边
}
void aad(int &cur,int cur1,int l,int r,int x,int y)//这是建立x[i]<x[j]的主席树
{
	cur=++newp;add(cur,cur1,np*(lab[cur1]-y),INF);//对应点连边 
	lab[cur]=y;lc[cur]=lc[cur1];rc[cur]=rc[cur1];
	if(l==r){add(cur,y,-xx[x],INF);return;}int mid=(l+r)>>1;
	if(x<=mid)aad(lc[cur],lc[cur1],l,mid,x,y),add(cur,lc[cur],0,INF);//向儿子连边
	else aad(rc[cur],rc[cur1],mid+1,r,x,y),add(cur,rc[cur],0,INF);//向儿子连边
}
void find(int cur,int cur1,int l,int r,int x,int y,int z)//建图时出点向主席树连边 
{
	if(l==r)
	{
		add(y,cur,-xx[x]+(lab[cur]-z)*np,INF);//到叶子节点时，x[i]==x[j]，所以两棵主席树都连边 
		add(y,cur1,xx[x]+(lab[cur1]-z)*np,INF);
		return;
	}int mid=(l+r)>>1;
	if(x<=mid)
	{
		add(y,rc[cur],-xx[x]+(lab[rc[cur]]-z)*np,INF);//因为向左走，所以向x[i]<x[j]的主席树连边 
		find(lc[cur],lc[cur1],l,mid,x,y,z);
	}else
	{
		add(y,lc[cur1],xx[x]+(lab[lc[cur1]]-z)*np,INF);//因为向右走，所以向x[i]>x[j]的主席树连边
		find(rc[cur],rc[cur1],mid+1,r,x,y,z);
	}
}
void pushup(int x,int y)//堆的pushup，因为spfa不加堆优化会T，所以写了个。 
{
	for(;x>>1&&dis[q[x>>1]]>dis[y];x>>=1)
		q[x]=q[x>>1],wz[q[x]]=x;
	q[x]=y;wz[y]=x;
}
void pushdown(int x,int y)//堆的pushdown 
{
	for(;x<<1<=len;x=lld)
	{
		lld=x<<1;if(lld<len&&dis[q[lld|1]]<dis[q[lld]])lld|=1;
		if(dis[q[lld]]>=dis[y])break;q[x]=q[lld];wz[q[x]]=x;
	}q[x]=y;wz[y]=x;
}
void spfa()//费用流的spfa 
{
	memset(dis,63,sizeof(dis));
	dis[S]=0;len=1;pushup(1,S);
	while(len)
	{
		u=q[1];pushdown(1,q[len--]);wz[u]=0;
		for(j=head[u],wz[u]=0;j;j=ne[j])
			if(flow[j]&&dis[u]+cost[j]<dis[v[j]])
			{
				dis[v[j]]=dis[u]+cost[j];pre[v[j]]=j;
				if(!wz[v[j]])wz[v[j]]=++len;pushup(wz[v[j]],v[j]);
			}
	}
}
long long max_cost_flow()//费用流啦。因为建图时省略了s点，所以就强制流n次，每次流1的流量 
{
	long long ans=0;
	for(int tc=1;tc<=n;tc++)
	{
		spfa();ans+=dis[T];
		for(i=T;i!=S;i=v[pre[i]^1])
			flow[pre[i]]--,flow[pre[i]^1]++;
	}return ans;
}
int main()
{
	freopen("plate.in","r",stdin);
	freopen("plate.out","w",stdout);
	scanf("%d%d",&n,&m);l=1;
	for(i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]),xx[i]=x[i];
	sort(xx+1,xx+m+2);ln=unique(xx+1,xx+m+2)-xx-1;newp=m*2;//这里是离散化和预处理 
	for(i=m;i>=1;i--)
	{
		x[i]=lower_bound(xx+1,xx+ln+1,x[i])-xx;
		add(root[i],root[i+1],1,ln,x[i],i);add(i,i+m,-np,1);
		aad(root1[i],root1[i+1],1,ln,x[i],i);
		if(i+y[i]+1<=m)find(root[i+y[i]+1],root1[i+y[i]+1],1,ln,x[i],i+m,i);
	}S=newp+1;T=S+1;add(S,T,np*m,m);
	find(root[1],root1[1],1,ln,lower_bound(xx+1,xx+ln+1,0)-xx,S,0);
	for(i=1;i<=m;i++)add(i+m,T,np*(m-i),1);//以上是建图
	printf("%lld\n",max_cost_flow()-np*(n-1)*m);
}

希望大家能看懂QAQ。。因为习惯，本弱的变量名奇葩，格式不好，各位不要介意。。