T1 开挂
因为可以随便选 \(b\) ，所以可以先对 \(a\) \(b\) 排序。不难想到最优策略是尽量把操作集中到一个点上，再把较小的 \(b\) 分配给它。
因此应让开始偏小的 \(a\) 最终尽量大。这个倒序扫描就可以实现。中间会出现若干空隙，考虑最优策略，肯定是先将数填到最近的空隙里，用栈维护可以完成。
\(code:\)
T1
#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef long long LL; typedef long double LD;
typedef unsigned long long ULL; typedef double DB;
typedef pair<int,int> PII;
#define fi first
#define se second
#define mpr make_pair
#define int ULL
#define pb push_back
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
void write(int x,char sp){
char ch[50]; int len=0;
if(x<0) x=-x,putchar('-');
do{ ch[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);
}
void ckmin(int& x,int y){ x=x<y?x:y; }
void ckmax(int& x,int y){ x=x>y?x:y; }
} using namespace IO;
const int NN=1000010;
int n,ans,a[NN],b[NN];
int it,top,pre;
PII stk[NN];
vector<int>op;
signed main(){
freopen("openhook.in","r",stdin);
freopen("openhook.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
sort(a+1,a+n+1); sort(b+1,b+n+1);
pre=a[n];
for(it=n-1;a[it]==a[n];it--)
++pre,op.pb(pre-a[it]);
while(it){
int lst=it,cnt=-1;
if(a[it]<a[it+1]-1) stk[++top]=mpr(a[it]+1,a[it+1]-1);
while(a[it]==a[lst]) --it,++cnt;
while(cnt&&top){
while(cnt&&stk[top].fi<=stk[top].se)
--cnt,op.pb(stk[top].fi-a[lst]),++stk[top].fi;
if(stk[top].fi>stk[top].se) --top;
}
while(cnt) --cnt,++pre,op.pb(pre-a[lst]);
}
sort(op.begin(),op.end(),[](int x,int y)->bool{return x>y;});
for(int i=0;i<op.size();i++) ans+=op[i]*b[i+1];
write(ans,'\n');
return 0;
}
T2 叁仟柒佰万
发现序列中合法的 \(mex\) 值只能有一个，可以用桶找出这个 \(mex\) 。
考虑暴力 \(n^2\) DP，可以预处理出所有 \(mex\) 合法的区间，设 \(f_i\) 为当前最后一个区间右端点为 \(i\) 的方案数，转移时枚举右端点对应的左端点，将方案数加和。
在右端点 \(r\) 增加时，最靠右的合法左端点是单调不降的，因此预处理可以通过单调指针加桶 \(O(n)\) 完成。转移时，每个右端点的合法左端点一定是从 \(1\) 开始的一段连续点。前缀和优化可以达到 \(O(n)\) 。
\(code:\)
T2
# pragma GCC optimize(12)
#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef long long LL; typedef long double LD;
typedef unsigned long long ULL; typedef double DB;
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
void write(int x,char sp){
char ch[50]; int len=0;
if(x<0) x=-x,putchar('-');
do{ ch[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);
}
void ckmin(int& x,int y){ x=x<y?x:y; }
void ckmax(int& x,int y){ x=x>y?x:y; }
} using namespace IO;
const int NN=37000010,mod=1e9+7;
int t,n,mex,a[NN],f[NN];
int buc[NN];
int qmod(int a){ return a<0?(a+mod):(a>=mod?a-mod:a); }
int qpow(int a,int b,int res=1){
for(;b;b>>=1,a=1ll*a*a%mod)
if(b&1) res=1ll*res*a%mod;
return res;
}
void read_a(){
f[1]=-1;
if(n<37000000)
for(int i=1;i<=n;i++) buc[(a[i]=read())]=1,f[i]=-1;
else{
int x=read(),y=read();
for(int i=2;i<=n;i++)
buc[(a[i]=(1ll*a[i-1]*x+y+i)&262143)]=1,f[i]=-1;
}
while(buc[mex]) ++mex;
}
void clear(){
mex=0;
for(int i=1;i<=n;i++)
buc[i]=f[i]=buc[a[i]]=0;
}
void init(){
if(n<37000000) for(int i=1;i<=n;i++) buc[a[i]]=0;
else memset(buc,0,sizeof(buc));
int it=0,now=0,pos=0;
while(now!=mex){
++buc[a[++pos]];
while(buc[now]) ++now;
} --buc[a[pos]];
for(int i=pos;i<=n;i++){
++buc[a[i]];
while(buc[a[it+1]]>1||a[it+1]>mex)
++it,--buc[a[it]];
f[i]=it;
}
f[0]=buc[0]=1;
}
signed main(){
freopen("clods.in","r",stdin);
freopen("clods.out","w",stdout);
t=read();
while(t--){
n=read(); read_a();
if(!mex){ write(qpow(2,n-1),'\n'); goto nxt; }
init();
for(int i=1;i<=n;i++){
if(f[i]>=0) f[i]=buc[f[i]];
else f[i]=0;
buc[i]=qmod(buc[i-1]+f[i]);
}
write(f[n],'\n');
nxt: clear();
}
return 0;
}
T3 超级加倍
一个牛B的东西： \(kruscal\) 重构树。按点权大小建树，可以满足原树上路径 \((x,y)\) 上最大或最小值在重构树上为 \(x，y\) 的 \(lca\) 。
因此建出树 \(t1,t2\) ，分别为按点权递增，递减建出的重构树。那么要求的答案实际上就是满足 \(x\) 在 \(t1\) 中为 \(y\) 祖先，在 \(t2\) 中为 \(y\) 后代的点对 \((x,y)\) 个数。本质上是个偏序问题，求出 \(t1\) 中的 \(dfs\) 序，在 \(t2\) 中用树状数组维护祖先链并查询即可。
\(code:\)
T3
#include<bits/stdc++.h>
using namespace std;
namespace IO{
typedef long long LL; typedef long double LD;
typedef unsigned long long ULL; typedef double DB;
#define pb push_back
const int Mxdt=100000;
inline char gc(){
static char buf[Mxdt],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxdt,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
int t=0,f=0;char v=gc();
while(v<'0')f|=(v=='-'),v=gc();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=gc();
return f?-t:t;
}
void write(LL x,char sp){
char ch[50]; int len=0;
if(x<0) x=-x,putchar('-');
do{ ch[len++]=x%10+'0'; x/=10; }while(x);
for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);
}
void ckmin(int& x,int y){ x=x<y?x:y; }
void ckmax(int& x,int y){ x=x>y?x:y; }
} using namespace IO;
const int NN=2000010;
int n,idx,prt[NN],heade[NN],headx[NN],headn[NN];
int cnt,up[NN],dn[NN];
LL ans;
struct Edge{
int to,nex;
Edge(){}
Edge(int t,int x){ to=t; nex=x; }
}tx[NN<<1],tn[NN<<1],te[NN<<1];
void addx(int a,int b){
tx[++idx]=Edge(b,headx[a]); headx[a]=idx;
tx[++idx]=Edge(a,headx[b]); headx[b]=idx;
}
void addn(int a,int b){
tn[++idx]=Edge(b,headn[a]); headn[a]=idx;
tn[++idx]=Edge(a,headn[b]); headn[b]=idx;
}
void adde(int a,int b){
te[++idx]=Edge(b,heade[a]); heade[a]=idx;
te[++idx]=Edge(a,heade[b]); heade[b]=idx;
}
namespace DSU{
int FA[NN];
int getf(int x){ return FA[x]==x?x:FA[x]=getf(FA[x]); }
void merge(int x,int y){
x=getf(x); y=getf(y);
if(x==y) return;
FA[y]=x;
}
void build(){
idx=0;
for(int i=1;i<=n;i++) FA[i]=i;
for(int i=1;i<=n;i++)
for(int j=heade[i],v=te[j].to;j;j=te[j].nex,v=te[j].to)
if(v<i){ addx(i,getf(v)); merge(i,v); }
idx=0;
for(int i=1;i<=n;i++) FA[i]=i;
for(int i=n;i>=1;i--)
for(int j=heade[i],v=te[j].to;j;j=te[j].nex,v=te[j].to)
if(v>i){ addn(i,getf(v)); merge(i,v); }
}
} using namespace DSU;
namespace BIT{
LL c[NN];
void insert(int pos,int x){ while(pos<=n){ c[pos]+=x; pos+=pos&-pos; } }
LL query(int pos,LL x=0){ while(pos){ x+=c[pos]; pos-=pos&-pos; } return x; }
LL calc(int l,int r){ return query(r)-query(l-1); }
} using namespace BIT;
void dfsx(int s,int f){
ans+=calc(up[s],dn[s]);
insert(up[s],1);
for(int v,i=headx[s];i;i=tx[i].nex)
if((v=tx[i].to)!=f) dfsx(v,s);
insert(up[s],-1);
}
void dfsn(int s,int f){
up[s]=++cnt;
for(int v,i=headn[s];i;i=tn[i].nex)
if((v=tn[i].to)!=f) dfsn(v,s);
dn[s]=cnt;
}
signed main(){
freopen("charity.in","r",stdin);
freopen("charity.out","w",stdout);
n=read(); idx=read();
for(int a,i=2;i<=n;i++)
a=read(),adde(i,a);
build(); dfsn(1,0); dfsx(n,0);
write(ans,'\n');
return 0;
}