题解
T1 wine
考虑转化成原花费减总优惠的形式。原花费是 $an+bm$，对于总优惠，我们将问题转化成一个有 $n+m$ 个点，$k$ 条边的图，每条边的边权是 $d_i$，我们要购买全部而且总优惠最大，也就是让用到的 $d_i$ 总和最大。
这样问题就转化成了求图上的最大生成树森林，转成负权求最小生成树森林即可。
#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=5e5+5,inf=1e18;
int n,m,k,a,b,ans,dis[N],vis[N],cnt;
struct node{
int v,w;
bool operator<(const node &b)const{
return w>=b.w;
}
};
vector<node> g[N];
priority_queue<node> q;
int prim(int s){
ans=0;
q.push({s,0});
dis[s]=0;
while(!q.empty()){
int u=q.top().v,w=q.top().w;
q.pop();
if(vis[u]) continue;
vis[u]=1;
cnt++;
ans+=w;
for(int i=0;i<g[u].size();i++){
int x=g[u][i].v,y=g[u][i].w;
if(dis[x]>y){
dis[x]=y;
q.push({x,y});
}
}
}
return ans;
}
int solve(){
for(int i=1;i<=n+m;i++) dis[i]=inf;
int res=0;
for(int i=1;i<=n+m;i++) if(!vis[i]) res+=prim(i);
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k>>a>>b;
for(int i=1,u,v,w;i<=k;i++){
cin>>u>>v>>w;
g[u].pb({n+v,-w});
g[n+v].pb({u,-w});
}
cout<<n*a+b*m+solve();
return 0;
}T2 flower
电线杆的倾倒就是两个区间修改，每个区间内价值的期望要乘上这棵树倾倒在这个区间的概率，用线段树维护区间乘法。
对于小花，花的美丽值乘上这个点不被砸到的概率就是该小花对答案的贡献，使用线段树单点查询。
数据范围比较大还有负数，离散化即可。
#include<bits/stdc++.h>
#define int long long
#define db double
#define endl '\n'
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const int N=5e5+5;
db t[N<<2],ans;
int n,m,a[N],h[N],l[N],r[N],b[N],tot,bb[N],z[N];
void update(int x,int l,int r,int L,int R,db k){
if(L<=l&&r<=R){
t[x]*=k/100.0l;
return ;
}
if(L<=mid) update(ls(x),l,mid,L,R,k);
if(R>mid) update(rs(x),mid+1,r,L,R,k);
}
db query(int x,int l,int r,int L){
if(l==r) return t[x];
if(L<=mid) return query(ls(x),l,mid,L)*t[x];
else return query(rs(x),mid+1,r,L)*t[x];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=0;i<(N<<2);i++) t[i]=1;
for(int i=1;i<=n;i++){
cin>>a[i]>>h[i]>>l[i]>>r[i];
b[++tot]=a[i]-h[i];
b[++tot]=a[i]+h[i];
b[++tot]=a[i]-1;
b[++tot]=a[i]+1;
}
for(int i=1;i<=m;i++){
cin>>bb[i]>>z[i];
b[++tot]=bb[i];
}
sort(b+1,b+tot+1);
int len=unique(b+1,b+tot+1)-b-1;
for(int i=1;i<=n;i++){
update(1,1,len,lower_bound(b+1,b+len+1,a[i]-h[i])-b,lower_bound(b+1,b+len+1,a[i]-1)-b,100.0l-l[i]);
update(1,1,len,lower_bound(b+1,b+len+1,a[i]+1)-b,lower_bound(b+1,b+len+1,a[i]+h[i])-b,100.0l-r[i]);
}
for(int i=1;i<=m;i++) ans+=query(1,1,len,lower_bound(b+1,b+len+1,bb[i])-b)*z[i];
cout<<fixed<<setprecision(12)<<ans;
return 0;
}T3 array
显然操作一的每个点修改次数总和不会太多。
证明一下。
考虑一次操作的时候同时操作了 $a_i$ 和 $a_j$（设 $j>i$），它们分别会变成 $a_i+i$ 和 $a_j+j$，$a_j$ 比 $a_i$ 多增加了 $j-i$。它们会再次被同时操作需要 $i\mid (j-i)$ 且要单独对 $a_i$ 进行 $\dfrac{j-i}{i}$ 次操作。所以操作一的每个点修改次数总和较少，大概在 $n+q$ 级别。
所以我们考虑暴力维护操作一，用 map<int,set<int>> 维护“值 $\to$ 下标集合”的映射，每次修改暴力把 set 里的元素迁移到新值。
对于操作二，我们要求区间 $[l, r]$ 内不同值个数，等于区间内有多少个位置 $i$ 满足 $pre_i < l$，其中 $pre_i$ 表示位置 $i$ 左边第一个与 $a_i$ 相同的位置，不存在则为 $0$。这个分块维护即可。
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+5,B=700;
int n,q,nb,pv[N],a[N];
map<int,set<int> > mp;
vector<int> blk[N/B+5];
void upd(int pos,int np){
if(pv[pos]==np) return;
int b=(pos-1)/B;
auto &v=blk[b];
int idx=lower_bound(v.begin(),v.end(),pv[pos])-v.begin();
v.erase(v.begin()+idx);
idx=lower_bound(v.begin(),v.end(),np)-v.begin();
v.insert(v.begin()+idx,np);
pv[pos]=np;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
mp[a[i]].insert(i);
}
for(auto &kv:mp){
int last=0;
for(int p:kv.second){
pv[p]=last;
last=p;
}
}
nb=(n+B-1)/B;
for(int i=1;i<=n;i++) blk[(i-1)/B].push_back(pv[i]);
for(int i=0;i<nb;i++) sort(blk[i].begin(),blk[i].end());
while(q--){
int op;
cin>>op;
if(op==1){
int x;
cin>>x;
if(!mp.count(x)) continue;
vector<int> pos(mp[x].begin(),mp[x].end());
mp.erase(x);
for(int i:pos){
int nv=x+i;
auto &st=mp[nv];
auto it=st.lower_bound(i);
int s=(it==st.end()?0:*it);
int p=(it==st.begin()?0:*prev(it));
st.insert(i);
upd(i,p);
if(s) upd(s,i);
}
}else{
int l,r;
cin>>l>>r;
int bl=(l-1)/B,br=(r-1)/B;
int ans=0;
if(bl==br){
for(int i=l;i<=r;i++) if(pv[i]<l) ans++;
}else{
for(int i=l;i<=min(n,(bl+1)*B);i++) if(pv[i]<l) ans++;
for(int i=br*B+1;i<=r;i++) if(pv[i]<l) ans++;
for(int b=bl+1;b<br;b++){
auto &v=blk[b];
ans+=lower_bound(v.begin(),v.end(),l)-v.begin();
}
}
cout<<ans<<endl;
}
}
return 0;
}T4 mex
考虑 $\text{mex}$ 只可能有 $0,1,2$ 三种，我们要让总答案尽可能大，就是尽可能让路径的 $\text{mex}$ 为 $2$，也就是尽量让更多的路径都出现 $0$ 和 $1$。容易想到贪心交替染色。但是交替染色的贪心是假的。可以被菊花连菊花的图卡掉，此时的最优解是两个菊花中心染 $1$ 其余点染 $0$。
考虑正难则反。一条路径的 $\text{mex}$ 不是 $2$ 当且仅当这条路径上的点权全部一样。树上所有的路径数量是 $\dfrac{n(n+1)}{2}$，所有路径的答案都为 $2$ 总答案就是 $n(n+1)$。一个大小为 $k$，颜色为 $0$ 的连通块会让答案减少 $\dfrac{i(i+1)}{2}$，而一个大小为 $k$，颜色为 $1$ 的连通块会让答案减少 $i(i+1)$。
考虑树上 dp。设 $dp_{u,i,0/1}$ 代表点 $u$ 的子树内，点 $u$ 所在的连通块大小为 $i$，颜色为 $0/1$，答案最少要减少多少。
子树合并的时候转移就是：
$dp_{u,i,0}=\min(dp_{u,i,0}+\min_{j}\{dp_{v,j,1}\},\min_{j}\{dp_{u,j,0}+dp_{v,i-j,0}+i(i-j))$
$dp_{u,i,1}=\min(dp_{u,i,1}+\min_{j}\{dp_{v,j,0}\},\min_{j}\{dp_{u,j,1}+dp_{v,i-j,1}+2i(i-j))$
但是这样 dp 时空都是 $O(n^2)$ 的，显然会爆炸。
期望得分 $20$。
考虑一个连通块太大肯定是不优的。我们可以回想交替染色的贪心。贪心不一定是最优的，所以我们的答案一定不会比贪心大（这里的答案指减去的部分）。
对于交替染色的贪心，所有长度大于 $2$ 的路径的 $\text{mex}$ 都是 $2$，而长度为 $1$ 的路径，大概有 $\dfrac{n}{2}$ 个点是 $0$，$\text{mex}$ 是 $1$，剩下的 $\dfrac{n}{2}$ 个点是 $1$，$\text{mex}$ 是 $0$。所以减少的答案约是 $n(n+1)-(\dfrac{n}{2}\times n(n-1)+\dfrac{n}{2})=\dfrac{3n}{2}$。
对于一个大小为 $i$ 的连通块，对于减少的答案的贡献是 $i^2$ 级别的。因为答案一定不会大于贪心，所以 $i^2\le \dfrac{3n}{2}$，也就是 $i\le \dfrac{\sqrt{6n}}{2}$。所以我们找连通块上界只要到 $\dfrac{\sqrt{6n}}{2}$ 就行了，时空变为 $O(n\sqrt n)$。
但是空间显然是开不下。
期望得分 $60$。
考虑到每个点的 dp 只需要用到子节点的 dp 值，所以一个点被用于求解父亲之后可以直接释放空间反复利用。
空间复杂度变为 $O(n)$。
期望得分 $100$。