？怎么 12 月都过一半了？
C0425 【1202 A组】模拟测试
A 【1202 A组】景点游览
一个垃圾的 \(\mathcal{O}(n\sqrt{n})\) 做法。先缩点，然后拓扑，求出每个点能到达的所有点中最大的和最小的，记为 \(R_i\) 和 \(L_i\)。那么一段区间 \([l,r]\) 合法的条件就是 \(\min\limits_{i=l}^r L_i=l\land \max\limits_{i=l}^r R_i=r\)。可以 st 表预处理后二分出每个点作为 \(l\) 或 \(r\) 时对应的另一个端点的合法范围，那么只需要两个点都在对方的范围内就可以组成一个合法的区间。可以以右端点的合法区间为询问区间，跑莫队，需要区间加加单点查询，因为加的次数很多而询问只有 \(n\) 次，选择用 \(\mathcal{O}(1)\) 单点加 \(\mathcal{O}(\sqrt{n})\) 区间求和的分块来维护，复杂度 \(\mathcal{O}(n\sqrt{n})\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18,mod=1e9+7;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[600005];
int tot,head[300005];
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int cur,top,rc,dfn[300005],low[300005],st[300005],in[300005],L[300005],R[300005],bel[300005];
void tarjan(int u){
dfn[u]=low[u]=++cur;st[++top]=u,in[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
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;rc++;
L[rc]=inf,R[rc]=-inf;
do{
v=st[top--],in[v]=0;
bel[v]=rc;
L[rc]=min(L[rc],v);
R[rc]=max(R[rc],v);
}while(v!=u);
}
}
int deg[300005],Log[300005],f[22][300005],g[22][300005];
int askf(int l,int r){
if(l>r)return inf;
int o=Log[r-l+1];
return min(f[o][l],f[o][r-(1ll<<o)+1]);
}
int askg(int l,int r){
if(l>r)return -inf;
int o=Log[r-l+1];
return max(g[o][l],g[o][r-(1ll<<o)+1]);
}
int ll[300005],lr[300005],rl[300005],rr[300005];
struct Que{
int l,r,id;
}qu[300005];
int n,m,siz,num,Bel[300005],bl[605],br[605];
int cmp(Que x,Que y){
return Bel[x.l]<Bel[y.l]||(Bel[x.l]==Bel[y.l]&&((Bel[x.l]&1ll)?x.r<y.r:x.r>y.r));
}
struct Block{
int s1[300005],s2[605];
void Add(int x,int v){
if(1<=x&&x<=n)s1[x]=(s1[x]+v+mod)%mod,s2[Bel[x]]=(s2[Bel[x]]+v+mod)%mod;
}
void Add(int l,int r,int v){
if(l<=r)Add(l,v),Add(r+1,-v);
}
int ask(int l,int r){
if(Bel[l]==Bel[r]){
int res=0;
for(int i=l;i<=r;i++)res=(res+s1[i])%mod;
return res;
}
int res=0;
for(int i=l;i<=br[Bel[l]];i++)res=(res+s1[i])%mod;
for(int i=bl[Bel[r]];i<=r;i++)res=(res+s1[i])%mod;
for(int i=Bel[l]+1;i<=Bel[r]-1;i++)res=(res+s2[i])%mod;
return res;
}
}B;
void Add(int x){
B.Add(ll[x],lr[x],1);
}
void Del(int x){
B.Add(ll[x],lr[x],-1);
}
int ask(int l,int r){
return B.ask(l,r);
}
signed main(){
n=read(),m=read(),siz=(int)sqrt(n),num=(n+siz-1)/siz;
for(int i=1;i<=n;i++)Bel[i]=(i-1)/siz+1;
for(int i=1;i<=num;i++)bl[i]=(i-1)*siz+1,br[i]=min(n,i*siz);
for(int i=1,u,v;i<=m;i++)u=read(),v=read(),add(u,v);
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
vector<pair<int,int> >tmp;
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(bel[u]!=bel[v])tmp.push_back({bel[u],bel[v]});
}
}
tot=0;for(int i=1;i<=n;i++)head[i]=0;
for(auto x:tmp)add(x.second,x.first),deg[x.first]++;
queue<int>q;
for(int i=1;i<=rc;i++){
if(!deg[i])q.push(i);
}
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
L[v]=min(L[v],L[u]),R[v]=max(R[v],R[u]);
if((--deg[v])==0)q.push(v);
}
}
Log[1]=0;for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
for(int i=1;i<=n;i++)f[0][i]=L[bel[i]],g[0][i]=R[bel[i]];
for(int j=1;j<=Log[n];j++){
for(int i=1;i+(1ll<<j)-1<=n;i++){
f[j][i]=min(f[j-1][i],f[j-1][i+(1ll<<(j-1))]);
g[j][i]=max(g[j-1][i],g[j-1][i+(1ll<<(j-1))]);
}
}
for(int i=1;i<=n;i++){
int l=i,r=n,lp=i-1,rp=n+1;
while(l<=r){
int mid=(l+r)>>1;
if(askf(i,mid)>i)lp=mid,l=mid+1;
else r=mid-1;
}
l=i,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(askf(i,mid)<i)rp=mid,r=mid-1;
else l=mid+1;
}
ll[i]=lp+1,lr[i]=rp-1;
}
for(int i=1;i<=n;i++){
int l=1,r=i,lp=i+1,rp=0;
while(l<=r){
int mid=(l+r)>>1;
if(askg(mid,i)<i)lp=mid,r=mid-1;
else l=mid+1;
}
l=1,r=i;
while(l<=r){
int mid=(l+r)>>1;
if(askg(mid,i)>i)rp=mid,l=mid+1;
else r=mid-1;
}
rl[i]=rp+1,rr[i]=lp-1;
}
int cnt=0,ans=0;
for(int i=1;i<=n;i++){
if(rl[i]<=rr[i])qu[++cnt]={rl[i],rr[i],i};
}
sort(qu+1,qu+cnt+1,cmp);
for(int i=1,ql=1,qr=0;i<=cnt;i++){
while(ql>qu[i].l)Add(--ql);
while(qr<qu[i].r)Add(++qr);
while(ql<qu[i].l)Del(ql++);
while(qr>qu[i].r)Del(qr--);
ans=(ans+ask(1,qu[i].id))%mod;
}
printf("%lld\n",ans);
return 0;
}
坏了，赛时的做法好像很唐。
注意到如果一个点对应的合法区间存在，那么这个区间一定有一个端点是它自己！所以直接数点就行，这就是 \(\mathcal{O}(n\log n)\) 的了。
似乎还有分治的做法，不太会。
B 【1202 A组】人生画卷
C 【1202 A组】博弈游戏
P4694 [PA2013] Raper。鉴定为【模板】模拟费用流。
一眼的费用流。考虑每个 \(i\) 向所有 \(j\ge i\) 的 \(j+n\) 连一条免费边，然后原点向 \(i\) 连 \(a_i\) 的边，\(i+n\) 向汇点连 \(b_i\) 的边，限制一下最大流为 \(k\) 就行。注意到会向后缀连边，可以直接优化一下建图跑 flow，能获得 44pts。
考虑更强力的做法。这个费用流模型告诉我们，问题的答案关于 \(k\) 有凸性，可以使用 wqs 二分来优化。二分额外代价 \(c\)，容易发现现在变成了一个 CF865D 那样的经典反悔贪心的样子，直接做就行。复杂度 \(\mathcal{O}(n\log^2 n)\)。
能不能再强力一点？考虑模拟费用流，相当于 \(k\) 次操作，每次选两个位置 \(i,j\)，让 \(c_i\) 加一并让 \(c_j\) 减一，代价是 \(a_i+b_j\)，需要满足每次操作后 \(c_i\) 的前缀和都非负。为什么可以这样转化？听题解说这是因为每次增广的时候我们只会退流中间的边，所以这只会改变原来选的边的匹配性，原来那些边该选还得选。据说这个结论正确性显然，但我不太会证，感觉就很显然吧.jpg
考虑直接线段树维护 \(a_i+b_j\) 最小的合法选取方案 \((i,j)\)。当 \(i\le j\) 时没有限制，但是 \(i>j\) 时需要让 \([i,j)\) 内的前缀和大于 0。这个信息并不好维护，考虑维护一个很高妙的东西，下面给一坨定义：
记当前区间为 \([l,r]\)。
-
\(\text{mina}/\text{minb}\) 表示区间里面 \(a/b\) 数组最小值所在的位置。
-
\(va\) 表示这个区间里面选择 \(i\le j\) 的 \(a_i+b_j\) 最小的方案。
-
\(vc\) 表示这个区间里面选择 \(i>j\) 的 \(a_i+b_j\) 最小的方案。
-
\(vb\) 表示这个区间里面选择 \(i>j\) 的 \(a_i+b_j\) 最小的，且同时满足 \([i,j)\) 之间的前缀和的最小值大于 \([l,r]\) 里面前缀和的最小值的方案。
-
\(tag/mn\) 表示区间加法懒标记和 \([l,r]\) 内所有位置前缀和的最小值。
-
\(\text{alim}\) 表示满足 \([l,\text{alim})\) 区间中前缀和最小值大于 \([l,r]\) 前缀和最小值的位置中，\(a\) 数组对应位置上值最小的一个。
-
\(\text{blim}\) 表示满足 \([\text{blim},r]\) 区间中前缀和最小值大于 \([l,r]\) 前缀和最小值的位置中，\(b\) 数组对应位置上值最小的一个。
注意：\(\text{alim}\) 定义中区间是不到其本身位置的，但是 \(\text{blim}\) 的定义取到了，所以最初建线段树在 \(l=r\) 时可以给 \(\text{alim}\) 赋值，但不能给 \(\text{blim}\) 赋。
下面是 pushup 的过程：
-
先用左右儿子内的信息直接更新 \(va,vb,vc,\text{mina},\text{minb},mn\)。
-
用 \((\text{mina}(ls),\text{minb}(rs))\) 更新 \(va\)，用 \((\text{mina}(rs),\text{minb}(ls))\) 更新 \(vc\)。
然后是大力分讨：
-
当 \(mn(ls)>mn(rs)\) 时，用 \(vc(ls)\) 和 \((\text{alim}(rs),\text{minb}(ls))\) 更新 \(vb\)，用 \(\text{alim}(rs)\) 和 \(\text{mina}(ls)\) 更新 \(\text{alim}\)，用 \(\text{blim}(rs)\) 更新 \(\text{blim}\)。
-
当 \(mn(ls)<mn(rs)\) 时，用 \(vc(rs)\) 和 \((\text{mina}(rs),\text{blim}(ls))\) 更新 \(vb\)，用 \(\text{alim}(ls)\) 更新 \(\text{alim}\)，用 \(\text{blim}(rs)\) 和 \(\text{minb}(ls)\) 更新 \(\text{blim}\)。
-
当 \(mn(ls)=mn(rs)\) 时，用 \((\text{alim}(rs),\text{blim}(ls))\) 更新 \(vb\)，用 \(\text{alim}(ls)\) 更新 \(\text{alim}\)，用 \(\text{blim}(rs)\) 更新 \(\text{blim}\)。
正确性显然，建议自己推一遍。
注意到当 \([l,r]=[1,n]\) 时因为上一次操作后每个位置前缀和都不小于 0，所以全局前缀和最小值一定为 0，这就刚好符合题目条件了。
直接重复 \(k\) 次，每次选最小的位置，复杂度 \(\mathcal{O}(k\log n)\)。
实现的时候最好把 \(a_0,b_0\) 设成 \(\infty\)，那些变量没有值的时候设成 0，这样会方便很多。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,a[500005],b[500005];
struct Info{
int x,y;
Info operator +(const Info &o)const{
if(a[x]+b[y]<=a[o.x]+b[o.y])return {x,y};
return o;
}
};
struct segtree{
#define ls (p<<1)
#define rs (p<<1|1)
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int mina,minb;
Info va,vc,vb;
int tag,mn,alim,blim;
}c[2000005];
void pushup(int p){
if(a[c[ls].mina]<a[c[rs].mina])c[p].mina=c[ls].mina;
else c[p].mina=c[rs].mina;
if(b[c[ls].minb]<b[c[rs].minb])c[p].minb=c[ls].minb;
else c[p].minb=c[rs].minb;
c[p].mn=min(c[ls].mn,c[rs].mn);
c[p].va=c[ls].va+c[rs].va;
c[p].vb=c[ls].vb+c[rs].vb;
c[p].vc=c[ls].vc+c[rs].vc;
c[p].va=c[p].va+(Info){c[ls].mina,c[rs].minb};
c[p].vc=c[p].vc+(Info){c[rs].mina,c[ls].minb};
if(c[ls].mn>c[rs].mn){
c[p].vb=c[p].vb+c[ls].vc;
c[p].vb=c[p].vb+(Info){c[rs].alim,c[ls].minb};
if(a[c[ls].mina]<=a[c[rs].alim])c[p].alim=c[ls].mina;
else c[p].alim=c[rs].alim;
c[p].blim=c[rs].blim;
}
else if(c[ls].mn<c[rs].mn){
c[p].vb=c[p].vb+c[rs].vc;
c[p].vb=c[p].vb+(Info){c[rs].mina,c[ls].blim};
c[p].alim=c[ls].alim;
if(b[c[rs].minb]<=b[c[ls].blim])c[p].blim=c[rs].minb;
else c[p].blim=c[ls].blim;
}
else{
c[p].vb=c[p].vb+(Info){c[rs].alim,c[ls].blim};
c[p].alim=c[ls].alim;
c[p].blim=c[rs].blim;
}
}
void pushdown(int p){
c[ls].mn+=c[p].tag,c[ls].tag+=c[p].tag;
c[rs].mn+=c[p].tag,c[rs].tag+=c[p].tag;
c[p].tag=0;
}
void build(int l,int r,int p){
c[p].tag=0;
if(l==r){
c[p].mina=c[p].minb=l;
c[p].va=(Info){l,l},c[p].vb=c[p].vc=(Info){0,0};
c[p].mn=0;
c[p].alim=l;
c[p].blim=0;
return;
}
int mid=(l+r)>>1;
build(lson);build(rson);
pushup(p);
}
void upd(int l,int r,int p,int x){
if(l==r)return;
int mid=(l+r)>>1;pushdown(p);
if(x<=mid)upd(lson,x);
else upd(rson,x);
pushup(p);
}
void add(int l,int r,int p,int L,int R,int k){
if(L>R)return;
if(L<=l&&r<=R){
c[p].mn+=k,c[p].tag+=k;
return;
}
int mid=(l+r)>>1;pushdown(p);
if(L<=mid)add(lson,L,R,k);
if(R>mid)add(rson,L,R,k);
pushup(p);
}
#undef lson
#undef rson
#undef ls
#undef rs
}Tr;
signed main(){
n=read(),m=read();a[0]=b[0]=inf;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
Tr.build(1,n,1);int ans=0;
while(m--){
Info tmp=Tr.c[1].va+Tr.c[1].vb;
ans+=a[tmp.x]+b[tmp.y];
if(tmp.x<=tmp.y)Tr.add(1,n,1,tmp.x,tmp.y-1,1);
else Tr.add(1,n,1,tmp.y,tmp.x-1,-1);
a[tmp.x]=inf,b[tmp.y]=inf;
Tr.upd(1,n,1,tmp.x),Tr.upd(1,n,1,tmp.y);
}
printf("%lld\n",ans);
return 0;
}
C0427 【1204 A组】模拟测试
A 【1204 A组】奇迹之夜
简单 dp。以 \(k\) 号地点为根，记 \(f_{i,0/1/2/3}\) 表示在以 \(i\) 为根的子树内，\(i\) 这个点选了日常/选了聚会且旁边已经有了后勤/选了聚会且旁边还没有后勤/选了后勤的最大价值和。可以随便转移一下。每次询问的限制相当于深度不超过 \(L\) 的点可以随便选，如果按深度分层，相当于上面的随便选，中间那层的 \(f\) 求和。dp 完之后预处理一下即可。记得判掉 \(L\ge n\) 的情况。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[200005];
int tot,head[100005];
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int a[100005],b[100005],f[100005][5],g[100005],h[100005],s[100005],dep[100005];
void dfs(int u,int fa,int d){
dep[u]=d;
f[u][0]=a[u],f[u][1]=b[u],f[u][2]=b[u],f[u][3]=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa)continue;
dfs(v,u,d+1);
}
vector<int>tmp;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;if(v==fa)continue;
f[u][0]+=max({f[v][0],f[v][1],f[v][3]});
f[u][1]+=max({f[v][0],f[v][1]}),tmp.push_back(f[v][3]-max({f[v][0],f[v][1]}));
f[u][2]+=max({f[v][0],f[v][1]});
f[u][3]+=max({f[v][0],f[v][1],f[v][2],f[v][3]});
}
sort(tmp.begin(),tmp.end(),[](int x,int y){return x>y;});
if(tmp.empty())f[u][1]=-inf;
else{
f[u][1]+=tmp[0];
for(int i=1;i<(int)tmp.size();i++)f[u][1]+=max(0ll,tmp[i]);
}
}
signed main(){
int n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++)b[i]=max(b[i],a[i]);
int root=read();
for(int i=1,u,v;i<n;i++)u=read(),v=read(),add(u,v),add(v,u);
dfs(root,0,0);
for(int i=1;i<=n;i++)h[dep[i]]+=b[i];
s[0]=h[0];for(int i=1;i<=n;i++)s[i]=s[i-1]+h[i];
for(int i=1;i<=n;i++)g[dep[i]]+=max({f[i][0],f[i][1],f[i][2],f[i][3]});
while(m--){
int l=read();
if(l>=n)printf("%lld\n",s[n]);
else if(l)printf("%lld\n",g[l]+s[l-1]);
else printf("%lld\n",g[l]);
}
return 0;
}
B 【1204 A组】树莓立方体
题解做法没看懂，写一个曦老师优秀做法。
考虑询问离线，挂到右端点，从大到小排序。那么现在从右往左移动右端点时就需要删除一个点，把一段分裂成几段，这个可以用 ST 表加二分处理。发现这个过程反过来就是每次加一个点，然后合并几段，于是容易证明这里均摊复杂度是对的。
为什么要从右往左扫呢？因为这个题是要维护一个每行 \(\min\) 的 \(\max\)，如果从左往右扫 \(\min\) 只会越来越小，此时无法忽略之前那个操作区间的影响，就寄了。但是反过来分裂出来的区间只会越来越大，所以之前的区间就直接没影响了，可以直接开一颗线段树维护。支持区间取 max，区间 \(F\) 值历史和，直接套 C 【1129 A组】序列 的板子就行。
有一些小细节：比如每次删点的时候那个点之后就不能再更新历史和了，还有问的是一段时间内的历史和，需要拆询问。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int k,n,q,A,B,C,a[25][50005],b[25][50005],s[50005];
int ql[50005],qr[50005],ans[50005];vector<int>v1[50005],v2[50005];
int F(int x){
if(x==0)return 0;
return A^(B*x+C);
}
struct segtree{
#define ls (p<<1)
#define rs (p<<1|1)
#define lson l,mid,ls
#define rson mid+1,r,rs
struct Node{
int cnt,mn,se,tag,ad,dl,a,ta;
}c[4000005];
void pushup(int p){
c[p].mn=min(c[ls].mn,c[rs].mn);c[p].cnt=0,c[p].se=inf;
if(c[ls].mn==c[p].mn)c[p].cnt+=c[ls].cnt,c[p].se=min(c[p].se,c[ls].se);
else c[p].se=min(c[p].se,c[ls].mn);
if(c[rs].mn==c[p].mn)c[p].cnt+=c[rs].cnt,c[p].se=min(c[p].se,c[rs].se);
else c[p].se=min(c[p].se,c[rs].mn);
c[p].ad=c[ls].ad+c[rs].ad;
c[p].dl=c[ls].dl+c[rs].dl;
}
void pushdown(int l,int r,int p){
int mid=(l+r)>>1,ln=mid-l+1,rn=r-mid;
if(c[ls].mn<c[p].tag)c[ls].ad+=c[ls].cnt*c[p].a,c[ls].dl+=c[ls].cnt*c[p].ta,c[ls].a+=c[p].a,c[ls].ta+=c[p].ta;
if(c[rs].mn<c[p].tag)c[rs].ad+=c[rs].cnt*c[p].a,c[rs].dl+=c[rs].cnt*c[p].ta,c[rs].a+=c[p].a,c[rs].ta+=c[p].ta;
if(c[ls].mn<c[p].tag)c[ls].tag=c[p].tag,c[ls].mn=c[p].tag;
if(c[rs].mn<c[p].tag)c[rs].tag=c[p].tag,c[rs].mn=c[p].tag;
c[p].a=c[p].ta=0,c[p].tag=-inf;
}
void build(int l,int r,int p){
c[p].a=c[p].ta=0,c[p].tag=-inf;
if(l==r){
c[p].mn=c[p].ad=c[p].dl=0,c[p].se=inf,c[p].cnt=1;
return;
}
int mid=(l+r)>>1;
build(lson);build(rson);
pushup(p);
}
void add(int l,int r,int p,int L,int R,int v,int t){
if(c[p].mn>=v)return;
if(L<=l&&r<=R){
if(c[p].mn<v&&v<c[p].se){
c[p].a+=(F(v)-F(c[p].mn)),c[p].ta+=t*(F(v)-F(c[p].mn));
c[p].ad+=c[p].cnt*(F(v)-F(c[p].mn)),c[p].dl+=c[p].cnt*t*(F(v)-F(c[p].mn));
c[p].tag=v,c[p].mn=v;
return;
}
}
if(l==r)return;
int mid=(l+r)>>1;pushdown(l,r,p);
if(L<=mid)add(lson,L,R,v,t);
if(R>mid)add(rson,L,R,v,t);
pushup(p);
}
void upd(int l,int r,int p,int x,int t){
if(l==r){
c[p].a+=(F(0)-F(c[p].mn)),c[p].ta+=t*(F(0)-F(c[p].mn));
c[p].ad+=c[p].cnt*(F(0)-F(c[p].mn)),c[p].dl+=c[p].cnt*t*(F(0)-F(c[p].mn));
c[p].tag=0,c[p].mn=0;
return;
}
int mid=(l+r)>>1;pushdown(l,r,p);
if(x<=mid)upd(lson,x,t);
else upd(rson,x,t);
pushup(p);
}
int ask(int l,int r,int p,int L,int R,int t){
if(L<=l&&r<=R){
return c[p].ad*t-c[p].dl;
}
int mid=(l+r)>>1,res=0;pushdown(l,r,p);
if(L<=mid)res+=ask(lson,L,R,t);
if(R>mid)res+=ask(rson,L,R,t);
return res;
}
#undef lson
#undef rson
#undef ls
#undef rs
}Tr;
int f[25][18][50005];
int ask(int I,int l,int r){
if(l>r)return inf;
int o=__lg(r-l+1);
return min(f[I][o][l],f[I][o][r-(1ll<<o)+1]);
}
signed main(){
k=read(),n=read(),q=read();
for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)a[i][j]=read();
A=read(),B=read(),C=read();
for(int i=1;i<=q;i++){
ql[i]=read(),qr[i]=read(),v1[qr[i]].push_back(i),v2[ql[i]].push_back(i);
}
for(int j=1;j<=k;j++){
for(int i=1;i<=n;i++)f[j][0][i]=a[j][i];
for(int o=1;(1ll<<o)<=n;o++){
for(int i=1;i+(1ll<<o)-1<=n;i++){
f[j][o][i]=min(f[j][o-1][i],f[j][o-1][i+(1ll<<(o-1))]);
}
}
}
Tr.build(1,n,1);
for(int i=n,t=1;i>=1;i--,t++){
for(auto x:v1[i])ans[x]-=Tr.ask(1,n,1,ql[x],qr[x],t-1);
if(i+1<=n)Tr.upd(1,n,1,i+1,t-1);
for(int j=1;j<=k;j++){
int p=i;
while(p>=1&&a[j][p]>a[j][i+1]){
int l=1,r=p,res=0;
while(l<=r){
int mid=(l+r)>>1;
if(ask(j,mid,p)==a[j][p])res=mid,r=mid-1;
else l=mid+1;
}
Tr.add(1,n,1,res,p,a[j][p],t-1),p=res-1;
}
}
for(auto x:v2[i])ans[x]+=Tr.ask(1,n,1,ql[x],qr[x],t);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
C 【1204 A组】爱上火车
考虑一个 25pts 的朴素 dp。定义 \(f_{i,j}\) 表示第 \(i\) 天坐了 \(j\) 次火车的最大价值和，有转移式 \(f_{i,j}=\max(f_{i-1,j},f_{i-1,j-1})+a_{j\bmod k,i}\)。发现题目中有刚好选 \(k\) 个的限制，考虑寻找凸性。大力瞪眼可以发现如果记 \(g_{p,q,i}=f_{i,pk+q}\)，那么 \(g_{p,q,*}\) 是凸的。证明略。考虑开一颗线段树维护凸包。具体的，考虑一个状态 \((l,r,p,q)\)，表示从第 \(l\) 天到第 \(r\) 天，第 \(l\) 天时在第 \(p\) 座城市，第 \(r\) 天时在第 \(q\) 座城市，可以维护 \((*,*,p,q)\) 的凸包，每个点 \((x,y)\) 表示坐了 \(x\) 次火车的最大价值和为 \(y\)。
合并是简单的。对于两个位置 \((x_1,y_1)\) 和 \((x_2,y_2)\)，容易发现合并后新的点就是 \((x_1+x_2,y_1+y_2)\)。注意到这就是一个 max,+ 的卷积，即对这两个凸包求闵可夫斯基和，可以做到 \(\mathcal{O}(|S_1|+|S_2|)\)。所以转移就是你枚举 \((l,mid)\) 的开始城市 \(i\)，结束城市 \(o\) 和 \((mid+1,r)\) 的结束城市 \(j\)。如果从 \(mid\) 天到第 \(mid+1\) 天没有坐火车就是 \((l,mid,i,o)+(mid+1,r,o,j)\)，否则就是 \((l,mid,i,o)+(mid+1,r,(o+1)\bmod k,j)\)，注意后面的转移需要让横坐标全部 +1。
算一下空间。\((l,r,p,q)\) 对应的凸包大小就是 \(\dfrac{r-l}{k}\)。由于每个点需要维护 \(k^2\) 个凸包，所以空间是 \(k^2\sum\dfrac{len}{k}=kn\log n\) 的。时间就是 \(k^3\sum\dfrac{len}{k}=k^2n\log n\)。4 秒钟的话常数大点应该也可以过。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll,ll>pii;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,m,q,a[5][100005];
struct convex{
vector<pii>v;
convex add(){
convex b;b.v=v;
for(int i=0;i<(int)v.size();i++)b.v[i].fi++;
return b;
}
convex operator +(const convex &b)const{
if(v.empty()||b.v.empty())return (convex){vector<pii>()};
convex c;int i=1,j=1;
c.v.push_back({v[0].fi+b.v[0].fi,v[0].se+b.v[0].se});
while(i<(int)v.size()&&j<(int)b.v.size()){
if(v[i].se-v[i-1].se>=b.v[j].se-b.v[j-1].se)c.v.push_back({v[i].fi+b.v[j-1].fi,v[i].se+b.v[j-1].se}),i++;
else c.v.push_back({v[i-1].fi+b.v[j].fi,v[i-1].se+b.v[j].se}),j++;
}
while(i<(int)v.size())c.v.push_back({v[i].fi+b.v[j-1].fi,v[i].se+b.v[j-1].se}),i++;
while(j<(int)b.v.size())c.v.push_back({v[i-1].fi+b.v[j].fi,v[i-1].se+b.v[j].se}),j++;
return c;
}
void merge(convex b){
for(int i=0,j=0;i<(int)v.size();i++){
while(j<(int)b.v.size()&&b.v[j].fi<v[i].fi)j++;
if(j<(int)b.v.size()&&b.v[j].fi==v[i].fi)v[i].se=max(v[i].se,b.v[j].se);
}
}
}t[400005][5][5];
void build(int l,int r,int p){
if(l==r){
for(int i=0;i<m;i++)t[p][i][i].v.push_back({0,a[i][l]});
return;
}
int mid=(l+r)>>1;build(l,mid,p<<1);build(mid+1,r,p<<1|1);
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
for(int x=j-i;x<=r-l;x+=m)if(x>=0)t[p][i][j].v.push_back({x,0});
if(t[p][i][j].v.empty())continue;
for(int o=0;o<m;o++){
t[p][i][j].merge(t[p<<1][i][o]+t[p<<1|1][o][j]);
t[p][i][j].merge((t[p<<1][i][o]+t[p<<1|1][(o+1)%m][j]).add());
}
}
}
for(int l=0;l<m;l++)for(int r=0;r<m;r++){
vector<pii>().swap(t[p<<1][l][r].v);
vector<pii>().swap(t[p<<1|1][l][r].v);
}
}
ll ans[100005];
signed main(){
n=read(),m=read(),q=read();
for(int i=0;i<m;i++)for(int j=1;j<=n;j++)a[i][j]=read();
build(1,n,1);
for(int i=0;i<m;i++){
for(auto x:t[1][0][i].v)ans[x.fi+1]=max(ans[x.fi+1],x.se);
}
while(q--){
int pos=read();
printf("%lld\n",ans[pos]);
}
return 0;
}
C0432 【1208 A组】模拟测试
A 【1208 A组】蛋神的团建
P6571 [BalticOI 2017] Political Development。
又不会做蓝题。
考虑部分分。当 \(d_i\le k\) 时我们可以枚举一个在团里的点，然后团里其他点只会是它相邻的点，可以 \(nk^22^k\) 算。优化就是你发现周围只有至多 10 个点，记周围的点集为 \(S\)，可以 \(k^2\log n\) 预处理 \(S\) 中每个点能到达 \(S\) 中哪些点，这样单次检查复杂度变为 \(\mathcal{O}(k)\)。
考虑正解。注意到还有性质没用。发现整张图一定存在至少一个点 \(d_i\le k\)，那么对这个点跑上述做法后这个点就没用了，可以删去。删去后这个新图一定也有度数不超过 \(k\) 的点，直接递归做就行。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,k,ans,d[50005],vis[50005],id[50005],f[50005];set<int>g[50005];
void dfs(int u){
vis[u]=1;vector<int>tmp;tmp.push_back(u);
for(auto v:g[u])if(!vis[v])tmp.push_back(v);
int siz=(int)tmp.size();
for(int i=0;i<siz;i++){
f[i]=0;
for(int j=0;j<siz;j++){
int x=tmp[i],v=tmp[j];
if(g[x].count(v)||x==v)f[i]|=1ll<<j;
}
}
for(int i=0;i<(1ll<<siz);i++){
int flag=1;
for(int j=0;j<siz;j++){
if((i>>j)&1ll&&(f[j]&i)!=i){flag=0;break;}
}
if(flag)ans=max(ans,(int)__builtin_popcountll(i));
}
for(auto v:g[u])if(!vis[v])g[v].erase(u),d[v]--;
for(auto v:g[u])if(!vis[v]&&(int)g[v].size()<=k)dfs(v);
}
signed main(){
n=read(),k=read();
for(int i=0;i<n;i++){
d[i]=read();
for(int j=1;j<=d[i];j++)g[i].insert(read());
}
for(int i=0;i<n;i++)if(!vis[i]&&(int)g[i].size()<=k)dfs(i);
printf("%lld\n",ans);
return 0;
}