首页 > 其他分享 >CF940F.Machine Learning-带修莫队、Mex

CF940F.Machine Learning-带修莫队、Mex

时间:2024-05-03 21:23:02浏览次数:27  
标签:cnt cm rep tot mex Machine CF940F cq Mex

给一个序列 \(a\),两个操作:

  • 1、给 \(l,r\) ,设 \(a_l,\dots,a_r\) 这些数集中每个数 \(v\) 的出现次数是 \(c_v\),要求 \(\mathrm{mex} (c_i)\) .
  • 2、单点修改

\(1\leq n,q\leq 10^5\),时限4s


这种一眼看过去很难维护的信息,一般就先找找性质。

首先注意到关键性质:要求的是出现次数的mex,如果mex是 \(m\) 的话,意味着存在出现 \(1,\dots,m-1\) 次的数字,则区间长度至少是 \(1+2+\dots+(m-1)=O(m^2)\),所以mex至多是 \(O(\sqrt n)\) 的。

如果添加一个数字\(v\),会让 \(cnt_v\to cnt_v+1\),同时假设 \(sz_i\) 表示出现 \(i\) 次的数字个数,则会让原本的 sz[cnt[v]]--,以及 sz[cnt[v]+1]++,删除操作同理,对 cnt,sz 的修改都可以 \(O(1)\) 完成。
那如何维护mex呢?一开始我犯了个错误就是企图在莫队里动态维护mex,明明一读完题就看出来 \(O(\sqrt n)\) 的性质了…

直接用带修莫队维护 cnt,sz 的信息,对于每个询问,\(O(\sqrt n)\) 地暴力跑mex就行了…这样的复杂度是 \(O(q\sqrt n+n^{5/3})\) 的,瓶颈是在带修莫队上面。

写这道题的时候主要犯了两个错误:

  • 一是想的时候没有去想把求解mex和莫队分开,想破了脑子不知道怎么快速更新mex的信息,最后看了眼题解马上就懂了。
  • 二是写代码的时候,居然把离散化写错了…调试调了半天…
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int N=1e5+5;
struct Query{int l,r,idx,times;}Q[N];
struct Modify{int p,x;}M[N];
int n,q,cq,cm;
int cnt[N<<1],sz[N],a[N],b[N<<1],tot,ans[N];
int bl[N],S;
void add(int v){
    sz[cnt[v]]--;
    cnt[v]++;
    sz[cnt[v]]++;
}
void del(int v){
    sz[cnt[v]]--;
    cnt[v]--;
    sz[cnt[v]]++;
}
void modify(int ql,int qr,int t){
    int p=M[t].p;
    if(ql<=p&&p<=qr)del(a[p]);
    swap(a[p],M[t].x);
    if(ql<=p&&p<=qr)add(a[p]);
}
int get_ans(){
    rep(i,1,N-5)if(!sz[i])return i;
    return -1;
}
int main(){
    fastio;
    //prework
    cin>>n>>q;
    rep(i,1,n)cin>>a[i],b[++tot]=a[i];
    rep(i,1,q){
        int op,l,r,p,x;
        cin>>op;
        if(op==1){
            cq++;
            cin>>Q[cq].l>>Q[cq].r;
            Q[cq].idx=cq;
            Q[cq].times=cm;
        }else{
            cm++;
            cin>>M[cm].p>>M[cm].x;
            b[++tot]=M[cm].x;
        }
    }
    sort(b+1,b+tot+1);
    tot=unique(b+1,b+tot+1)-(b+1);
    auto get=[&](int v)->int{
        return lower_bound(b+1,b+tot+1,v)-b;
    };
    rep(i,1,n)a[i]=get(a[i]);
    rep(i,1,cm)M[i].x=get(M[i].x);

    //block
    S=pow(n,2.0/3.0)+1;
    rep(i,1,n)bl[i]=(i-1)/S+1;
    sort(Q+1,Q+cq+1,[&](Query a,Query b){
        if(bl[a.l]!=bl[b.l])return a.l<b.l;
        if(bl[a.r]!=bl[b.r])return a.r<b.r;
        return a.times<b.times;
    });

    //Mo's algorithm
    int l=Q[1].l,r=Q[1].l-1,now=0;
    rep(i,1,cq){
        int ql=Q[i].l,qr=Q[i].r,qt=Q[i].times;
        while(l>ql)add(a[--l]);
        while(r<qr)add(a[++r]);
        while(l<ql)del(a[l++]);
        while(r>qr)del(a[r--]);
        while(now<qt)modify(ql,qr,++now);
        while(now>qt)modify(ql,qr,now--);
        ans[Q[i].idx]=get_ans();
    }
    rep(i,1,cq)cout<<ans[i]<<endl;
    return 0;
}

标签:cnt,cm,rep,tot,mex,Machine,CF940F,cq,Mex
From: https://www.cnblogs.com/yoshinow2001/p/18171630

相关文章

  • Machine Learning - 梯度下降
    一、梯度下降:目的是为了寻找到最合适的$w$和$b$,让成本函数的值最小\[w=w-α\frac{\partialJ(w,b)}{\partialw}\]\[b=b-α\frac{\partialJ(w,b)}{\partialb}\]    其中\(α\)的值通常在\(0-1\)之间,用于控制梯度下降算法的幅度。\(α\)太大,会造成发......
  • Nene and the Mex Operator
    这道题目告诉我们的是,看到\(n\)非常小,不一定是搜索,也不一定是状压,还有可能是枚举是否操作考虑枚举每个不操作的位置,这些位置将序列分成若干个连续段,每一段里面的数字一定会被操作至少一次当一个数字被操作了至少一次之后,他的值就不会比某次操作的区间长度大,于是我们猜想,一个段里......
  • 论文笔记-Machine learning based flow regime recognition in helically coiled tube
    对象:进行了螺旋线圈中的自动两相流模式识别方法:X射线照相的空隙率测量数据+聚类+KNN、RF、SVM目标:模式识别关注特征:结果:聚类分类:模型是随机森林(RF)分类器、KNN分类器和SVM(参见第1节)。为了优化超参数并估计分类器精度,所有模型均采用嵌套5×5交叉验证方案,如图1所示。......
  • 论文笔记-Modeling of dynamic characteristic of particle in transient gas–solid
    对象:气固两相流+数值模拟方法:RCNN=RNN+CNN目标:学习颗粒流的时间和空间不均匀性并预测颗粒动态关注特征:关注颗粒不均匀性对颗粒动力学的独特影响,旨在提出一种基于机器学习的方法来建模颗粒不均匀性和颗粒动力学之间的映射结果:R-CNN模型的预测精度用1-9个时间步长(即1-9ms)的各......
  • 论文笔记-Two-phase flow regime identification based on the liquid-phase velocity
    对象:液相速度信息方法:CNN、LSTM、SVM目标:实现了水平管道内两相流态识别关注特征:从速度时间序列数据中提取的统计特征:均值、均方根和功率谱密度、最大速度比和最大速度差比结果:SVM-93.1%,CNN-94%,LSTM-不佳73.3%LSTM:总共使用了300秒的速度数据,然后将其分为180秒用于训练和......
  • T434199 「LAOI-4」Mex Tower (Hard ver.)
    /* 和上题一样只不过,是换成了检验答案,还是找规律, 自己看看吧awa*///O(n)#pragmaGCCoptimize(2)#include<iostream>#include<algorithm>#include<cstring>#include<ctime>usingnamespacestd;intn,m;strings;charget(chara,charb){ints......
  • T429423 「LAOI-4」Mex Tower (Easy ver.)
    /* 手玩数据找规律 你会发现有很强的规律性*///O(n)#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;intn,m;strings;intx[3]={2,1,0};inty[3]={2,0,1};intx2[3]={1,0,2};inty2[3]={0,1,2};intmai......
  • CF1942B Bessie and MEX 题解
    题目简述给定一个长度为$n$的数组$a$,让你构造一个等长的排列$p$,其中从$0$到$n-1$的每个整数恰好出现一次。满足对于每一个位置$a_i=\texttt{MEX}(p_1,p_2,\ldots,p_i)-p_i$,其中数组的$\texttt{MEX}$是不在该数组中出现的最小非负整数。题目分析我们发现正着做并......
  • AP1867 是一种合成的定向配体 | MedChemExpress (MCE)
    AP1867CAS:195514-23-9品牌:MedChemExpress(MCE)存储条件:Powder:-20°C,3years;4°C,2years.Insolvent:-80°C,6months;-20°C,1month.生物活性:AP1867是一种合成的FKBP12F36V定向配体[1]。IC50和目标:FKBP[1]体外:AP1867与野生型FKBP(Kd=67nM)[2]结......
  • PLGA (50:50) 是聚乳酸 (PLA) 和聚乙醇酸 (PGA) 的共聚物 | MedChemExpress (MCE)
    PLGA(50:50)|聚乳酸-羟基乙酸共聚物中文名:聚乳酸-羟基乙酸共聚物CAS:34346-01-5品牌:MedChemExpress(MCE)存储条件:Powder:-20°C,3years;4°C,2years.Insolvent:-80°C,6months;-20°C,1month.生物活性:PLGA(50:50)(poly(lactic-co-glycolicacid)(50:5......