[JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)
做法比较显然，依次考虑每一个数能否加进去，判断标准就是剩下的空隙里还够插入需要的区间数量。
因为加入一个区间最多改变两个空隙，我们只需要考虑这些空隙的增量即可。
对于一个空隙，我们一定是每次贪心找到右端点最小的区间，这个东西显然倍增快速计算，复杂度 \(O(n\log n)\)
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int n,m;
struct node
{
int l,r;
}p[N];
int f[N][20];
int num[N*2],tot=0;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
bool operator <(node a,node b){return a.l<b.l;}
set<node> segment;
int query(int l,int r)
{
int res=0;
for(int i=19;i>=0;i--)
if(f[l][i]<=r)res+=(1<<i),l=f[l][i];
return res;
}
int now,K;
int main()
{
read(n);read(K);
for(int i=1;i<=n;i++)
{
read(p[i].l);num[++tot]=p[i].l;
read(p[i].r);num[++tot]=p[i].r;
}
sort(num+1,num+tot+1);tot=unique(num+1,num+tot+1)-num-1;
for(int i=1;i<=tot+1;i++)f[i][0]=tot+1;
for(int i=1;i<=n;i++)
{
p[i].l=lower_bound(num+1,num+tot+1,p[i].l)-num;
p[i].r=lower_bound(num+1,num+tot+1,p[i].r)-num;
f[p[i].l][0]=min(f[p[i].l][0],p[i].r);
}
for(int i=tot;i>=1;i--)f[i][0]=min(f[i][0],f[i+1][0]);
for(int k=1;k<=19;k++)
for(int i=1;i<=tot+1;i++)
f[i][k]=f[f[i][k-1]][k-1];
now=query(1,tot);
if(now<K)
{
cout<<-1;
return 0;
}
segment.insert((node){0,1});
segment.insert((node){tot,tot+1});
for(int i=1;i<=n;i++)
{
if(!K)continue;
int l=p[i].l,r=p[i].r;
auto rp=segment.lower_bound((node){r,0});
auto lp=rp;lp--;
if(!((*lp).r<=l))continue;
int upd=now+query((*lp).r,l)+query(r,(*rp).l)-query((*lp).r,(*rp).l);
if(upd+1<K)continue;
segment.insert(p[i]);
printf("%d\n",i);
K--;
now=upd;
}
return 0;
}
[JOISC 2021 Day2] 道路の建設案 (Road Construction)
先二分答案，然后把曼哈顿转为切比雪夫，然后做个二维偏序即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
int n,m;
struct node
{
int l,r;
}p[N];
int f[N][20];
int num[N*2],tot=0;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
bool operator <(node a,node b){return a.l<b.l;}
set<node> segment;
int query(int l,int r)
{
int res=0;
for(int i=19;i>=0;i--)
if(f[l][i]<=r)res+=(1<<i),l=f[l][i];
return res;
}
int now,K;
int main()
{
read(n);read(K);
for(int i=1;i<=n;i++)
{
read(p[i].l);num[++tot]=p[i].l;
read(p[i].r);num[++tot]=p[i].r;
}
sort(num+1,num+tot+1);tot=unique(num+1,num+tot+1)-num-1;
for(int i=1;i<=tot+1;i++)f[i][0]=tot+1;
for(int i=1;i<=n;i++)
{
p[i].l=lower_bound(num+1,num+tot+1,p[i].l)-num;
p[i].r=lower_bound(num+1,num+tot+1,p[i].r)-num;
f[p[i].l][0]=min(f[p[i].l][0],p[i].r);
}
for(int i=tot;i>=1;i--)f[i][0]=min(f[i][0],f[i+1][0]);
for(int k=1;k<=19;k++)
for(int i=1;i<=tot+1;i++)
f[i][k]=f[f[i][k-1]][k-1];
now=query(1,tot);
if(now<K)
{
cout<<-1;
return 0;
}
segment.insert((node){0,1});
segment.insert((node){tot,tot+1});
for(int i=1;i<=n;i++)
{
if(!K)continue;
int l=p[i].l,r=p[i].r;
auto rp=segment.lower_bound((node){r,0});
auto lp=rp;lp--;
if(!((*lp).r<=l))continue;
int upd=now+query((*lp).r,l)+query(r,(*rp).l)-query((*lp).r,(*rp).l);
if(upd+1<K)continue;
segment.insert(p[i]);
printf("%d\n",i);
K--;
now=upd;
}
return 0;
}
[JOISC 2021 Day3] ビーバーの会合 2
首先奇数的答案肯定是 \(1\)，偶数的时候我们要找一条尽量长的链然后把 \(k/2\) 个点塞端点所在的子树里。
点分治，求出这条链经过分支中心的答案，假设两个端点分别是 \(i,j\)，到分治中心的距离是 \(d_i,d_j\)，子树大小是 \(s_i,s_j\) ，那么这一对会贡献到 \(k\leq 2\min(s_i,s_j)\) ，这是一个前缀，我们只需要枚举 $\min $ 所在位置，找大于它的 \(j\) 中 \(d_j\) 最大的即可。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
vector<int> G[N];
int n;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
int siz[N],son[N],vis[N];
void findroot(int x,int pre,int tot,int &root)
{
siz[x]=1;son[x]=0;
for(int y:G[x])
{
if(vis[y]||y==pre)continue;
findroot(y,x,tot,root);
son[x]=max(son[x],siz[y]);
siz[x]+=siz[y];
}
son[x]=max(son[x],tot-siz[x]);
if(!root||son[x]<son[root])root=x;
}
vector<int> seq;
int ans[N],col[N],dep[N];
void extend(int x,int pre)
{
siz[x]=1;
dep[x]=dep[pre]+1;
if(pre)seq.push_back(x);
for(int y:G[x])
{
if(vis[y]||y==pre)continue;
if(!pre)col[y]=y;
else col[y]=col[x];
extend(y,x);
siz[x]+=siz[y];
}
}
void ckmax(int &x,int v){x=max(x,v);}
bool cmp(int x,int y){return siz[x]>siz[y];}
struct node
{
int x,y;
};
node upd(node o,int x)
{
if(!o.x)return (node){x,0};
if(col[o.x]!=col[x])
{
if(dep[x]>=dep[o.x])return (node){x,o.x};
if(dep[x]>=dep[o.y])return (node){o.x,x};
return o;
}
if(dep[x]>=dep[o.x])return (node){x,o.y};
return o;
}
void divide(int r)
{
vis[r]=1;
seq.clear();
extend(r,0);
int m=(int)seq.size();
sort(seq.begin(),seq.end(),cmp);
node o=(node){0,0};
for(int i=0;i<m;i++)
{
int x=seq[i];
if(o.x&&col[o.x]!=col[x])
ckmax(ans[2*siz[x]],dep[x]+dep[o.x]-1);
else if(o.y) ckmax(ans[2*siz[x]],dep[x]+dep[o.y]-1);
o=upd(o,x);
}
for(int i=0;i<m;i++)
{
int x=seq[i];
ckmax(ans[2*min(siz[x],siz[r]-siz[col[x]])],dep[x]);
}
for(int y:G[r])if(!vis[y])
{
int z=0;
findroot(y,r,siz[y],z);
divide(z);
}
}
int main()
{
read(n);
for(int i=1;i<n;i++)
{
int x,y;
read(x);read(y);
G[x].push_back(y);
G[y].push_back(x);
}
int r=0;
findroot(1,0,n,r);
for(int i=1;i<=n;i++)ans[i]=1;
divide(r);
for(int i=n;i>=1;i--)if(i%2==0)
ckmax(ans[i-2],ans[i]);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
[JOISC 2021 Day1] フードコート
首先还是对序列扫描线，维护时间线段树，可以发现每个时候存在的是一个后缀。我们可以找到最后一个把队列删空的位置，然后后面就是查询倒数第 \(k\) 个插入的位置，线段树二分即可。
最后一个把队列删空的位置求法：把插入看成 +，删除看成 -，查询后缀和最大的位置，证明比较简单。
code
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
typedef long long LL;
const int N = 3e5+7;
struct Issue
{
int t;
LL v;
};
vector<Issue> Q[N],Ask[N];
int n,m,q;
int qc[N],qv[N];
int ans[N];
struct Info
{
LL sum,suf;
}tr[N*4];
LL val[N*4];
inline Info operator +(Info A,Info B){return (Info){A.sum+B.sum,max(B.suf,A.suf+B.sum)};}
void upd(int k,int l,int r,int x,LL v)
{
if(l==r)
{
tr[k]=(Info){v,max(0ll,v)};
val[k]=max(0ll,v);
return;
}
int mid=(l+r)>>1;
if(x<=mid)upd(k<<1,l,mid,x,v);
else upd(k<<1|1,mid+1,r,x,v);
tr[k]=tr[k<<1]+tr[k<<1|1];
val[k]=val[k<<1]+val[k<<1|1];
}
Info query(int k,int l,int r,int L,int R)
{
if(L>R)return (Info){0,0};
if(L<=l&&r<=R)return tr[k];
int mid=(l+r)>>1;
if(R<=mid)return query(k<<1,l,mid,L,R);
if(L>mid)return query(k<<1|1,mid+1,r,L,R);
return query(k<<1,l,mid,L,mid)+query(k<<1|1,mid+1,r,mid+1,R);
}
int get(int k,int l,int r,int L,int R,LL &s)
{
if(L<=l&&r<=R)
{
if(val[k]<s)
{
s-=val[k];
return -1;
}
if(l==r)return l;
}
int mid=(l+r)>>1;
int p=-1;
if(R>mid)p=get(k<<1|1,mid+1,r,L,R,s);
if(p!=-1)return p;
if(L<=mid)p=get(k<<1,l,mid,L,R,s);
return p;
}
int main()
{
read(n);read(m);read(q);
for(int i=1;i<=q;i++)
{
read(qc[i]);
if(qc[i]==1)
{
int l,r,v;
read(l);read(r);read(qv[i]);read(v);
Q[l].push_back((Issue){i,v});
Q[r+1].push_back((Issue){i,0});
}
else if(qc[i]==2)
{
int l,r,v;
read(l);read(r);read(v);
Q[l].push_back((Issue){i,-v});
Q[r+1].push_back((Issue){i,0});
}
else
{
int p;LL v;
read(p);read(v);
Ask[p].push_back((Issue){i,v});
}
}
for(int i=1;i<=n;i++)
{
for(auto u:Q[i])
{
int t=u.t;LL v=u.v;
upd(1,1,q,t,v);
}
for(auto u:Ask[i])
{
int t=u.t;LL v=u.v;
Info f=query(1,1,q,1,t);
if(f.suf>=v)
{
LL p=f.suf-v+1;
ans[t]=qv[get(1,1,q,1,t,p)];
}
}
}
for(int i=1;i<=q;i++)if(qc[i]==3)printf("%d\n",ans[i]);
return 0;
}
[JOISC 2021 Day4] 最悪の記者 4 (Worst Reporter 4)
老实说，感觉题解区的大部分都可以撤掉。
大部分题解的线段树合并部分都很奇怪，如果按照这些题解的 dp 定义，父子之间本应该是单向的合并关系但是具体实现却是双向的，并且应当是每个位置做后缀 min 再加起来的话，当父亲该节点为空时，儿子该节点应该对自己取后缀 min，毕竟不一定是单调的。
正确的理解方式应当是，在子树内选出一些点，选出的 h 的 min = i 的代价，这样的话才可以这样合并。
合并两个子树只需要按照正常的线段树维护后缀 min 即可，需要支持区间加。
至于基环树的部分，可以发现环上所有点最终都相同，那么要么这个最终值是原来环上某个点的权值，要么是线段树上的最小值，简单统计就好了。
code
#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
const int N = 2e5+7;
const int M = N*32;
int n,p[N],h[N],c[N];
vector<int> G[N];
typedef long long LL;
bool vis[N];
int deg[N];
queue<int> q;
bool oncir[N];
LL tag[M],mn[M];
int lson[M],rson[M];
void pushtag(int k,LL v)
{
if(!k)return;
tag[k]+=v;
mn[k]+=v;
}
void pushup(int k)
{
mn[k]=min(mn[lson[k]],mn[rson[k]]);
}
void pushdown(int k)
{
if(tag[k])
{
pushtag(lson[k],tag[k]);
pushtag(rson[k],tag[k]);
tag[k]=0;
}
}
void modify(int k,int l,int r,int L,int R,LL v)
{
if(!k||L>R)return;
if(L<=l&&r<=R)
{
pushtag(k,v);
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(L<=mid)modify(lson[k],l,mid,L,R,v);
if(R>mid)modify(rson[k],mid+1,r,L,R,v);
pushup(k);
}
int tot=0;
void upd(int &k,int l,int r,int x,LL v)
{
if(!k)k=++tot;
if(l==r)
{
mn[k]=v;
return;
}
pushdown(k);
int mid=(l+r)>>1;
if(x<=mid)upd(lson[k],l,mid,x,v);
else upd(rson[k],mid+1,r,x,v);
pushup(k);
}
LL query(int k,int l,int r,int L,int R)
{
if(!k||L>R)return 0ll;
if(L<=l&&r<=R)return mn[k];
pushdown(k);
LL res=0;
int mid=(l+r)>>1;
if(L<=mid)res=min(res,query(lson[k],l,mid,L,R));
if(R>mid)res=min(res,query(rson[k],mid+1,r,L,R));
return res;
}
int Merge(int x,int y,int l,int r,LL xv,LL yv)
{
if(!x&&!y)return 0;
pushdown(x);pushdown(y);
if(!y)
{
pushtag(x,yv);
return x;
}
if(!x)
{
pushtag(y,xv);
return y;
}
if(l==r)
{
mn[x]=min(mn[x]+min(yv,mn[y]),mn[y]+xv);
return x;
}
int mid=(l+r)>>1;
lson[x]=Merge(lson[x],lson[y],l,mid,min(xv,mn[rson[x]]),min(yv,mn[rson[y]]));
rson[x]=Merge(rson[x],rson[y],mid+1,r,xv,yv);
pushup(x);
return x;
}
int rot[N];
int m,dct[N];
void dfs(int x)
{
for(int y:G[x])
{
dfs(y);
rot[x]=Merge(rot[x],rot[y],1,m,0ll,0ll);
}
LL v=query(rot[x],1,m,h[x],m);
upd(rot[x],1,m,h[x],v-c[x]);
}
int seq[N],cnt=0;
LL buc[N];
int main()
{
read(n);
for(int i=1;i<=n;i++)read(p[i]),read(h[i]),read(c[i]),deg[p[i]]++,dct[++m]=h[i];
sort(dct+1,dct+m+1);
m=unique(dct+1,dct+m+1)-dct-1;
for(int i=1;i<=n;i++)h[i]=lower_bound(dct+1,dct+m+1,h[i])-dct;
for(int i=1;i<=n;i++)if(!deg[i])q.push(i);
while(!q.empty())
{
int x=q.front();
q.pop();
int y=p[x];
--deg[y];
if(!deg[y])q.push(y);
}
for(int i=1;i<=n;i++)if(deg[i])oncir[i]=1;
else G[p[i]].push_back(i);
LL ans=0ll;
for(int i=1;i<=n;i++)ans+=c[i];
for(int i=1;i<=n;i++)
if(oncir[i])
{
if(vis[i])continue;
int x=i;
cnt=0;
while(!vis[x])
{
vis[x]=1;
seq[++cnt]=x;
x=p[x];
}
int root=0;
for(int j=1;j<=cnt;j++)
{
x=seq[j];
for(int y:G[x])
{
dfs(y);
root=Merge(root,rot[y],1,m,0ll,0ll);
}
buc[h[x]]+=c[x];
}
LL res=query(root,1,m,1,m);
for(int j=1;j<=cnt;j++)
{
int x=seq[j];
res=min(res,query(root,1,m,h[x],m)-buc[h[x]]);
}
ans+=res;
for(int j=1;j<=cnt;j++)buc[h[seq[j]]]=0;
}
cout<<ans;
return 0;
}
[JOISC 2021 Day3] ボディーガード
把（时间，坐标）看成一个二维点，那么每个人每次就是向右上或者右下移动。
我们转一下，变成向上和向右移动，那么每个人的轨迹就是一条水平或者竖直的线。
把所有线的端点坐标离散化一下，就变成了一个网格图，每条边有一定权值。
考虑一下一个保镖是怎么动的，一定是先向上或者向右走到某一条线，然后再沿着这条线走到第一个格点。
走到格点后的情况我们可以预先 \(dp\) 出来，前面的部分，可以发现是一个关于保镖坐标的一次函数，那么就是每次查询横线或者竖线某个后缀直线的最值，可以离线下来用李超线段树维护。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 6000;
const int M = 3e6+7;
template <typename T>inline void read(T &x)
{
x=0;char c=getchar();bool f=0;
for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
x=(f?-x:x);
}
typedef long long LL;
struct segment
{
LL K,B;
LL operator ()(LL x){return x*K+B;}
};
segment seg[N];
int tot=0,root=0;
int lson[N],rson[N];
void ins(int &k,LL l,LL r,segment L)
{
if(!k)
{
k=++tot;
seg[k]=L;
return;
}
LL mid=(l+r)>>1;
if(L(mid)>seg[k](mid))swap(seg[k],L);
if(L(l)>seg[k](l))ins(lson[k],l,mid,L);
if(L(r)>seg[k](r))ins(rson[k],mid+1,r,L);
}
LL qry(int k,LL l,LL r,LL x)
{
if(!k)return 0ll;
LL v=seg[k](x);
LL mid=(l+r)>>1;
if(x<=mid)v=max(v,qry(lson[k],l,mid,x));
else v=max(v,qry(rson[k],mid+1,r,x));
return v;
}
void clr()
{
for(int i=1;i<=tot;i++)lson[i]=rson[i]=0;
tot=0;root=0;
}
int n,m;
int nx,ny;
#define PII pair<LL,LL>
#define X(x) x.first
#define Y(x) x.second
#define mk(x,y) make_pair(x,y)
PII S[N],T[N];
LL valx[N],valy[N];
LL down[N][N],rgh[N][N],w[N];
LL dp[N][N];
LL ans[M],qx[M],qy[M];
vector<int> Qry[N][N];
int main()
{
read(n);read(m);
for(int i=1;i<=n;i++)
{
LL t,x,y;
read(t);read(x);read(y);read(w[i]);
S[i]=mk(t+x,t-x);
T[i]=mk(t+abs(y-x)+y,t+abs(y-x)-y);
valx[++nx]=S[i].first;
valx[++nx]=T[i].first;
valy[++ny]=S[i].second;
valy[++ny]=T[i].second;
}
sort(valx+1,valx+nx+1);nx=unique(valx+1,valx+nx+1)-valx-1;
sort(valy+1,valy+ny+1);ny=unique(valy+1,valy+ny+1)-valy-1;
for(int i=1;i<=n;i++)
{
S[i].first=lower_bound(valx+1,valx+nx+1,S[i].first)-valx;
T[i].first=lower_bound(valx+1,valx+nx+1,T[i].first)-valx;
S[i].second=lower_bound(valy+1,valy+ny+1,S[i].second)-valy;
T[i].second=lower_bound(valy+1,valy+ny+1,T[i].second)-valy;
if(S[i].first==T[i].first)
{
for(int j=S[i].second;j<T[i].second;j++)
rgh[S[i].first][j]=max(rgh[S[i].first][j],w[i]);
}
else
{
for(int j=S[i].first;j<T[i].first;j++)
down[j][S[i].second]=max(down[j][S[i].second],w[i]);
}
}
for(int i=nx;i>=1;i--)
for(int j=ny;j>=1;j--)
{
dp[i][j]=max(dp[i][j],dp[i][j+1]+rgh[i][j]*(valy[j+1]-valy[j]));
dp[i][j]=max(dp[i][j],dp[i+1][j]+down[i][j]*(valx[i+1]-valx[i]));
}
for(int i=1;i<=m;i++)
{
LL t,p;
read(t);read(p);
LL x=t+p,y=t-p;
if(valx[nx]<x||valy[ny]<y)continue;
int px=lower_bound(valx+1,valx+nx+1,x)-valx;
int py=lower_bound(valy+1,valy+ny+1,y)-valy;
qx[i]=x;qy[i]=y;
Qry[px][py].push_back(i);
//for(int j=px;j<=nx;j++)ans[i]=max(ans[i],dp[j][py]+ rgh[j][py-1]*(valy[py]-y));
//for(int j=py;j<=ny;j++)ans[i]=max(ans[i],dp[px][j]+down[px-1][j]*(valx[px]-x));
}
for(int py=1;py<=ny;py++)
{
clr();
for(int j=nx;j>=1;j--)
{
ins(root,-2e9,2e9,(segment){-rgh[j][py-1],dp[j][py]+rgh[j][py-1]*valy[py]});
for(int u:Qry[j][py])ans[u]=max(ans[u],qry(root,-2e9,2e9,qy[u]));
}
}
for(int px=1;px<=nx;px++)
{
clr();
for(int j=ny;j>=1;j--)
{
ins(root,-2e9,2e9,(segment){-down[px-1][j],dp[px][j]+down[px-1][j]*valx[px]});
for(int u:Qry[px][j])ans[u]=max(ans[u],qry(root,-2e9,2e9,qx[u]));
}
}
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]/2);
return 0;
}