好久没写博客了？
今晚写爽。
P5311 成都七中
这有黑？
对于一个点 \(x\)，设其子树任意一点为 \(y\)。
我们可以求出这 \(x\rightarrow y\) 这条路径经过节点的的 \(l,r\)。
遍历 \(x\) 的子树，我们可以得到一些三元组 \((l,r,c)\) 表示 \(x\) 所属连通块包含了 \(l,r\) 这些节点，就有一个颜色 \(c\)。
那么就可以二维数点处理询问了。
注意到我们只考虑了 \(x\) 子树内的节点。事实上，对于 \(y\) 的一个询问 \(l_y,r_y\)，如果 \(l_y\leq l,r \leq r_y\) 时，我们可以直接挂到 \(x\) 上解决。
点分治即可，复杂度 \(O(n\log^2 n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,a[N],ans[N],lst[N],c[N];
vector<int> G[N];
struct node{
int op,l,r,id;
bool operator<(const node &x)const{
return l==x.l?op<x.op:l>x.l;
}
};
vector<node> vec,q[N];
void upd(int x,int v) {for(;x<=n;x+=x&-x) c[x]+=v;}
int qsum(int x) {int r=0;for(;x;x^=x&-x) r+=c[x];return r;}
int rt,sz[N],mx[N],vis[N];
void getrt(int u,int f,int sum)
{
sz[u]=1,mx[u]=0;
for(int v:G[u])
{
if(v==f||vis[v]) continue;
getrt(v,u,sum);
sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
}
mx[u]=max(mx[u],sum-sz[u]);
if(!rt||mx[u]<mx[rt]) rt=u;
}
void getcol(int u,int f,int l,int r)
{
vec.push_back({0,l,r,a[u]});
for(auto x:q[u]) if(!ans[x.id]&&x.l<=l&&r<=x.r) vec.push_back(x);
for(int v:G[u]) if(v!=f&&!vis[v]) getcol(v,u,min(l,v),max(r,v));
}
void solve(int u,int sum)
{
vis[u]=1;
vec.clear();
getcol(u,u,u,u);
sort(vec.begin(),vec.end());
for(auto &[op,l,r,id]:vec)
if(!op) {if(r<lst[id]) upd(lst[id],-1),upd(lst[id]=r,1);}
else ans[id]=qsum(r);
for(auto i:vec) if(!i.op&&lst[i.id]!=n+1) upd(lst[i.id],-1),lst[i.id]=n+1;
for(int v:G[u])
{
if(vis[v]) continue;
rt=0;int t=sz[v]<sz[u]?sz[v]:sum-sz[u];
getrt(v,u,t),solve(rt,t);
}
}
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0,f=1;char c=nc();
for(;!isdigit(c);c=nc()) if(c=='-') f=-1;
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) a[i]=rd(),lst[i]=n+1;
for(int i=1;i<n;i++)
{
int u=rd(),v=rd();
G[u].push_back(v),G[v].push_back(u);
}
for(int i=1;i<=m;i++)
{
int l=rd(),r=rd(),x=rd();
q[x].push_back({1,l,r,i});
}
getrt(1,0,n);solve(rt,n);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
CF1651F Tower Defense
分块后就是萌萌题了。
考虑一个怪经过，会清空一些前缀块，然后某个块走一些。
注意到 \(t\leq 2\times 10^5\)，我们可以预处理出 \(s_{i,j}\) 表示块 \(i\) 在被清空后经过 \(j\) 秒恢复的魔力总和。
对于没有清空的块，我们暴力走。
那么每有一个怪，最多让一个块暴力算，所以复杂度是 \(O(n\sqrt n)\)。
由于直接预处理空间会爆，离线下来对于每个块分别处理即可，这也是经典套路了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5,B=450;
int n,q,k,lst,clr,m[N],c[N],r[N],t[N];
ll ans,h[N],s[N];
struct node{int c,r,t;} a[N];
void solve(int L,int R)
{
k=lst=clr=0;ll sc=0,sr=0;
for(int i=L;i<=R;i++) m[i]=c[i],sc+=c[i],sr+=r[i];
for(int i=L;i<=R;i++) a[++k]={c[i],r[i],c[i]/r[i]};
sort(a+1,a+1+k,[&](node a,node b){return a.t<b.t;});
for(int i=1,j=1;i<=t[q];i++) {s[i]=0;while(j<=k&&a[j].t<i) s[i]+=a[j].c-(i-1)*a[j].r,sr-=a[j].r,j++;s[i]+=s[i-1]+sr;}
for(int i=1;i<=q;i++)
{
if(!h[i]) continue;
int ti=t[i];ll now=0;
if(clr) now=s[ti-lst];
else for(int j=L;j<=R;j++) now+=min((ll)c[j],m[j]+(ll)(ti-lst)*r[j]);
if(h[i]>=now) h[i]-=now,clr=1;
else
{
if(clr) for(int j=L;j<=R;j++) m[j]=0;clr=0;
for(int j=L;j<=R;j++) m[j]=min((ll)c[j],m[j]+(ll)(ti-lst)*r[j]);
for(int j=L;j<=R;j++) if(m[j]>=h[i]) {m[j]-=h[i],h[i]=0;break;} else h[i]-=m[j],m[j]=0;
}
lst=ti;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;for(int i=1;i<=n;i++) cin>>c[i]>>r[i];
cin>>q;for(int i=1;i<=q;i++) cin>>t[i]>>h[i];
for(int i=0;i<=n/B;i++) solve(max(1,i*B),min(n,i*B+B-1));
for(int i=1;i<=q;i++) ans+=h[i];
cout<<ans<<'\n';
}
P5163 WD 与地图
码力题。
删边是不好做的，考虑反过来，维护加边。
那么加入一条边可能会合并两个 SCC，线段树合并就可以做了。
注意到这不是树，所以需要启发式合并。
当然也可能在之后合并。
对于一条边 \((u_i,v_i)\)，如果我们可以求出使 \(u_i\) 所在 SCC 与 \(v_i\) 所在 SCC 的合并时间 \(mt_i\)，那么这条边的贡献就是在 \(mt_i\) 这个时间合并这两个 SCC。
同样，再维护一条边的加入时间 \(t_i\)，如果一条边没被删除过，那么加入时间 \(t_i=q+1\)。
问题转化为如何求这 \(m\) 条边的 \(mt_i\)。
可以发现 \(mt_i\) 是单调不降的，因为越往前加入的边越多。
考虑整体二分。
定义 \(solve(l,r,ll,rr)\) 表示当前答案区间为 \([l,r]\)，在这个区间的边的区间为 \([ll,rr]\)。
具体流程如下：
-
如果 \(l=r\)，直接 \(\forall i\in[ll,rr],mt_i=l\)，结束递归。
-
\(mid \leftarrow \frac{(l+r)}{2}\)，加入编号在 \([ll,rr]\) 中 \(t> mid\) 的边。注意，我们之前已经加入了 \([rr+1,m]\) 这些边，也就是说，要保留加入 \([rr+1,m]\) 这些边后，SCC 的信息。这可以用并查集维护每个点属于哪个 SCC。
-
在新建出的图中跑 tarjan，用并查集合并 SCC。这只需要遍历 流程 2 中出现过的点。
-
清除 2. 中加入的边。为什么可以直接清除？如果某条边对左边递归有用，那么会被直接划分到左边。否则，这条边连接的两点已属于一个 SCC，对合并新的 SCC 没有用。
-
遍历 \([ll,rr]\) 内的边，如果一条边 \(t>mid\) 且两点属于一个 SCC，划分到右边，否则划分到左边。
-
当前保留了加入时间在 \([mid+1,r]\) 这些边后的 SCC 信息（并查集维护的），\(solve(l,mid,ll,ll')\)。
-
撤销 3. 中跑 tarjan 时的并查集操作。
-
\(solve(mid+1,r,rr',rr)\)。
时间复杂度 \(O(n\log^2 n)\)。
整体二分可能有点抽象，不如看代码，破天荒加了许多注释（本来想加注释的，但感觉自己写得挺清晰不需要）。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
long long ans[N];
int n,m,q,k,tot,V,a[N],fa[N],sz[N],lsh[N*2];
vector<int> G[N];
vector<pair<int,int>> stk;
map<pair<int,int>,int> id;
struct node{int op,a,b,t;} b[N*2];
struct edge{int x,y,t,mt;} e[N],_e[N];
int find(int x) {return fa[x]==x?x:find(fa[x]);}
int rk(int x) {return lower_bound(lsh+1,lsh+1+V,x)-lsh;}
void merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
sz[x]+=sz[y],fa[y]=x,stk.push_back({x,y});
}
int dn,top,dfn[N],low[N],in[N],stk2[N];
void tarjan(int u)
{
dfn[u]=low[u]=++dn;
stk2[++top]=u,in[u]=1;
for(int v:G[u])
{
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
int v;
do{
v=stk2[top--];
merge(u,v),in[v]=0;
}while(v!=u);
}
}
void solve(int l,int r,int ll,int rr)
{
if(l==r) {for(int i=ll;i<=rr;i++) e[i].mt=l;return;}
int mid=l+r>>1;vector<int> p;
for(int i=ll;i<=rr;i++)
if(e[i].t>mid)
{
int x=find(e[i].x),y=find(e[i].y);
G[x].push_back(y);p.push_back(x),p.push_back(y);
}
int now=stk.size();
for(int i:p) if(!dfn[i]) tarjan(i);
dn=0;for(int i:p) G[i].clear(),dfn[i]=0;
int k1=ll,k2=rr;
for(int i=ll;i<=rr;i++)
if(e[i].t>mid&&find(e[i].x)==find(e[i].y)) _e[k2--]=e[i];
else _e[k1++]=e[i];
for(int i=ll;i<=rr;i++) e[i]=_e[i];
solve(l,mid,ll,k1-1);
while(stk.size()>now)
{
auto [x,y]=stk.back();
sz[x]-=sz[y],fa[y]=y;
stk.pop_back();
}
solve(mid+1,r,k2+1,rr);
}
#define mid (l+r>>1)
long long sum[N*40];
int nd,rt[N],lc[N*40],rc[N*40],cnt[N*40];
void upd(int &k,int x,int op,int l=1,int r=V)
{
if(!k) k=++nd;
sum[k]+=lsh[x]*op,cnt[k]+=op;
if(l==r) return;
x<=mid?upd(lc[k],x,op,l,mid):upd(rc[k],x,op,mid+1,r);
}
long long qsum(int k,int x,int l=1,int r=V)
{
if(!k) return 0;
if(l==r) return 1ll*x*lsh[l];
return x<=cnt[rc[k]]?qsum(rc[k],x,mid+1,r):sum[rc[k]]+qsum(lc[k],x-cnt[rc[k]],l,mid);
}
int t_merge(int p,int q)
{
if(!p||!q) return p+q;
sum[p]+=sum[q],cnt[p]+=cnt[q];
lc[p]=t_merge(lc[p],lc[q]);
rc[p]=t_merge(rc[p],rc[q]);
return p;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>a[i],lsh[++V]=a[i];
for(int i=1;i<=m;i++)
{
int u,v;cin>>u>>v;
e[i]={u,v,q+1},id[{u,v}]=i;
}
for(int i=1;i<=q;i++)
{
int op,x,y;cin>>op>>x>>y;
if(op==1) e[id[{x,y}]].t=i;
if(op==2) b[++tot]={2,x,y,i},a[x]+=y,lsh[++V]=a[x];
if(op==3) b[++tot]={3,x,y,i};
}
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
solve(0,q+1,1,m);
for(int i=1;i<=m;i++) b[++tot]={1,e[i].x,e[i].y,e[i].mt};
sort(b+1,b+1+tot,[&](node a,node b){return a.t==b.t?a.op<b.op:a.t>b.t;});
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
sort(lsh+1,lsh+1+V);
V=unique(lsh+1,lsh+1+V)-lsh-1;
for(int i=1;i<=n;i++) upd(rt[i],rk(a[i]),1);
for(int i=1;i<=tot;i++)
{
auto &[op,x,y,_]=b[i];
int fx=find(x),fy;
if(op==1)
{
fy=find(y);
if(fx==fy) continue;
if(sz[fx]<sz[fy]) swap(x,y),swap(fx,fy);
sz[fx]+=sz[fy],fa[fy]=fx,rt[fx]=t_merge(rt[fx],rt[fy]);
}
if(op==2) upd(rt[fx],rk(a[x]),-1),upd(rt[fx],rk((a[x]-=y)),1);
if(op==3) ans[++k]=qsum(rt[fx],min(cnt[rt[fx]],y));
}
while(k) cout<<ans[k--]<<'\n';
}
P5610 大学
虽然是 23 年写的题，但哥们今晚上写爽了。
先忽略 \(x=1\) 的操作。
可以发现一个位置进行 \(\log\) 操作后就会变为 1。
考虑用 vector 维护是 \(i\) 及 \(i\) 的倍数位置。
虽然 \(\max\{d(500000)\}\) 是 100 多，但这并不好笑，并不好卡满。
那么对于修改 \(x\)，定位到对应的 vector，先 lower_bound 第一个 \(\geq l\) 的位置，然后往后暴力修改就可以了。
但有可能操作完后他不再能满足条件，我们需要删除这个位置。
具体地，对于 vector 某个元素，我们再维护一下它的 \(nxt\) 表示对应 vector 内下一个满足要求的位置，如果不满足要求，就暴力往后跳，然后把路径上所有 \(nxt\) 都指向最后停下的位置。
容易发现这很对。
复杂度不算高，写得丑的话需要卡卡常。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll lans,c[N];
int n,m,V,a[N];
vector<int> t[N*5],v[N*5],nxt[N*5];
void upd(int x,int v) {for(;x<=n;x+=x&-x) c[x]+=v;}
ll qsum(int x) {ll r=0;for(;x;x^=x&-x) r+=c[x];return r;}
char buf[1<<15],*p1=buf,*p2=buf;
#define nc() (p1==p2&&(p2=buf+fread(p1=buf,1,1<<15,stdin),p1==p2)?-1:*p1++)
inline int rd()
{
int x=0;char c=nc();
for(;!isdigit(c);c=nc());
for(; isdigit(c);c=nc()) x=(x<<3)+(x<<1)+(c^48);
return x;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++) t[a[i]=rd()].push_back(i),V=max(V,a[i]),upd(i,a[i]);
for(int i=2;i<=V;i++)
{
for(int j=i;j<=V;j+=i) for(int x:t[j]) v[i].push_back(x);
stable_sort(v[i].begin(),v[i].end());
for(int j=0;j<v[i].size();j++) nxt[i].push_back(j+1);
}
while(m--)
{
int op=rd(),l=rd()^lans,r=rd()^lans,x;
if(op==1)
{
x=rd()^lans;
int i=lower_bound(v[x].begin(),v[x].end(),l)-v[x].begin();
while(i<v[x].size()&&v[x][i]<=r)
{
int j=v[x][i];
if(a[j]%x==0) upd(j,a[j]/x-a[j]),a[j]/=x;
j=nxt[x][i];
while(j<v[x].size()&&a[v[x][j]]%x) j=nxt[x][j];
while(i!=j) {int t=nxt[x][i];nxt[x][i]=j;i=t;}
}
}
else cout<<(lans=qsum(r)-qsum(l-1))<<'\n';
}
}
P6773 命运
先考虑一个的树形 dp。
假设当前考虑一条边 \((u,v)\)（假设 \(u\) 为 \(v\) 的父亲）。
\(v\) 的子树内可能有一些限制。
考虑一个限制 \((x,y)\)，其中 \(y\) 在 \(v\) 子树内。显然 \(dep_x\leq dep_u\)，否则这个限制无论如何也满足不了。
可以发现这些合法的限制都往上都会经过同一条链 \(1\rightarrow u\)，那么我们只需要记录限制中 \(\max\{dep_x\}\)，如果满足了这个限制，显然其余所有限制都能满足。
于是可以定义状态 \(f_{u,i}\) 表示考虑到子树 \(u\)，\(\max\{dep_x\}=i\) 的方案数，规定 \(i=0\) 表示满足所有限制。
\((u,v)\) 这条边权值为 1：
\(f_{u,i}\leftarrow f_{u,i}\sum_{0\leq j\leq dep_u} f_{v,j}\)
\((u,v)\) 这条边权值为 0：
\(f_{u,max(i,j)}\leftarrow \sum\limits_{0\leq i,j\leq dep_u} f_{u,i}\cdot f_{v,j}\)，即 \(f_{u,i}\leftarrow f_{u,i}\sum\limits_{0\leq j\leq i} f_{v,j}+f(v,i)\sum\limits_{0\leq j< i}f_{u,j}\)
记 \(g(u,i)=\sum\limits_{0\leq j\leq i} f_{u,i}\)
那么有：
\(f_{u,i}\leftarrow f_{u,i}(g_{v,dep_u}+g_{v,i})+f_{v,i}g_{u,i-1}\)
注意到叶子上有用的 \(f\) 只有一个，考虑线段树合并优化 dp，照着上面这个式子维护一下就可以了。
多么抽象。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+5,P=998244353;
int n,m,dep[N],lim[N];
vector<int> G[N];
void mul(int &x,int y) {x=x*y%P;}
void inc(int &x,int y) {if((x+=y)>=P) x-=P;}
void dfs0(int u,int f)
{
dep[u]=dep[f]+1;
for(int v:G[u]) if(v!=f) dfs0(v,u);
}
#define mid (l+r>>1)
int tot,rt[N],lc[N*20],rc[N*20],s[N*20],tag[N*20];
void pushdown(int k)
{
if(lc[k]) mul(s[lc[k]],tag[k]),mul(tag[lc[k]],tag[k]);
if(rc[k]) mul(s[rc[k]],tag[k]),mul(tag[rc[k]],tag[k]);
tag[k]=1;
}
void upd(int &k,int x,int v,int l=0,int r=n)
{
if(!k) tag[k=++tot]=1;
if(l==r) {inc(s[k],v);return;}
pushdown(k);
x<=mid?upd(lc[k],x,v,l,mid):upd(rc[k],x,v,mid+1,r);
s[k]=(s[lc[k]]+s[rc[k]])%P;
}
int qsum(int k,int x,int y,int l=0,int r=n)
{
if(!k) return 0;
if(l>=x&&r<=y) return s[k];
pushdown(k);int res=0;
if(x<=mid) res=qsum(lc[k],x,y,l,mid);
if(mid<y) inc(res,qsum(rc[k],x,y,mid+1,r));
return res;
}
int merge(int p,int q,int &s1,int &s2,int l=0,int r=n)
{
if(!p) {inc(s1,s[q]);mul(s[q],s2),mul(tag[q],s2);return q;}
if(!q) {inc(s2,s[p]);mul(s[p],s1),mul(tag[p],s1);return p;}
if(l==r)
{
int sp=s[p];
inc(s1,s[q]);
s[p]=(s[p]*s1+s[q]*s2)%P;
inc(s2,sp);
return p;
}
pushdown(p),pushdown(q);
lc[p]=merge(lc[p],lc[q],s1,s2,l,mid);
rc[p]=merge(rc[p],rc[q],s1,s2,mid+1,r);
s[p]=(s[lc[p]]+s[rc[p]])%P;
return p;
}
void dfs(int u,int f)
{
upd(rt[u],lim[u],1);
for(int v:G[u])
{
if(v==f) continue;
dfs(v,u);
int s1=qsum(rt[v],0,dep[u]),s2=0;
rt[u]=merge(rt[u],rt[v],s1,s2);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
G[u].push_back(v),G[v].push_back(u);
}
dfs0(1,0);
cin>>m;
while(m--)
{
int u,v;cin>>u>>v;
lim[v]=max(lim[v],dep[u]);
}
dfs(1,0);
cout<<qsum(rt[1],0,0);
}