单调队列优化dp

粉刷木板

题意

有\(N\)块木板从左到右排成一行，有\(M\)个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。第\(i\)个木匠要么不粉刷，要么粉刷包含木板\(S_{i}\)且长度不超过\(L_{i}\)的连续的一段木板，每粉刷一块可以得到\(P_{i}\)的报酬。求最大总报酬。

分析

先考虑一个朴素的\(dp\)。我们设\(f[i][j]\)表示我们考虑前\(i\)个工匠，前\(j\)块木板所能得到的最大价值。我们有转移\(f[i][j]=Max(f[i-1][j],f[i][j-1],f[i][k]+(j-k)*p[i])\to k∈[j-l_{i},s[i]-1]\)。

接着我们可以把\(dp\)式转化为\(f[i][j]=Max(f[i][k]-k*p[i]+j*p[i])\)。

我们可以考虑单调队列优化\(dp\)。首先将所有工匠按照\(s[i]\)大小从小到大排序，这样可以保证\(k\)序列不总为\(k\)从而取不到合适的\(k\)。而后我们考虑可以维护一个较优的\(k\)序列，每次操作前先检查队首是否最优。而后我们在\(j>s[i]\&\&s[i]+l[j]\ge j\)时候对\(f[i]\)进行转移。而后我们对队尾的\(k\)进行最优性检查。而后我们将\(j\)入队。可以考虑使用\(deque\)或\(list\)维护。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int s[N],l[N];
int f[105][N];
int n,m;
int p[N];
int get_ans(int x,int i){
	return f[i-1][x]-p[i]*x;
}
struct Str {
	int l, p, s;
} str[N];
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&str[i].l,&str[i].p,&str[i].s);
	}
	sort(str + 1, str + m + 1, [] (const Str& A, const Str& B) {
		return A.s < B.s;
	});
	for (int i = 1; i <= m; ++i) {
		l[i] = str[i].l, p[i] = str[i].p, s[i] = str[i].s;
	}
	for(int i=1;i<=m;i++){
		list<int> q;
		if(str[i].s-str[i].l<=0) q.push_front(0);
		for(int j=1;j<=n;j++){
			f[i][j]=max(f[i-1][j],f[i][j-1]);
			while(!q.empty()&&(q.front()>str[i].s-1||q.front()<j-str[i].l)) q.pop_front();
			if(!q.empty()&&j>=str[i].s&&str[i].s+str[i].l>=j)f[i][j]=max(get_ans(q.front(),i)+str[i].p*j,f[i][j]);
			if (j<str[i].s&&j>=str[i].s-str[i].l) {
				while (!q.empty()&&get_ans(q.back(), i)<get_ans(j, i)) q.pop_back();
				q.push_back(j);
			}
		}
	}
	printf("%d",f[m][n]);
}
int main(){solve();return 0;}

线段树

魔法传输

题意

我们对于一段区间\([L,R]\)，我们对于区间第\(1\)个加\(1\)，第\(2\)个加\(2\)，第\(n\)个加\(n\)。

分析

那么我们可以维护一个差分序列，每次对\([L,R]\)区间加\(1\)，而后我们对\(R+1\)减掉\(R-L+1\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
const int N=5e5+7;
const int mod=1e9+7;
int sum[N],laz[N];
int a[N];
int n,m;
void add(int k,int l,int r,int val){
	sum[k]+=val*(r-l+1);
	laz[k]+=val;
}
void pushdown(int k,int l,int r){
	if(!laz[k]) return;
	add(ls,l,mid,laz[k]);
	add(rs,mid+1,r,laz[k]);
	laz[k]=0;
}
int query(int k,int l,int r,int x,int y){
	int res=0;
	if(x<=l&&y>=r) return sum[k]%mod;
	pushdown(k,l,r);
	if(x<=mid) res+=query(ls,l,mid,x,y);
	if(y>=mid+1) res+=query(rs,mid+1,r,x,y);
	return res%=mod;
}
void pushup(int k,int l,int r){
	return sum[k]=sum[ls]+sum[rs],void();
}
void modify(int k,int l,int r,int x,int y,int val){
	if(x<=l&&y>=r) return add(k,l,r,val),void();
	pushdown(k,l,r);
	if(x<=mid) modify(ls,l,mid,x,y,val);
	if(y>=mid+1) modify(rs,mid+1,r,x,y,val);
	pushup(k,l,r);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		int l,r;
		char op[4];
		scanf("%s",op);
		if(op[0]=='C'){
			scanf("%lld%lld",&l,&r);
			modify(1,1,n,l,r,1);
			modify(1,1,n,r+1,r+1,-(r-l+1));
		}
		else scanf("%lld",&l),printf("%lld\n",query(1,1,n,1,l));
	}
	return 0;
}

可持久化线段树\(1\)

题意

rt。

分析

我们先建出一棵空树。而后我们每次都先建出一个新\(root\)。我们将修改的子节点到新根链接出一条新路径。而后我们把这条路径和上一个版本的线段树相连。这样就可以通过\(root[pre]\)得到每个版本的线段树。单点query写法与正常线段树相同。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define mid ((l+r)>>1)
const int N=100000005;
int a[N];
int rt[N];
struct seg_tree{
	int ls[N],rs[N],sum[N],cnt;
	void build(int &k,int l,int r){
		k=++cnt;
		if(l==r)return sum[k]=a[l],void();
		build(ls[k],l,mid),build(rs[k],mid+1,r);
	}
	void modify(int &k,int pre,int l,int r,int x,int val){
		k=++cnt,ls[k]=ls[pre],rs[k]=rs[pre],sum[k]=sum[pre];
		if(l==r) return sum[k]=val,void();
		if(x<=mid) modify(ls[k],ls[pre],l,mid,x,val);
		else modify(rs[k],rs[pre],mid+1,r,x,val);
	}
	int query(int k,int l,int r,int x){
		if(l==r) return sum[k];
		if(x<=mid) return query(ls[k],l,mid,x);
		else return query(rs[k],mid+1,r,x);
	}
}T;
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	T.build(rt[0],1,n);
	for(int i=1;i<=m;i++){
		int pre,opt,x,v;
		scanf("%d%d%d",&pre,&opt,&x);
		if(opt==1){
			scanf("%d",&v);
			T.modify(rt[i],rt[pre],1,n,x,v);
		}
		else printf("%d\n",T.query(rt[pre],1,n,x)), rt[i] = rt[pre];
	}
}
int main(){
	solve();return 0;
}

队伍整理

题意

给定一个队列里的一些人的排名数列，而后我们进行两个操作。

询问排在\(i\)位置的人前面的人最好的成绩是多少。
排在\(i\)位置的人移动到队尾。

最后我们需要输出最少移动多少同学使得队伍没有空隙。

分析

我们考虑使用线段树维护队列位置上的人的排名。

对于\(1\)操作我们可以求位置\(i\)前的线段树上的\(Min\)排名，对于\(2\)操作我们可以将原位置排名赋值为\(inf\)而后我们讲该排名移动到线段树上\(len+1\)的位置。对于询问我们可以将有人的位置打上标记，我们维护\(vis\)数组对应的前缀和数组\(sum[i]\)。而后我们枚举求出\(sum[i]-sum[i-n]\)的最大值。结果就是\(n-Max(sum[i]-sum[i-n])\)。

我们注意需要注意线段树的空间是\(n+m\)而我们查询的时候同理查询上限是\(n+m\)而不是\(n\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define ls (k<<1)
#define rs (k<<1|1)
const int N=2e5+5;
const int inf=1e9+9;
int n,m,a[N],sum[N],b[10000010],tr[N<<2];
int vis[N];
struct seg_tree{
  void pushup(int k,int l,int r){
    tr[k]=min(tr[ls],tr[rs]);
  }
  void build(int k,int l,int r){
    if(l==r) return tr[k]=a[l],void();
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(k,l,r);
  }
  void modify(int k,int l,int r,int x,int val){
    if(l==r) return tr[k]=val,void();
    if(x<=mid) modify(ls,l,mid,x,val);
    else modify(rs,mid+1,r,x,val);
    pushup(k,l,r);
  }
  int query(int k,int l,int r,int x,int y){
    if(y<x) return inf;
    if(x<=l&&r<=y) return tr[k];
    int res=inf;
    if(x<=mid) res=min(res,query(ls,l,mid,x,y));
    if(y>=mid+1) res=min(res,query(rs,mid+1,r,x,y));
    return res;
  }
}T;
char op;
int main(){
  scanf("%d%d",&n,&m);
  memset(a,0x3f,sizeof a);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;
  T.build(1,1,n+m);
  int len=n;
  for(int i=1;i<=m;i++){
    cin>>op;
    int x;scanf("%d",&x);
    if(op=='A'){
      if(!b[x]){printf("-1\n");continue;}
      int ans=T.query(1,1,n+m,1,b[x]-1);
      if(ans==inf) ans=-1;
      printf("%d\n",ans);
    }
    else{
      T.modify(1,1,n+m,b[x],inf);
      b[x]=++len;
      T.modify(1,1,n+m,b[x],x);
    }
  }
  int res=0;
  for(int i=1;i<=n;i++) vis[b[a[i]]]=1;
  for(int i=1;i<=n+m;i++) sum[i]=sum[i-1]+vis[i];
  for(int i=n;i<=n+m;i++) res=max(res,sum[i]-sum[i-n]);
  res=n-res;
  printf("%d",res);
  return 0;
}