A. Dreamoon Likes Coloring
显然我们不看把整块涂满 最优的构造
就是1 2 3 4....
但是要考虑将整块板涂满
我们就要往右挪 显然我们每次挪后面的板子都会动
我们一定要让后面的板子都不能超过总长
我们用st表维护后面的板子最右端的最长即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 998244353;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int f[N][30],n,b[N],m;
void init(){
for(int len=0;len<30;len++){
for(int i=1;i+(1<<len)-1<=m;i++){
if(!len)f[i][len]=b[i];
else f[i][len]=max(f[i][len-1],f[i+(1<<(len-1))][len-1]);
} //i+1<<len-1的话是包括了i 不用加1
}
}
int query(int l,int r){
int len=r-l+1;
int k=log(len)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]); //而r-1<<k是没有包含到r所以要+1
}
void solve() {
cin>>n>>m;
vector<int>a(m+10);
int sum=0,mx=0;
for(int i=1;i<=m;i++){
cin>>a[i],sum+=a[i];
mx=max(a[i]+i-1,mx);
b[i]=a[i]+i-1;
}
if(sum<n||mx>n){cout<<-1<<endl;return;}
init();
vector<int>s(m+10);
int now=0;
for(int i=2;i<=m;i++){
int need=n-query(i,m)-now;
if(need>a[i-1]-1){
s[i]+=a[i-1]-1;
now+=s[i];
}else{
s[i]+=need;
break;
}
}
for(int i=1;i<=m;i++){
s[i]+=s[i-1];
}
for(int i=1;i<=m;i++){
cout<<s[i]+i<<' ';
}cout<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:631,const,10,int,Codeforces,aramis,板子,mx
From: https://www.cnblogs.com/ycllz/p/16835015.html