我的代码在 init_dp() 调用线段树 Change 的时候 RE 了,一句指令都没有执行成功,求调。
菜鸡代码,码风垃圾,求轻喷。
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll Inf=-1e16;
const int N=3e5+12;
using pi=pair<int,ll> ;
vector<pi> fish[N];
vector<pi> FISH[N];
vector<pi> dp[N];
int _n_,_m_;
vector<int> _x_;
vector<int> _y_;
vector<int> _w_;
inline void init_FISH(){
for(int i=0;i<_n_;++i){
FISH[i].emplace_back(Inf,0);
ll sum=0;
for(pi f:fish[i]){
sum+=f.second;
FISH[i].emplace_back(f.first,sum);
}
}
}
inline ll get_FISH(int rowid,int id){
return lower_bound(FISH[rowid].begin(),FISH[rowid].end(),make_pair(id,-1ll))->second;
}
inline void init_dp_space(){
for(int i=0;i<=_n_;i++){
if(i!=0){
for(pi f1:fish[i-1]){
dp[i].emplace_back(f1.first,0);
}
}
if(i!=_n_){
for(pi f2:fish[i+1]){
dp[i].emplace_back(f2.first,0);
}
}
for(pi f3:fish[i]){
dp[i].emplace_back(f3.first,0);
}
}
}
struct segment_tree{
ll tr[N<<2];
vector<int> trash;
segment_tree(){
fill(tr,tr+(N<<2)+1,Inf);
trash.clear();
}
inline void upd(int k){
tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
inline void change(int k,int L,int R,int id,ll val){
if(L==id&&id==R){
tr[L]=val;
return;
}
int mid=(L+R)>>1;
if(id<=mid)change(k<<1,L,mid,id,val);
else change(k<<1|1,mid+1,R,id,val);
upd(k);
}
inline void Change(int id,ll val){
// cout<<"CCF_NOI "<<id<<'\_n_';
trash.emplace_back(id);
// cout<<"1 0 "<<_n_<<" "<<id<<" "<<val<<endl;
change(1,0,_n_,id,val);
}
inline ll quary(int k,int L,int R,int ql,int qr){
if(ql<=L&&R<=qr){
return tr[k];
}
int mid=(L+R)>>1;
ll ans=Inf;
if(ql<=mid)ans=max(ans,quary(k<<1,L,mid,ql,qr));
if(qr>mid) ans=max(ans,quary(k<<1|1,mid+1,R,ql,qr));
return ans;
}
inline ll Quary(int L,int R){
return quary(1,0,_n_,L,R);
}
inline void Clear(){
for(int f:trash)Change(f,Inf);
trash.clear();
}
}tr[2][2];
inline void init_dp(){
for(pi &f:dp[0]){
f.second=0;
// cout<<"GF="<<get_FISH(1,f.first)<<' '<<f.first<<endl;
tr[0][0].Change(f.first,f.second-get_FISH(1,f.first));
// cout<<"GF="<<get_FISH(0,f.first-1)<<endl;
tr[0][1].Change(f.first,f.second+get_FISH(0,f.first-1));
}
}
ll max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){
_n_=n,_m_=m,_x_=x,_y_=y,_w_=w;
// printf("E1\_n_");
for(int i=0;i<_m_;++i){
_y_[i]++;
fish[_x_[i]].emplace_back(_y_[i],_w_[i]);
}
// printf("E2\_n_");
fish[_n_].emplace_back(0,0);
for(int i=0;i<=_n_;++i){
sort(fish[i].begin(),fish[i].end());
}
// printf("E3\_n_");
init_FISH();
// printf("E4\_n_");
init_dp_space();
// printf("E5\_n_");
init_dp();
// printf("E6\_n_");
for(int i=1;i<=_n_;i++){
bool th=i&1,lst=th^1;
for(pi &f:dp[i]){
f.second=max(tr[lst][0].Quary(1,f.first)+get_FISH(i,f.second-1),tr[lst][1].Quary(f.first+1,_n_)-get_FISH(i-1,f.first));
tr[th][0].Change(f.first,f.second-get_FISH(i,f.first));
tr[th][1].Change(f.first,f.second+get_FISH(i-1,f.first));
}
tr[lst][0].Clear();
tr[lst][1].Clear();
}
// printf("E7\_n_");
return dp[_n_][0].second;
}
//int _n1,_m1;
//vector<int> _x1,_y1,_w1;
//int f;
//int main(){
// cin>>_n1>>_m1;
// for(int i=0;i<_m1;i++){
// cin>>f;
// _x1.emplace_back(f);
// }
// for(int i=0;i<_m1;i++){
// cin>>f;
// _y1.emplace_back(f);
// }
// for(int i=0;i<_m1;i++){
// cin>>f;
// _w1.emplace_back(f);
// }
// cout<<max_weights(_n1,_m1,_x1,_y1,_w1);
// return 0;
//}
/*
5 4
0 1 4 3
2 1 4 3
5 2 1 3
*/