A 限速（speed）
对于边权小于等于 \(k\) 的，尽量选大的，对于边权大于 \(k\) 的，尽量选小的，然后按这两个条件排序后 kruskal，如果边权小的能组成生成树，那么答案就是小于等于 \(k\) 的最大的数和第一个大于 \(k\) 的数的较小代价。否则最后的生成树代价就是答案。有六十分的数据边权全部小于等于 \(k\)，没判边界值挂 60pts。
B 酒鬼（drunkard）
观察发现要求奇偶性一致，容易想到分讨维护前驱后继得到 83pts 的做法，但是有 \(p_i=1\) 的情况，此时是否出发就很关键，如果没出发，\(p_i=1\) 是不受奇偶限制的。
所以直接考虑时刻维护最早和最晚的出发时间，并且检测相邻的合法性。
- 当距离大于时间时，不可达，直接不合法。
- 当前一个不在起点，但它的时间比最早还早，不合法。
- 当后一个不在起点，此时一定出发了，可以尝试更新最晚出发时间，直接把它当做出发后的第一个到达点更新即可，这样一定不会错。
- 如果前一个在起点，并且它的时间比最晚早，这时的奇偶性就可以不同，如果不同，更新最早的出发时间，此时合法。
- 排除掉上述所有情况后，再次根据奇偶性判断是否合法就可以了。
想清楚这些后，这道题就很好做了，这种小模拟的题以后还是要想清楚做出来。
#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10,inf=1e18;
std::unordered_map<int,int> mp;
int n,m,lates,te[N],minn,maxn=inf;
struct OP{int op,x,t;}o[N];
std::set<pii> s;
inline bool check(pii a,pii b){
int t=b.fi-a.fi,dis=std::abs(b.se-a.se);
if(dis>t)return false;
if(a.se!=1&&a.first<=minn)return false;
if(b.se!=1)maxn=std::min(maxn,b.fi-b.se+1);
if(a.se==1&&a.fi<=maxn){
if(t%2!=dis%2)minn=std::max(minn,a.fi+1);return true;
}
if(t%2!=dis%2)return false;
return true;
}
inline void sub(){
bool pd=0;
s.insert({0,1});
for(int i=1;i<=m;++i){
char ch[5];std::cin>>ch;
if(ch[1]=='l'){
int x,t;std::cin>>x>>t;
if(pd){continue;}
if(mp[t])if(mp[t]!=x){pd=1;continue;}
mp[t]=x;
auto it=s.insert({t,x}).first;
auto zc=it;--zc;
auto la=*zc,now=*it;
if(!check(la,now)){pd=1;continue;}
++it;if(it!=s.end()){
la=*it;if(!check(now,la)){pd=1;continue;}
}
}if(ch[1]=='i'){
if(pd){std::cout<<"bad\n";continue;}
std::cout<<minn<<'\n';
}if(ch[1]=='a'){
if(pd){std::cout<<"bad\n";continue;}
if(maxn==inf){std::cout<<"inf\n";continue;}
std::cout<<maxn<<'\n';
}
}
}
signed main(){
freopen("drunkard.in","r",stdin);freopen("drunkard.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
std::cin>>n>>m;
sub();
}
C1 距离（distance）
换题后的 C 题，确实放原题太水了。
首先如果直接看这个式子，大力分讨应该会得到一个树套树或者 CDQ 分治的三个 log 的做法，又复杂又难写，还不优秀，考虑化式子。
切比雪夫距离：\(\max(|x1-x2|,|y1-y2|)\)，曼哈顿距离：\(|x1-x2|+|y1-y2|\)。
曼哈顿距离转化：\(|x1-x2|+|y1-y2|=\max\{x1-x2+y1-y2,x1-x2+y2-y1,x2-x1+y1-y2,x2-x1+y2-y1\}=\max(|(x1+y1)-(x2+y2)|,|(x1-y1)-(x2-y2)|)\)，就转化成了 \((x+y,x-y)\) 的切比雪夫距离。
同理切比雪夫距离等同于 \((\frac{x+y}{2},\frac{x-y}{2})\) 的曼哈顿距离，证明分讨即可。
如果了解过一定的切比雪夫距离，就会很自然想到化式子了，\(\min(a,b)=a+b-\max(a,b)\)，后面一个就是切比雪夫距离了，设 \(p_i=\frac{a_i+b_i}{2},q_i=\frac{a_i-b_i}{2}\)，最后需要求：
由于点对本来就要乘 \(2\)，所以 \(p,q\) 不必除以 \(2\)，处理这四个绝对值自然想到分讨，dsu 套 BIT，时间复杂度 \(\mathcal{O}(n\log^2n)\)，且常数巨大，不太可能通过 5e5 的数据。
考虑如果在序列上处理绝对值该怎么做，一种就是上树状数组或者线段树分讨，还有一种更加简单，排完序后直接找前面后后面即可，这题也是同理，如果可以使节点的值有序，那么直接查前面和后面即可，\(ans[l,r]=ans[l,mid]+ans[mid+1,r]+sum[mid+1,r]\times cnt[l,mid]-sum[l,mid]\times cnt[mid+1,r]\)，如果我们可以一直保留这个序列，答案也就迎刃而解了，放弃 dsu，尝试把节点拍到线段树上，然后从下往上线段树合并即可，根节点就是答案，时间复杂度 \(\mathcal{O}(n\log n)\)。
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii std::pair<int,int>
#define eb emplace_back
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+10,mod=1e9+7;
std::mt19937 myrand(std::chrono::high_resolution_clock::now().time_since_epoch().count());
inline int R(int n){return myrand()%n+1;}
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
inline void Min(int &x,int y){x=std::min(x,y);}
inline void Max(int &x,int y){x=std::max(x,y);}
inline void W(int &x,int y){x=(x+y)%mod;}
int n,temp[4][N],val[4][N],ans[N],tot,ANS[N],root[N],sm[N];
std::vector<int> e[N];
struct TREE{int res,sum,ls,rs,cnt;}t[N*20];
inline void clear(){for(int i=1;i<=tot;++i)t[i]={0,0,0,0,0};tot=0;for(int i=1;i<=n;++i)root[i]=0;}
inline void update(int p){
t[p].res=t[t[p].ls].res+t[t[p].rs].res+t[t[p].rs].sum*t[t[p].ls].cnt%mod-t[t[p].ls].sum*t[t[p].rs].cnt%mod;
t[p].sum=(t[t[p].ls].sum+t[t[p].rs].sum)%mod;t[p].cnt=t[t[p].ls].cnt+t[t[p].rs].cnt;
}
inline void insert(int &p,int l,int r,int pos,int x){
if(!p)p=++tot;
if(l==r){W(t[p].sum,x),t[p].cnt++;return ;}
int mid=l+r>>1;if(pos<=mid)insert(t[p].ls,l,mid,pos,x);
if(pos>mid)insert(t[p].rs,mid+1,r,pos,x);update(p);
}
inline int merge(int a,int b,int l,int r){
if(!a||!b)return a|b;
if(l==r){W(t[a].res,t[b].res),W(t[a].sum,t[b].sum),t[a].cnt+=t[b].cnt;return a;}
int mid=l+r>>1;
t[a].ls=merge(t[a].ls,t[b].ls,l,mid);
t[a].rs=merge(t[a].rs,t[b].rs,mid+1,r);
update(a);return a;
}
inline void dfs(int x,int fa,int id){
insert(root[x],1,n,val[id][x],temp[id][val[id][x]]);
for(int v:e[x]){
if(v==fa)continue;
dfs(v,x,id);
root[x]=merge(root[x],root[v],1,n);
}
ans[x]=t[root[x]].res;
}
signed main(){
freopen("in.in","r",stdin);freopen("out.out","w",stdout);
freopen("distance.in","r",stdin);freopen("distance.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();for(int i=1;i<n;++i){int u=read(),v=read();e[u].eb(v);e[v].eb(u);}
for(int i=1;i<=n;++i){
int a=read(),b=read();val[0][i]=a,val[1][i]=b,val[2][i]=a+b,val[3][i]=a-b;
temp[0][i]=a,temp[1][i]=b,temp[2][i]=a+b,temp[3][i]=a-b;
}
for(int i=0;i<4;++i){
std::sort(temp[i]+1,temp[i]+n+1);int cnt=std::unique(temp[i]+1,temp[i]+n+1)-temp[i]-1;
for(int j=1;j<=n;++j)val[i][j]=std::lower_bound(temp[i]+1,temp[i]+cnt+1,val[i][j])-temp[i];
}
dfs(1,0,0);for(int i=1;i<=n;++i)ANS[i]=ans[i]*2%mod;clear();
dfs(1,0,1);for(int i=1;i<=n;++i)W(ANS[i],ans[i]*2);clear();
dfs(1,0,2);for(int i=1;i<=n;++i)W(ANS[i],-ans[i]);clear();
dfs(1,0,3);for(int i=1;i<=n;++i)W(ANS[i],-ans[i]),W(ANS[i],mod),std::cout<<ANS[i]<<'\n';
}
赛时两个 dfs 函数的名写错了，挂了 60pts。
C2 单峰数列（peak）
原题解中的 C 题，大体就是拿线段树维护一个序列区间的单调性，支持区间加，没有任何深意。
D 选拔方案
不会
标签：std,ch,48,int,mid,long,CSP,模拟,define From： https://www.cnblogs.com/Ishar-zdl/p/18469441