F. MEX vs MED

一开始写了个感觉每个点只会搞一次的那种线性 感性理解了很对 结果又wa又t

int left=l-z-1,right=n-r;
            int cnt=2*now;
            for(int len=min(n-z,cnt);len>=r-l+1;len--)
                ans+=min({left,right,len-(r-l+1),right+left+r-l+1-(len)})+1;
            for(int i=z;i<l;i++)s.erase(a[i]);
            l=z;
            now=*s.begin();         

现在回过头来看 我们这样枚举区间长度的话还是很容易构造出近似n2的做法

回归正题

我们发现只有mex(0,1,2…x-1)都存在一个区间内的时候 我们该区间小于x2的长度时 这时我们可以左右开始延展!
没错“延展”这个很有用途 为我们后面埋下了伏笔
但是我们这里延展的时候为了不重复计算 我们要用一个set来实时更新一下下一个阻断点
比如有时候我们现在枚举x-1完了 我们要吃掉x 但是去吃掉x的途中 我们还吃掉了x+1 x+2
这下我们下一个阻断点就必须是x+3了 这样才不会重复计算
但是我们考虑如何计算贡献
我们知道
我们给定了一个大区间 然后有个小区间在中间 让后最长不超过x
2长度
这时候其实我们直接暴力枚举即可 但是枚举的方向同x的方向
比如我们x在左我们就让l去左 这样就保证了每个点只枚举了一次!
这样就做完了
最后我们特判一下最后一个点一定是结束的时候囊括了所有数但是我们s已经empty了 所以 +1 即可

void solve(){
    int n;cin>>n;
    set<int>s;
    for(int i=1;i<n;i++)s.insert(i);
    vector<int>a(n+1),pos(n+1);
    for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
    int l=pos[0],r=pos[0],now=1;
    long long ans=0;
    while(s.size()){
        int z=pos[now];
        if(z<l){
            for(int i=z+1;i<=l;i++)
                ans+=max(0,min(2*now+i-1,n)-r+1);
            for(int i=z;i<l;i++)s.erase(a[i]);
            l=z;
            now=*s.begin();
        }else{
            for(int i=r;i<z;i++)
                ans+=max(0,l-max(i-2*now+1,1)+1);
            for(int i=r+1;i<=z;i++)s.erase(a[i]);
            r=z;
            now=*s.begin();
        }
    }
    cout<<ans+1<<endl;
}

原文地址:http://www.cnblogs.com/ycllz/p/16931210.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性