题解 CF1288E 【Messenger Simulator】

题解 CF1288E 【Messenger Simulator】

简单思维+数据结构

1.首先发现x的最小值一定是x或1(x出现过就为1,否则为x)

2.然后我们发现x最大值要么是x,要么是出现x 之前的 x所在位置。这个我们直接用线段树维护每个值的位子即可。相当于对于一个数,他会把比他大的数都加1。修改某个数的位子,就先消除这个数之前的+1,然后把他放到最前,在把后面的数加1。

代码:

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define gc getchar
//#define int long long
const int N=1e6+5;
int n,m,mi[N],ma[N],pos[N],tree[N*4],lazy[N*4];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void pushdown(int nod)
{
    tree[nod*2]+=lazy[nod];
    tree[nod*2+1]+=lazy[nod];
    lazy[nod*2]+=lazy[nod];
    lazy[nod*2+1]+=lazy[nod];
    lazy[nod]=0;
}
void change(int nod,int l,int r,int L,int R,int val)
{
    if(l==L&&r==R)
    {
        tree[nod]+=val;
        lazy[nod]+=val;
        return;
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)change(nod*2,l,mid,L,R,val);
    else if(L>mid)change(nod*2+1,mid+1,r,L,R,val);
    else{
        change(nod*2,l,mid,L,mid,val);
        change(nod*2+1,mid+1,r,mid+1,R,val);
    }
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
int find(int nod,int l,int r,int x)
{
    if(l==r)return tree[nod];
    pushdown(nod);
    int mid=(l+r)/2;
    if(x<=mid)return find(nod*2,l,mid,x);
    else return find(nod*2+1,mid+1,r,x);
}
signed main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)mi[i]=ma[i]=i;
    for(int i=1;i<=n;i++)change(1,0,n+m,pos[i]=i+m,n+m,1);
    for(int i=1;i<=m;i++)
    {
        int x=read();
        mi[x]=1;
        ma[x]=max(ma[x],find(1,0,n+m,pos[x]));
        change(1,0,n+m,pos[x],n+m,-1);
        pos[x]=m-i;
        change(1,0,n+m,pos[x],n+m,1);
    }
    for(int i=1;i<=n;i++)ma[i]=max(ma[i],find(1,0,n+m,pos[i]));
    for(int i=1;i<=n;i++)printf("%d %d\n",mi[i],ma[i]);
    return 0;
}
/*
发现如果一个数x没有出现,那么最小值一定是x
出现了,最小值就是1
最大值要么是x,要么是出现x前的值,这个我们线段树维护一下即可,区间加,单点查 
*/
xuxuxuxuxu 文章被收录于专栏

信息学竞赛

全部评论

相关推荐

Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务