单调队列优化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;
}