题解：P16956 「NLOI Round1」真空剑圣
Drink_Assam
·
·
题解
其他题解怎么都是 O(n) 的？那就让我来一发无脑 O(m) DP，清晰易懂，我认为难度只有黄！
首先观察一个简单的性质，这也是本做法的最难点：每一个点只被操作一次是不劣的，因为如果被操多次，除最后一次都是无意义的。
那就 DP，设 f_{i,j} 表示操作完前 i 个点，且第 i 个点在 j 时刻被操作的最大总和。转移：
f_{i,j}=\max_{k\ne j}\{f_{i-1,k}\}+y_j\\
f_{i,0}=\max_{k}\{f_{i-1,k}\}+a_i
第一条转移存在的条件是 x_j=i 或 x_j+1=i。
你可能会问：状态数不是 $O(nm)$ 的吗？\
在所有 $m$ 种可能的 $j$ 中，每个 $j$ 只对应两个 $i$ 分别是 $x_j,x_j+1$，所以 $j$ 非零的 $f_{i,j}$ 只有 $2m$ 个，状态数为 $2m+n$ 在 $O(m)$ 级别。
$\max\{f_{n,j}\}$ 即为答案。
:::success[二分版本（不要用 map 因为会被卡常）]
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define bmid ((l+r+1)>>1)
#define pb push_back
#define eb emplace_back
#define fswap(a,b) ((a)^=(b)^=(a)^=(b))
using namespace std;
using ll= long long;
#ifndef ONLINE_JUDGE
template <typename tp>
void _debug(const tp& t) {cerr<<t<<'\n';}
template <typename tp,typename... args>
void _debug(const tp& t, const args&... rest) {cerr<<t<<' ';_debug(rest...);}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
#define int ll
const int N=200005,H=N<<2,inf=1000000000,mod=1000000007;
vector<pair<int,int> > vec[N];
vector<pair<int,int> > f[N],pre[N],suf[N];
int n,m,a[N];
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int x,y,i=1;i<=m;i++) {
cin>>x>>y;
vec[x].eb(i,y);
vec[x+1].eb(i,y);
}
f[0].eb(0,0),pre[0].eb(0,0),suf[0].eb(0,0);
for(int i=1;i<=n;i++) {
f[i].eb(0,pre[i-1].back().se+a[i]);
for(auto& t: vec[i]) {
const int j=t.fi,x=t.se;
auto p=lower_bound(pre[i-1].begin(),pre[i-1].end(),make_pair(j,0ll));
int tm=0;
if(p!=pre[i-1].begin()) tm=max(tm,prev(p)->se+x);
p=upper_bound(suf[i-1].begin(),suf[i-1].end(),make_pair(j,inf));
if(p!=suf[i-1].end()) tm=max(tm,p->se+x);
f[i].eb(j,tm);
}
for(auto t: f[i])
debug(i,t.fi,t.se);
int last=0;
vector<pair<int,int> > ve;
for(auto t: f[i]) {
ve.pb(t);
last=max(last,t.se);
pre[i].eb(t.fi,last);
}
last=0;
reverse(ve.begin(),ve.end());
for(auto t: ve) {
last=max(last,t.se);
suf[i].eb(t.fi,last);
}
reverse(suf[i].begin(),suf[i].end());
}
cout<<pre[n].back().se;
return 0;
}
```
:::
:::success[双指针版本]
```cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define mid ((l+r)>>1)
#define bmid ((l+r+1)>>1)
#define pb push_back
#define eb emplace_back
#define fswap(a,b) ((a)^=(b)^=(a)^=(b))
using namespace std;
using ll= long long;
#ifndef ONLINE_JUDGE
template <typename tp>
void _debug(const tp& t) {cerr<<t<<'\n';}
template <typename tp,typename... args>
void _debug(const tp& t, const args&... rest) {cerr<<t<<' ';_debug(rest...);}
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)
#else
#define debug(...) 0
#endif
#define int ll
const int N=200005,H=N<<2,inf=1000000000,mod=1000000007;
vector<pair<int,int> > vec[N];
vector<pair<int,int> > f[N],pre[N],suf[N];
int n,m,a[N];
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int x,y,i=1;i<=m;i++) {
cin>>x>>y;
vec[x].eb(i,y);
vec[x+1].eb(i,y);
}
f[0].eb(0,0),pre[0].eb(0,0),suf[0].eb(0,0);
for(int i=1;i<=n;i++) {
f[i].eb(0,pre[i-1].back().se+a[i]);
int p1=0,p2=0;
for(auto& t: vec[i]) {
const int j=t.fi,x=t.se;
while(p1+1<f[i-1].size()&&f[i-1][p1+1].fi<j) p1++;
while(p2<f[i-1].size()&&f[i-1][p2].fi<=j) p2++;
int tm=0;
tm=max(tm,pre[i-1][p1].se+x);
if(p2!=suf[i-1].size()) tm=max(tm,suf[i-1][p2].se+x);
f[i].eb(j,tm);
}
for(auto t: f[i])
debug(i,t.fi,t.se);
int last=0;
vector<pair<int,int> > ve;
for(auto t: f[i]) {
ve.pb(t);
last=max(last,t.se);
pre[i].eb(t.fi,last);
}
last=0;
reverse(ve.begin(),ve.end());
for(auto t: ve) {
last=max(last,t.se);
suf[i].eb(t.fi,last);
}
reverse(suf[i].begin(),suf[i].end());
}
cout<<pre[n].back().se;
return 0;
}
```
:::