专栏文章

题解：P5979 [PA 2014] Druzyny

zzzy_zzy
P5979题解参与者 2已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipihyhd
此快照首次捕获于
2025/12/03 12:33
3 个月前
此快照最后确认于
2025/12/03 12:33
3 个月前
查看原文

前言

感谢 liu_yi跟我细心讲解！

思路

先考虑暴力怎么做。
像这种分段的题，很多都是 dp，因此我们考虑 dp。套路的，设 dpidp_i 表示以 ii 为一段的结尾的组数最大，gig_i 表示总方案数，则有转移：
dpi=max⁡max⁡k=j+1ick≤i−j≤min⁡k=j+1idkdpj+1dp_i=\max_{\max_{k=j+1}^{i}c_k\le i-j\le \min_{k=j+1}^{i}d_k}dp_j+1 gi=∑max⁡k=j+1ick≤i−j≤min⁡k=j+1idkgjg_i=\sum_{\max_{k=j+1}^{i}c_k\le i-j\le \min_{k=j+1}^{i}d_k}g_j
这样的复杂度是 O(n2)O(n^2) 的，考虑优化。
首先可以确定的是，当 ii 固定时，满足条件的 jj 并非一段区间，因此不能直接使用线段树等数据结构进行优化。
但是，当 ii 固定时，满足 i−j≤min⁡k=j+1idki-j\le \min_{k=j+1}^{i}d_k 的 jj 是一段连续的区间（因为当 jj 减小时，i−ji-j 在变大，而 min⁡k=j+1idk\min_{k=j+1}^{i}d_k 却在变小，迟早会有一个位置会使得这个限制不满足）。所以，可以考虑记 pip_i 为最早满足这个限制的位置。
这时，我们还剩下一个很烦的限制，我们考虑引入一种分治（不妨设它叫 ly 分治）。具体的，对于每段区间 [l,r][l,r]，我们找到这段区间最大值的位置（记作 midmid），先考虑递归计算 [l,mid][l,mid] 的值，将其插入至某种数据结构中，再考虑用 [l,mid][l,mid] 的值去更新 [mid+1,r][mid+1,r] 的值，最后再递归计算 [mid+1,r][mid+1,r] 对 [mid+1,r][mid+1,r] 的贡献。
但是，用 [l,mid][l,mid] 去更新 [mid+1,r][mid+1,r] 的过程也因具体情况而定，一般要分 [l,mid][l,mid] 和 [mid+1,r][mid+1,r] 谁的长度更短两种情况来保证复杂度。（因为如果不这样干的话每次最坏可以遍历 nn 个位置，而递归树的树高最坏是 O(n)O(n) 的，所以总复杂度就退化到 O(n2)O(n^2) 了。若分情况讨论，复杂度就相当于在笛卡尔树上做启发式合并（不用数据结构维护）的复杂度，是 O(nlog⁡n)O(n\log n) 的）
在这道题里。我们分以下两种情况：
  • 若 [l,mid][l,mid] 的长度比 [mid+1,r][mid+1,r] 长，那很简单。直接遍历 [mid+1,r][mid+1,r] 的所有数，由于 midmid 是任意一个跨过 midmid 的区间的最大值，所以这时满足条件的 jj 是一个区间！只要实现单点修、区间求和。可以用线段树维护！
  • 若 [l,mid][l,mid] 的长度比 [mid+1,r][mid+1,r] 短，那也很简单。直接遍历 [l,mid][l,mid] 的所有数，此时我们会发现 pp 是单调的（这个很容易想），因此可以二分出这个位置能更新到的最后一个位置，而由于当 jj 固定时，所能更新到的 ii 也是一段区间（同上一种情况），所以只需要实现区间加、单点修、单点查，也可以使用线段树！
因此，这道题就做完了！实现上，可以新定义加运算表示两个带有最值和最值个数的结构体的合并，注意一下边界条件。

AC code：

CPP
#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
int c[1000010],d[1000010],p[1000010];
const int Mod=1e9+7;
pair<int,int>st[1000010][20];
int Log[1000010];
int getMin(int l,int r){//找d的最小值
    int k=Log[r-l+1];
    if(st[l][k].first<st[r-(1<<k)+1][k].first)return st[l][k].second;
    return st[r-(1<<k)+1][k].second;
}
int getMax(int l,int r){//找c的最大值
    if(!l&&!r)return 0;
    if(!l)l=1;
    int k=Log[r-l+1];
    if(st[l][k].first>st[r-(1<<k)+1][k].first)return st[l][k].second;
    return st[r-(1<<k)+1][k].second;
}
struct NN{
    int Max,ci;//最大值、出现次数
}tree[4000010],tag[4000010];
NN operator+(NN a,NN b){//新定义加
    if(a.Max>b.Max)return a;
    if(a.Max<b.Max)return b;
    return {a.Max,(a.ci+b.ci)%Mod};
}
NN dp[1000010],unit_cell={-1000000000,0};//unit_cell是加操作的单位元
void pushdown(int p){
    if(tag[p].Max==unit_cell.Max&&tag[p].ci==unit_cell.ci)return;
    tree[ls]=tree[ls]+tag[p];
    tree[rs]=tree[rs]+tag[p];
    tag[ls]=tag[ls]+tag[p];
    tag[rs]=tag[rs]+tag[p];
    tag[p]=unit_cell;
}
inline void change(int p,int l,int r,int x,NN Y){//线段树单点修改
    if(l==r&&l==x){
        tree[p]=Y;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(x<=mid)change(ls,l,mid,x,Y);
    else change(rs,mid+1,r,x,Y);
    tree[p]=tree[ls]+tree[rs];
}
inline void Change(int p,int l,int r,int L,int R,NN Y){//线段树区间加
    if(l>R||r<L)return;
    if(l>=L&&r<=R){
        tag[p]=tag[p]+Y;
        tree[p]=tree[p]+Y;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    Change(ls,l,mid,L,R,Y);
    Change(rs,mid+1,r,L,R,Y);
    tree[p]=tree[ls]+tree[rs];
}
inline NN ask(int p,int l,int r,int L,int R){//线段树区间求和
    if(l>R||r<L)return unit_cell;
    if(l>=L&&r<=R)return tree[p];
    pushdown(p);
    int mid=(l+r)>>1;
    return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
}
int n;
inline void ly(int l,int r){//ly分治
    if(l>=r)return;
    int mid=getMax(l,r-1);//细节(如果写成getMax(l,r)会死循环)
    if(mid==l&&r!=l+1)mid=getMax(l+1,r-1);//细节(如果不加会死循环)
    if(r-mid<mid-l+1||r-l==1){//右边更短
        ly(l,mid);
        for(int i=mid+1;i<=r;i++){
            NN ss;
            if(i==r&&c[r]>=c[mid]){
                ss=ask(1,0,n,max(l,p[i]),min(mid-1,i-c[r]));
            }
            else{
                ss=ask(1,0,n,max(l,p[i]),min(mid-1,i-c[mid]));
            }
            ss.Max++;
            dp[i]=ask(1,0,n,i,i);
            dp[i]=dp[i]+ss;
            if(mid>=p[i]&&i-mid>=c[getMax(mid+1,i)]){//细节，考虑每个数对 mid 的贡献
                dp[mid]=ask(1,0,n,mid,mid);
                NN sss=dp[mid];
                sss.Max++;
                dp[i]=dp[i]+sss;
            }
            change(1,0,n,i,dp[i]);
        }
        ly(mid+1,r);
    }
    else{
        ly(l,mid-1);//细节，考虑把 mid 和 mid+1~r 一起算，不然很难用 mid 更新 mid+1~r
        for(int i=l;i<mid;i++){
            int ll=mid,rr=r,ans=mid-1;
            while(ll<=rr){//二分找到右边界
                int Mid=(ll+rr)>>1;
                if(p[Mid]<=i){
                    ans=Mid;
                    ll=Mid+1;
                }
                else rr=Mid-1;
            }
            dp[i]=ask(1,0,n,i,i);
            NN ss=dp[i];
            ss.Max++;
            Change(1,0,n,max(mid,i+c[mid]),min(r-1,ans),ss);
            if(c[r]>=c[mid]){
                if(r-i>=c[r]&&p[r]<=i)dp[r]=dp[r]+ss,Change(1,0,n,r,r,ss);
            }
            else{
                if(r-i>=c[mid]&&p[r]<=i)dp[r]=dp[r]+ss,Change(1,0,n,r,r,ss);
            }
        }
        ly(mid,r);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>c[i]>>d[i];
        st[i][0]={d[i],i};
    }
    Log[0]=-1;
    for(int i=1;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n-(1<<i)+1;j++){
            if(st[j][i-1].first<st[j+(1<<(i-1))][i-1].first){
                st[j][i]=st[j][i-1];
            }
            else{
                st[j][i]=st[j+(1<<(i-1))][i-1];
            }
        }
    }
    // 二分找p
    for(int i=1;i<=n;i++){
        int l=0,r=i-1,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if((i-mid)<=d[getMin(mid+1,i)]){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        p[i]=ans;
    }
    for(int i=1;i<=n;i++)st[i][0]={c[i],i};
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n-(1<<i)+1;j++){
            if(st[j][i-1].first>st[j+(1<<(i-1))][i-1].first){
                st[j][i]=st[j][i-1];
            }
            else{
                st[j][i]=st[j+(1<<(i-1))][i-1];
            }
        }
    }
    // 这个不是cdq分治，那我们就叫它ly分治吧QaQ
    dp[0]={0,1};
    change(1,0,n,0,dp[0]);
    for(int i=1;i<=n;i++){
        dp[i]=unit_cell;
        change(1,0,n,i,dp[i]);
    }
    for(int i=1;i<=4*n;i++){
        tag[i]=unit_cell;
    }
    ly(0,n);
    dp[n]=ask(1,0,n,n,n);
    if(!dp[n].ci||!dp[n].Max){
        cout<<"NIE";
        return 0;
    }
    cout<<dp[n].Max<<" "<<dp[n].ci;
    return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...