我决定每天都写随笔。
大抵是觉得自己太菜了吧。
\(10611\)：
A.
为什么赛时不会呢？
每条管道没有流量或者有单向的流量，每个点处流入的流量之和等于流出的流量之和。
这句话的意思是说对于一个点，至多有一条与之连接的边可以不查询。
所以想到对于那些不查询的边，构成了一片森林。
为使得总代价尽可能的小，我们可以让不查询的森林的全职总和尽可能的大，于是变成了一道最大生成森林。
负权边特殊处理一下即可。
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define ll long long
int n,m,tot;
struct edge{
int x,y,w;
}e[N];
int fa[N];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
bool cmp(edge a,edge b){ return a.w>b.w; }
ll ans;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
if(w<0) ans+=w;
else e[++tot]={x,y,w};
}
sort(e+1,e+tot+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=tot;i++){
int x=find(e[i].x),y=find(e[i].y);
if(x==y){
ans+=e[i].w;
continue;
}
fa[x]=y;
}
printf("%lld",ans);
return 0;
}
B.
有傻逼赛时写了个双 \(\log\) 巨大麻烦的做法因为数组开小狂砍 \(40 pts\) ，是谁呢。
先说一下我的思路。
一开始的时候我拓扑排序，直接放，对拍发现被 hack 了。
6
2 5 4 2 4 2
2 1
3 2
4 2
5 1
6 2
这样会输出 \(10\)，但实际上答案是 \(9\) 。
考虑按照 \(a_i+dep_i\) 从大到小排序，最大的尽可能的先放，只可能在 \([0,n-1]\) 的时刻出发。
对于一个点，它要在它子树内所有节点放完之后才能放，所以我们在这个节点上挂一段区间 \([l,r]\) 表示这个节点的子树应该在 \([l,r]\) 的顺序里出发。
然后线段树求一下距离最近的被标记过的祖先节点，这就是 这道题 。
先放一下 \(O(n^2)\) 的代码。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,ans;
int a[N],t[N];
int dep[N],dfn[N],siz[N],f[N],tot;
vector<int> g[N];
int l[N],r[N],vis[N];
void dfs(int x,int fa){
dep[x]=dep[fa]+1;
dfn[x]=++tot;
siz[x]=1,f[x]=fa;
for(auto y:g[x]) if(y!=fa) dfs(y,x),siz[x]+=siz[y];
}
struct node{ int x,id; }b[N];
bool cmp(node x,node y){ return x.x>y.x; }
int query(int x){
while(!vis[x]) x=f[x];
return x;
}
void modify(int x){
int c=siz[x];
while(!vis[x]) siz[x]-=c,x=f[x];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[i]=i;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dep[0]=-1;
dfs(1,0);
for(int i=1;i<=n;i++) b[i]={a[i]+dep[i],i};
sort(b+1,b+n+1,cmp);
vis[0]=1;
for(int i=1;i<=n;i++){
int id=b[i].id,x=query(id);
l[id]=l[x],r[id]=l[id]+siz[id]-1;
ans=max(ans,r[id]+b[i].x);
l[x]+=siz[id];
modify(id);
vis[id]=1;
}
printf("%d",ans);
return 0;
}
优化完之后是 \(O(n \log ^2 n)\) 的。
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,ans;
int a[N];
int dep[N],siz[N],f[N],mxson[N];
int dfn[N],top[N],pos[N],tot;
vector<int> g[N];
void dfs1(int x,int fa){
dep[x]=dep[fa]+1;
siz[x]=1,f[x]=fa;
for(auto y:g[x]){
if(y==fa) continue;
dfs1(y,x);
siz[x]+=siz[y];
if(siz[mxson[x]]<siz[y]) mxson[x]=y;
}
}
void dfs2(int x,int topf){
dfn[x]=++tot;
pos[tot]=x;
top[x]=topf;
if(!mxson[x]) return;
dfs2(mxson[x],topf);
for(auto y:g[x]) if(y!=f[x]&&y!=mxson[x]) dfs2(y,y);
}
struct node{ int x,id; }b[N];
bool cmp(node x,node y){ return x.x>y.x; }
struct tree{
int l,r,siz,d;
}t[N*4];
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
t[p].siz=t[p].d=0;
if(l==r){
t[p].siz=siz[pos[l]];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
int query(int p,int x){
if(t[p].l==t[p].r) return t[p].siz;
int mid=(t[p].l+t[p].r)>>1;
int res=t[p].siz;
if(x<=mid) res+=query(p<<1,x);
else res+=query(p<<1|1,x);
return res;
}
void modify(int p,int l,int r,int v){
if(t[p].l==l&&t[p].r==r){
t[p].siz+=v;
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) modify(p<<1,l,r,v);
else if(l>mid) modify(p<<1|1,l,r,v);
else modify(p<<1,l,mid,v),modify(p<<1|1,mid+1,r,v);
}
void add(int x,int y,int v){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(1,dfn[top[x]],dfn[x],v);
x=f[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
modify(1,dfn[y],dfn[x],v);
}
void update(int p,int l,int r,int x){
if(t[p].l==l&&t[p].r==r){
if(dep[t[p].d]<dep[x]) t[p].d=x;
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) update(p<<1,l,r,x);
else if(l>mid) update(p<<1|1,l,r,x);
else update(p<<1,l,mid,x),update(p<<1|1,mid+1,r,x);
}
int q(int p,int x){
if(t[p].l==t[p].r) return t[p].d;
int ans=t[p].d;
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid){
int t=q(p<<1,x);
if(dep[t]>dep[ans]) ans=t;
}else{
int t=q(p<<1|1,x);
if(dep[t]>dep[ans]) ans=t;
}
return ans;
}
int l[N],r[N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dep[0]=-1;
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
for(int i=1;i<=n;i++) b[i]={a[i]+dep[i],i};
sort(b+1,b+n+1,cmp);
for(int i=1;i<=n;i++){
int id=b[i].id;
int s=query(1,dfn[id]);
int x=q(1,dfn[id]);
l[id]=l[x],r[id]=l[id]+s-1;
ans=max(ans,r[id]+b[i].x);
l[x]+=s;
add(x,id,-s);
update(1,dfn[id],dfn[id]+siz[id]-1,id);
}
printf("%d",ans);
return 0;
}
很小丑，直接二分可以做到 \(O(n \log n)\) 。
C.
题解很清楚了。
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5;
#define pii pair<int,int>
#define ll long long
int n,m;
vector<pii> g[N];
int a[N];
struct tree{
int l,r;
ll f,val,tag;
}t[N*4];
void pushup(int p){
t[p].f=max(t[p<<1].f,t[p<<1|1].f);
t[p].val=max(t[p<<1].val,t[p<<1|1].val);
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
t[p].f=t[p].val=t[p].tag=0;
if(l==r){
t[p].val=t[p].f=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void pushdown(int p){
if(t[p].tag>t[p<<1].tag){
t[p<<1].tag=t[p].tag;
t[p<<1].f=max(t[p<<1].f,t[p<<1].val+t[p].tag);
}
if(t[p].tag>t[p<<1|1].tag){
t[p<<1|1].tag=t[p].tag;
t[p<<1|1].f=max(t[p<<1|1].f,t[p<<1|1].val+t[p].tag);
}
}
void modify(int p,int l,int r,int v){
if(t[p].l==l&&t[p].r==r){
if(v>t[p].tag){
t[p].tag=v;
t[p].f=max(t[p].f,t[p].val+v);
}
return;
}
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) modify(p<<1,l,r,v);
else if(l>mid) modify(p<<1|1,l,r,v);
else modify(p<<1,l,mid,v),modify(p<<1|1,mid+1,r,v);
pushup(p);
}
int stk[N],tp;
ll ans[N];
ll query(int p,int l,int r){
if(t[p].l==l&&t[p].r==r) return t[p].f;
pushdown(p);
int mid=(t[p].l+t[p].r)>>1;
if(r<=mid) return query(p<<1,l,r);
else if(l>mid) return query(p<<1|1,l,r);
else return max(query(p<<1,l,mid),query(p<<1|1,mid+1,r));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
g[l].push_back({r,i});
}
build(1,1,n);
for(int i=n;i>=1;i--){
for(int j=tp;j>=1;j--){
if(j!=tp&&a[stk[j+1]]>=a[i]||2*stk[j]-i>n) break;
modify(1,2*stk[j]-i,n,a[i]+a[stk[j]]);
}
while(tp&&a[i]>=a[stk[tp]]) tp--;
stk[++tp]=i;
for(auto y:g[i]) ans[y.second]=query(1,i,y.first);
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
return 0;
}