A 商品
对于任意一组相邻的数 \((l,r)\ (l\le r)\)，可以发现，不管怎么压缩，都会有 \(l\le r\)，也就是说，相邻两个数的大小关系是不变的
那么我们就可以把 \(\sum(|\max-\min|)\) 拆出来，变成
\[\sum(\max-\min)=\sum(\max)-\sum(\min) \]所以我们可以每对数里的 \(\max\) 和 \(\min\) 都分别提出来
提出来之后求和就很容易了，我们只需要分别做两次 lower_bound ，分成三个区间求和（全为 \(l\)，全为 \(r\)，其他）就行了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,d;
int a[400001];
int Bsum[400001],Ssum[400001];
int B[400001],S[400001];
vector<int>L;
int solve(int l){
int b1=lower_bound(B+1,B+n,l)-B;
int b2=lower_bound(B+1,B+n,l+d)-B;
while(b2==n or B[b2]>l+d) b2--;
int s1=lower_bound(S+1,S+n,l)-S;
int s2=lower_bound(S+1,S+n,l+d)-S;
while(s2==n or S[s2]>l+d) s2--;
return (l*(b1-1)+Bsum[b2]-Bsum[b1-1]+(l+d)*(n-1-b2))
-(l*(s1-1)+Ssum[s2]-Ssum[s1-1]+(l+d)*(n-1-s2));
}
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
cin>>n>>d;
for(int i=1;i<=n;++i){
cin>>a[i];
L.push_back(a[i]);
if(a[i]-d>0) L.push_back(a[i]-d);
}
for(int i=1;i<=n-1;++i){
B[i]=max(a[i],a[i+1]);
S[i]=min(a[i],a[i+1]);
}
sort(B+1,B+n);
sort(S+1,S+n);
sort(L.begin(),L.end());
for(int i=1;i<=n-1;++i){
Bsum[i]=Bsum[i-1]+B[i];
Ssum[i]=Ssum[i-1]+S[i];
}
int ans=0;
for(int l:L){
ans=max(ans,solve(l));
}
cout<<ans<<endl;
}
赛时 10k 美丽代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,d;
namespace d_{
int n,d;
int a[200001],b[200001];
int ans,nowl,nowr;
int valcnt[200001];
int cntsum[200001];
int to_val[200001];
int cnt;
int up,down;
inline bool fixr(){
while(nowr<=cnt and to_val[nowr]<to_val[nowl]+d) nowr++;
if(nowr>cnt) return false;
return true;
}
inline int fixed(int a,int l,int r){
l=to_val[l];r=to_val[r];
if(a<=l) return l;
if(a>=r) return r;
return a;
}
int main(){
scanf("%d %d",&n,&d);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
n=unique(a+1,a+n+1)-a;
for(int i=1;i<=n;++i){
b[i]=a[i];
}
sort(b+1,b+n+1);
for(int i=1;i<=n;++i){
if(i==1 or b[i]!=b[i-1]){
to_val[++cnt]=b[i];
}
valcnt[cnt]++;
}
nowl=1,nowr=1;fixr();
for(int i=1;i<=n;++i){
cntsum[i]=cntsum[i-1]+valcnt[i];
if(i!=n) ans+=abs(fixed(a[i],nowl,nowr)-fixed(a[i+1],nowl,nowr));
}
down=valcnt[1];
up=cntsum[n]-cntsum[nowr];
int res=ans;
cout<<"res ("<<to_val[nowl]<<","<<to_val[nowr]<<") "<<res<<endl;
//[to_val[nowl],to_val[nowl]+d]
for(nowl=2;nowl<=cnt;++nowl){
int orl=nowr;if(!fixr()) break;
res+=up*(to_val[nowr]-to_val[orl])-down*(to_val[nowl]-to_val[nowl-1]);
down+=valcnt[nowl];
up=cntsum[n]-cntsum[nowr];
cout<<"res ("<<to_val[nowl]<<","<<to_val[nowr]<<") "<<res<<endl;
if(res>ans){
ans=res;
}
}
cout<<ans<<endl;
}
}
inline int _fixed(int a,int l,int r){
if(a<=l) return l;
if(a>=r) return r;
return a;
}
int a[400001],b[400001];
class BIT{
private:
long long d[100001],di[100001],s[100001];
inline int lowbit(int x){
return x&-x;
}
void change(long long *c,int x,int y){
while(x<=n){
c[x]+=y;
x+=lowbit(x);
}
}
long long sum(long long *c,int x){
long long ans=0;
while(x>0){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
long long sum_(int end){
return s[end]+(end+1)*sum(d,end)-sum(di,end);
}
public:
int n;
void clear(){
memset(d,0,sizeof(d));
memset(di,0,sizeof(di));
memset(s,0,sizeof(s));
}
long long sum(int l,int r){
return sum_(r)-sum_(l-1);
}
void change(int x,int y,int changevalue){
change(d,x,changevalue);
change(d,y+1,-changevalue);
change(di,x,changevalue*x);
change(di,y+1,-changevalue*(y+1));
}
void make_sum(int id,int x){
s[id]=s[id-1]+x;
}
long long sum(int id){
return sum(id,id);
}
void change(int id,int changevalue){
change(id,id,changevalue);
}
};
map<int,int>mp;
int dx[200001];
/*
2 5 d=4
x y d l r
2 5 = 1 5
2 5 = 2 6
3 5 - 3 7
4 5 - 4 8
5 5 - 5 9
6 6 = 6 10
7 7 = 7 11
2 5 d=2
x y d l r
2 3 1 1 3 in up
2 4 + 2 4 down in
3 5 = 3 5
4 5 - 4 6
5 5 - 5 7
6 6 = 6 8 down down
7 7 = 7 9
*/
vector<int>lo;
vector<int>lo2;
int fixed(int p,int val,int valp){
int ans=0;
if(p<=val){
ans+=valp-val;
}
if(p>val and p<=valp){
ans+=valp-p;
}
if(p>valp and p<=val+d);
if(p>val+d and p<=valp+d){
ans+=p-(val+d);
}
if(p>valp+d){
ans+=valp-val;
}
return ans;
}
/*
3 1 4 1 5 9 2 6
1 4 : 3 1 4 1 4 4 2 4
2 3 3 3 0 2 2 15
I D I D U U I U
- - - + +
2 5 : 3 2 4 2 5 5 2 5
1 2 2 3 0 3 3 14
3 6 : 3 3 4 3 5 6 3 6
0 1 1 2 1 3 3 11
4 7 : 4 4 4 4 5 7 4 6
0 0 0 1 2 3 2 8
*/
int m[400001];
int dx[400001];
int ori[400001];
int maxn;
namespace bl{
void main(){
int ans=0,res=0;
for(int l=1;l+d<=maxn;++l){
res=0;
for(int i=1;i<=n-1;++i){
res+=abs(_fixed(a[i],l,l+d)-_fixed(a[i+1],l,l+d));
}
ans=max(ans,res);
}
cout<<ans<<endl;
}
}
namespace zj{
int main(){
scanf("%d %d",&n,&d);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
m[i]=a[i]+d;
maxn=max(a[i],maxn);
}
for(int i=1;i<=n-1;++i){
for(int j=min(a[i],a[i+1])+1;j<=max(a[i],a[i+1]);++j){
dx[j]++;
}
for(int j=min(m[i],m[i+1])+1;j<=max(m[i],m[i+1]);++j){
dx[j]--;
}
}
for(int i=1;i<=maxn;++i){
// cout<<dx[i]<<endl;
}
int ans=0,res=0;
for(int i=1;i<=d;++i) ans+=dx[i];
res=ans;
for(int i=d+1;i<=maxn;++i){
res+=dx[i];
ans=max(ans,res);
}
cout<<ans<<endl;
bl::main();
// maxd=(int)lo2.size()-1;
// for(int i=1;i<=n-1;++i){
// if(a[i]==a[i+1]) continue;
// int minn=min(a[i],a[i+1]);
// int maxn=a[i]+a[i+1]-minn;
// for(int j=1;j<=(int)lo2.size()-1;++j){
// int val=lo2[j],valp=lo2[j+1];
// dx[i]+=fixed(maxn,val,valp)-fixed(minn,val,valp);
// }
// }
// for(int i=1;i<=tmp;++i){
// cout<<dx[i]<<endl;
// }
}
}
namespace tree{
struct tree{
int l,r;
int sum;
int lazy;
}t[800001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void build(int id,int l,int r){
t[id].l=l;t[id].r=r;
if(l==r) return;
int mid(l,r);
build(tol,l,mid);
build(tor,mid+1,r);
}
void pushdown(int id){
if(t[id].lazy){
t[tol].lazy+=t[id].lazy;
t[tor].lazy+=t[id].lazy;
t[tol].sum+=t[id].lazy*(t[tol].r-t[tol].l+1);
t[tor].sum+=t[id].lazy*(t[tor].r-t[tor].l+1);
t[id].lazy=0;
}
}
void change(int id,int l,int r,int k){
if(l<=t[id].l and t[id].r<=r){
t[id].sum+=k*(t[id].r-t[id].l+1);
t[id].lazy+=k;
return;
}
if(r<=t[tol].r){
change(tol,l,r,k);
}
else if(l>=t[tor].l){
change(tor,l,r,k);
}
else{
change(tol,l,t[tol].r,k);
change(tor,t[tor].l,r,k);
}
}
int ask(int id,int p){
if(t[id].l==t[id].r){
return t[id].sum;
}
pushdown(id);
if(p<t[tol].r){
return ask(tol,p);
}
return ask(tor,p);
}
}
using namespace tree;
int cnt;
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
scanf("%lld %lld",&n,&d);
// for(int i=1;i<=n;++i){
// scanf("%d",&a[i]);
// if(!mp.count(a[i])){
// mp[a[i]]=++cnt;
// ori[cnt]=a[i];
// }
// a[i]=mp[a[i]];
// m[i]=ori[a[i]]+d;
// maxn=max(ori[a[i]],maxn);
// }
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
b[++cnt]=a[i];
b[++cnt]=a[i]+d;
}
sort(b+1,b+cnt+1);
maxn=unique(b+1,b+cnt+1)-b;
for(int i=1;i<=maxn;++i){
ori[i]=b[i];
mp[b[i]]=i;
}
for(int i=1;i<=n;++i){
m[i]=mp[a[i]+d];
a[i]=mp[a[i]];
}
// for(int i=1;i<=n;++i){
// cout<<a[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;++i){
// cout<<m[i]<<" ";
// }
// cout<<endl;
for(int i=1;i<=n-1;++i){
for(int j=min(a[i],a[i+1])+1;j<=max(a[i],a[i+1]);++j){
dx[j]+=ori[j]-ori[j-1];
}
for(int j=min(m[i],m[i+1])+1;j<=max(m[i],m[i+1]);++j){
dx[j]-=ori[j]-ori[j-1];
}
}
// for(int i=1;i<=maxn;++i){
// cout<<dx[i]<<endl;
// }
int ans=0,res=0;
// for(int i=1;i<=d;++i) ans+=dx[i];
// res=ans;
for(int i=1;i<=maxn;++i){
res+=dx[i];
ans=max(ans,res);
}
cout<<ans<<endl;
// bl::main();
// maxd=(int)lo2.size()-1;
// for(int i=1;i<=n-1;++i){
// if(a[i]==a[i+1]) continue;
// int minn=min(a[i],a[i+1]);
// int maxn=a[i]+a[i+1]-minn;
// for(int j=1;j<=(int)lo2.size()-1;++j){
// int val=lo2[j],valp=lo2[j+1];
// dx[i]+=fixed(maxn,val,valp)-fixed(minn,val,valp);
// }
// }
// for(int i=1;i<=tmp;++i){
// cout<<dx[i]<<endl;
// }
}
int a[400001];
int Bsum[400001],Ssum[400001];
int B[400001],S[400001];
vector<int>L;
int solve(int l){
// cout<<"solve ["<<l<<" "<<l+d<<"]"<<endl;
int b1=lower_bound(B+1,B+n,l)-B;
int b2=lower_bound(B+1,B+n,l+d)-B;
while(b2==n or B[b2]>l+d) b2--;
int s1=lower_bound(S+1,S+n,l)-S;
int s2=lower_bound(S+1,S+n,l+d)-S;
while(s2==n or S[s2]>l+d) s2--;
// cout<<"find ["<<b1<<" "<<b2<<"] ["<<s1<<" "<<s2<<"]"<<endl;
// cout<<"sum "<<(l*(b1-1)+Bsum[b2]-Bsum[b1-1]+(l+d)*(n-1-b2))<<" and "<<(l*(s1-1)+Ssum[s2]-Ssum[s1-1]+(l+d)*(n-1-s2))<<endl;
return (l*(b1-1)+Bsum[b2]-Bsum[b1-1]+(l+d)*(n-1-b2))
-(l*(s1-1)+Ssum[s2]-Ssum[s1-1]+(l+d)*(n-1-s2));
}
/*
solve [3 6]
find [1 5] [7 8]
sum 34 and 4
30
*/
signed main(){
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
cin>>n>>d;
for(int i=1;i<=n;++i){
cin>>a[i];
L.push_back(a[i]);
if(a[i]-d>0) L.push_back(a[i]-d);
}
for(int i=1;i<=n-1;++i){
B[i]=max(a[i],a[i+1]);
S[i]=min(a[i],a[i+1]);
}
sort(B+1,B+n);
sort(S+1,S+n);
sort(L.begin(),L.end());
for(int i=1;i<=n-1;++i){
Bsum[i]=Bsum[i-1]+B[i];
Ssum[i]=Ssum[i-1]+S[i];
}
// for(int i=1;i<=n-1;++i){
// cout<<B[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n-1;++i){
// cout<<S[i]<<" ";
// }
// cout<<endl;
int ans=0;
for(int l:L){
// cout<<l<<" "<<solve(l)<<endl;
ans=max(ans,solve(l));
}
cout<<ans<<endl;
}
B 价值
我不会（老实）
去 Ratio 的博客 里沉淀了一下
沉淀半天啥也没沉淀出来
把我的胶体讲一下:
首先 \(f_{n,0/1,0/1/2,0/1/2}\)，定义的是考虑 \(n\) 的子树的匹配方案，第一个 \(0/1\) 里 \(0\) 表示当前点不在匹配中，第二个 \(0/1/2\) 分别表示当前节点的子树中 \(dfs\) 序最小的叶节点在当前匹配中/会在当前匹配中/不在当前匹配中，第三个表示的是最大的叶节点
首先我们可以预处理出节点的最大/最小叶节点，这个跑一边搜就行
然后考虑树形 DP，我们做两遍 DP，因为考虑到这个图里是有环的，因此做环形处理，第一遍强制从第一个叶节点和最后一个叶节点的连边处断开环，第二遍强制连上，取一个加和
这个 g 数组实际上只是个中转数组，不明白为啥不直接在 f 上改
然后看 DP 的具体内容
假设我们已经求出了 \(u\) 的所有子节点的答案，现在我们需要统计 \(u\) 处的答案
因为输入数据保证编号是一个合法的 dfs 序，因此，编号最小的子节点总是意味着当前子树中编号最小的叶节点在编号最小的子节点中
由于连边需要至少两个边的判断，所以特殊处理最小子节点
-
可以直接向最小的子节点连边，这要求该子节点不能连边
-
可以不向最小子节点连边，由最小子节点所有状态继承
-
连接当前节点，一种情况是当前节点已经相连，我们只需要枚举情况统计即可。这里我们只考虑当前节点的最大叶节点和子节点的最小叶节点，我们在从小到大枚举该节点的子节点的时候，最多只会遇到一个子节点，使得当前节点的最大叶节点与该子节点的最小叶节点在叶节点编号的序列上恰好相邻，当遇到这样的状态时，我们即可对当前节点进行连边，因此我们尝试枚举所有的这种状态，这里的分讨情况多是因为我们需要考虑已经经过这个状态，正在这个状态和尚未进行这个状态三种情况，其实大体都是一样的，大家可以五个一组来看
-
当前节点已经与更小的子节点连边，而当前枚举叶节点尚未连边，当前节点的最大叶节点和子节点的最小叶节点尚未连接
-
当前节点已经与更小的子节点连边，而当前枚举叶节点尚未连边，当前节点的最大叶节点和子节点的最小叶节点已连接
-
当前节点已经与更小的子节点连边，而当前枚举叶节点尚未连边，当前节点的最大叶节点和子节点的最小叶节点已连接，但是并不是当前节点的最大叶节点和子节点的最小叶节点相连，而是当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点与后一个相邻节点相连
-
当前节点已经与更小的子节点连边，而当前枚举叶节点尚未连边，当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点尚未连接
-
当前节点已经与更小的子节点连边，而当前枚举叶节点尚未连边，子节点的最小叶节点与后一个相邻节点相连,当前节点的最大叶节点尚未连接
-
当前节点已经与更小的子节点连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点尚未连接
-
当前节点已经与更小的子节点连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接
-
当前节点已经与更小的子节点连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接，但是并不是当前节点的最大叶节点和子节点的最小叶节点相连，而是当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点与后一个相邻节点相连
-
当前节点已经与更小的子节点连边，当前枚举叶节点已经连边，当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点尚未连接
-
当前节点已经与更小的子节点连边，当前枚举叶节点已经连边，子节点的最小叶节点与后一个相邻节点相连,当前节点的最大叶节点尚未连接
-
当前节点和当前枚举叶节点都没连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点尚未连接
-
当前节点和当前枚举叶节点都没连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接
-
当前节点和当前枚举叶节点都没连边，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接，但是并不是当前节点的最大叶节点和子节点的最小叶节点相连，而是当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点与后一个相邻节点相连
-
当前节点和当前枚举叶节点都没连边，当前枚举叶节点已经连边，当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点尚未连接
-
当前节点和当前枚举叶节点都没连边，当前枚举叶节点已经连边，子节点的最小叶节点与后一个相邻节点相连,当前节点的最大叶节点尚未连接
-
-
不连接当前节点，那么我们无需寻找具有上述状态的时刻
- 当前节点未连边，枚举的子节点连不连边均可，然后分别处理当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点尚未连接，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接，当前枚举叶节点已经连边，当前节点的最大叶节点和子节点的最小叶节点已连接，但是并不是当前节点的最大叶节点和子节点的最小叶节点相连，而是当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点与后一个相邻节点相连，当前枚举叶节点已经连边，当前节点的最大叶节点与前一个相邻节点相连，子节点的最小叶节点尚未连接，当前枚举叶节点已经连边，子节点的最小叶节点与后一个相邻节点相连,当前节点的最大叶节点尚未连接五种情况即可
看着比较多，实际上就是比较多，但是只要你写出前五个就可以把脑子丢掉无脑写了
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
int n,minn=1e9,maxn;
int fa[100001];
int f[100001][2][3][3];
int g[2][3][3];
int ans;
vector<int>e[100001];
void dfs(int now){
if(!e[now].size()){
minn=min(minn,now);
maxn=max(maxn,now);
return;
}
for(int i:e[now]){
dfs(i);
}
}
void solve(int now,bool flag){
if(flag and (now==minn or now==maxn)){
f[now][1][2][2]=(minn!=maxn);
return;
}
if(!e[now].size()){
f[now][0][0][0]=f[now][1][1][2]=f[now][1][2][1]=1;
return;
}
for(int i:e[now]){
solve(i,flag);
}
int v=e[now][0];
for(int j=0;j<=2;++j){
for(int k=0;k<=2;++k){
f[now][0][j][k]=(f[v][0][j][k]+f[v][1][j][k])%p,
f[now][1][j][k]=f[v][0][j][k];
}
}
for(int i=1;i<=e[now].size()-1;++i){
v=e[now][i];
for(int j=0;j<=2;++j){
for(int k=0;k<=2;++k){
g[1][j][k]=(f[now][1][j][0]*f[v][0][0][k]%p+f[now][1][j][1]*f[v][0][1][k]%p+f[now][1][j][2]*f[v][0][2][k]%p+f[now][1][j][2]*f[v][0][0][k]%p+f[now][1][j][0]*f[v][0][2][k]%p+f[now][1][j][0]*f[v][1][0][k]%p+f[now][1][j][1]*f[v][1][1][k]%p+f[now][1][j][2]*f[v][1][2][k]%p+f[now][1][j][2]*f[v][1][0][k]%p+f[now][1][j][0]*f[v][1][2][k]%p+f[now][0][j][0]*f[v][0][0][k]%p+f[now][0][j][1]*f[v][0][1][k]%p+f[now][0][j][2]*f[v][0][2][k]%p+f[now][0][j][2]*f[v][0][0][k]%p+f[now][0][j][0]*f[v][0][2][k]%p)%p;
g[0][j][k]=(f[now][0][j][0]*f[v][0][0][k]%p+f[now][0][j][1]*f[v][0][1][k]%p+f[now][0][j][2]*f[v][0][2][k]%p+f[now][0][j][2]*f[v][0][0][k]%p+f[now][0][j][0]*f[v][0][2][k]%p+f[now][0][j][0]*f[v][1][0][k]%p+f[now][0][j][1]*f[v][1][1][k]%p+f[now][0][j][2]*f[v][1][2][k]%p+f[now][0][j][2]*f[v][1][0][k]%p+f[now][0][j][0]*f[v][1][2][k]%p)%p;
}
}
for(int op=0;op<=1;++op){
for(int j=0;j<=2;++j){
for(int k=0;k<=2;++k){
f[now][op][j][k]=g[op][j][k];
}
}
}
}
}
signed main(){
freopen("value.in","r",stdin);
freopen("value.out","w",stdout);
cin>>n;
for(int i=2;i<=n;++i){
cin>>fa[i];
e[fa[i]].push_back(i);
}
for(int i=1;i<=n;++i){
sort(e[i].begin(),e[i].end());
}
dfs(1);
solve(1,0);
ans=(f[1][0][2][0]+f[1][0][0][2]+f[1][0][2][2]+f[1][0][0][0]+f[1][1][2][0]+f[1][1][0][2]+f[1][1][2][2]+f[1][1][0][0])%p;
memset(f,0,sizeof f);
solve(1,1);
ans=(ans+f[1][0][2][2]+f[1][1][2][2])%p;
cout<<ans<<endl;
}