题解 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前的值，这个我们线段树维护一下即可，区间加，单点查 
*/