怎么又开一个 ds 专题啊/yun
A - 如何正确地排序
以前写的，把以前写的题解贺过来。
正难则反，总贡献减去不会成为 \(\min/\max\) 的数。 \(B_i+B_j\) 不会产生贡献的条件就是存在 \(A_i+A_j,C_i+C_j\) 满足 \(\begin{cases}A_i+A_j\le B_i+B_j\\B_i+B_j\le C_i+C_j\end{cases}\)，移项可得 \(\begin{cases}A_i-B_i\le B_j-A_j\\B_i-C_i\le C_j-B_j\end{cases}\)。两边的项都只和 \(i,j\) 有关系，可以直接算出来。枚举 \(A,B,C\)，这就是一个二维数点。注意相等会算两遍，我们可以钦定行数大的更大。因为有负数，要开两倍空间。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18,SIZ=2e5;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct BIT{
int c[400005];
void clear(){memset(c,0,sizeof(c));}
void add(int x,int k){
for(;x<=SIZ<<1;x+=x&-x)c[x]+=k;
}
int ask(int x){
int res=0;for(;x;x-=x&-x)res+=c[x];
return res;
}
}Tr;
struct Node{
int op,x,y,id;
}q[400005];
int cmp(Node x,Node y){
return (x.x!=y.x)?(x.x<y.x):(x.op<y.op);
}
int n,m,ans,a[5][200005];
void calc(int x,int y,int z){
Tr.clear();
for(int i=1;i<=m;i++){
q[i]=(Node){0,(a[x][i]-a[y][i])+(x>y)+SIZ,(a[y][i]-a[z][i])+(y>z)+SIZ,i};
q[i+m]=(Node){1,-(a[x][i]-a[y][i])+SIZ,-(a[y][i]-a[z][i])+SIZ,i};
}
sort(q+1,q+m*2+1,cmp);
for(int i=1;i<=m*2;i++){
if(q[i].op==0)Tr.add(q[i].y,1);
else ans-=a[y][q[i].id]*Tr.ask(q[i].y);
}
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
a[i][j]=read(),ans+=a[i][j]*2*m;
for(int i=n+1;i<=4;i++)for(int j=1;j<=m;j++)
a[i][j]=a[i-n][j],ans+=a[i][j]*2*m;
n=4;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)
if(i!=j&&i!=k&&j!=k)calc(i,j,k);
printf("%lld",ans);
return 0;
}
L - Souvenirs
典，考虑所有 \(i<j,a_i\ge a_j\) 的 \((i,j)\) 的贡献，\(a_i\le a_j\) 的贡献可以令 \(a_i\gets -a_i\) 再做一遍。枚举 \(i\)，向左找到第一个 \(j\) 满足 \(a_j\ge a_i\)，注意到此时一对 \((k,i),k<j<i\) 可能有用的条件是 \(a_i\le a_k\le\lfloor\dfrac{a_i+a_j}{2}\rfloor\)，因为如果更靠近 \(a_j\)，那么如果一个询问包含 \((k,i)\)，那 \((k,j)\) 也一定可选，且一定比 \((k,i)\) 更优。如果 \(a_k>a_j\) 那更不行了。于是一个位置只会有不超过 \(\log V\) 对有用的答案，找出来之后扫描线即可，复杂度 \(\mathcal{O}(n\log n\log V)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
const int inf=1e18,V=1e9;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct segtree{
#define ls (lc[p])
#define rs (rc[p])
#define lson l,mid,ls
#define rson mid+1,r,rs
int T,lc[4000005],rc[4000005],mx[4000005];
void clear(){
for(int i=0;i<=T;i++)lc[i]=rc[i]=0,mx[i]=-inf;
T=0;
}
void pushup(int p){
mx[p]=max(mx[ls],mx[rs]);
}
void add(int l,int r,int &p,int x,int v){
if(!p)p=++T,mx[p]=-inf;
if(l==r){mx[p]=max(mx[p],v);return;}
int mid=(l+r)>>1;
if(x<=mid)add(lson,x,v);
else add(rson,x,v);
pushup(p);
}
int ask(int l,int r,int p,int L,int R){
if(!p)return -inf;
if(L<=l&&r<=R)return mx[p];
int mid=(l+r)>>1,res=-inf;
if(L<=mid)res=max(res,ask(lson,L,R));
if(R>mid)res=max(res,ask(rson,L,R));
return res;
}
#undef lson
#undef rson
#undef ls
#undef rs
}Tr;
int a[100005],ql[300005],qr[300005],ans[300005];vector<int>v[100005],t[100005];
signed main(){
int n=read(),root=0;
for(int i=1;i<=n;i++)a[i]=read();
int m=read();
for(int i=1;i<=m;i++)ql[i]=read(),qr[i]=read(),v[qr[i]].push_back(i),ans[i]=inf;
Tr.clear();root=0;
for(int i=1;i<=n;i++){
int j=V;
while(a[i]<=j){
int p=Tr.ask(0,V,root,a[i],j);if(p<=0)break;
t[i].push_back(p);
if(a[p]==a[i])break;
j=(a[i]+a[p])>>1;
}
Tr.add(0,V,root,a[i],i);
}
Tr.clear();root=0;
for(int i=1;i<=n;i++){
for(auto x:t[i])Tr.add(1,n,root,x,a[i]-a[x]);
for(auto x:v[i])ans[x]=min(ans[x],-Tr.ask(1,n,root,ql[x],qr[x]));
}
for(int i=1;i<=n;i++)a[i]=V-a[i],t[i].clear();
Tr.clear();root=0;
for(int i=1;i<=n;i++){
int j=V;
while(a[i]<=j){
int p=Tr.ask(0,V,root,a[i],j);if(p<=0)break;
t[i].push_back(p);
if(a[p]==a[i])break;
j=(a[i]+a[p])>>1;
}
Tr.add(0,V,root,a[i],i);
}
Tr.clear();root=0;
for(int i=1;i<=n;i++){
for(auto x:t[i])Tr.add(1,n,root,x,a[i]-a[x]);
for(auto x:v[i])ans[x]=min(ans[x],-Tr.ask(1,n,root,ql[x],qr[x]));
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
return 0;
}