CF1288E Messenger Simulator（树状数组）

根据题目要求，首先最左边的情况直接维护即可。问题是如何知道何时最靠后。

一个朴素的想法是模拟这个过程，把这个数提到最前面，那么每次都对每个数查询一下在他前面的数量最多是多少。

这其实就是单点修改+区间查询，因此我们想到使用树状数组来维护。其实我们不用每次都对每个点查询。我们只需要对每次询问的点查一遍

之后在最后对每个点查一遍就是最后的答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
const int N=1e6+10;
const int M=2e6+10;
const int inf=0x3f3f3f3f;
int tr[N],pos[N];
int l[N],r[N];
int lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    int i;
    for(i=x;i<N;i+=lowbit(i)){
        tr[i]+=c;
    }
}
int sum(int x){
    int i;
    ll ans=0;
    for(i=x;i;i-=lowbit(i)){
        ans+=tr[i];
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int i;
    int now=m;
    for(i=1;i<=n;i++){
        pos[i]=m+i;
        l[i]=r[i]=i;
        add(pos[i],1);
    }

    while(m--){
        int x;
        cin>>x;
        l[x]=1;
        r[x]=max(r[x],sum(pos[x]));
        add(pos[x],-1);
        pos[x]=now--;
        add(pos[x],1);
    }
    for(i=1;i<=n;i++) r[i]=max(r[i],sum(pos[i]));
    for(i=1;i<=n;i++) cout<<l[i]<<" "<<r[i]<<endl;
}