P4137

Aryper · 2021-08-18 13:33:36 · 个人记录

Rmq Problem / mex

一开始，我想用一个树状数组套主席树，然后再离线莽，这个想法是正确的，时间复杂度上能过，然而空间复杂度太高，在卡了无数次的空间大小之后，最终只能得到 73pts。当然，如果它能把空间开到 256M，这个离线树状数组套主席树，就叫绝杀，可惜换不得。（玩梗。当然这个复杂度是 O(n\log^2 n) 的还是有点烂）

后来就看到了非常巧妙的做法。

同样是建立权值线段树，然后离线。但是我们给每个数存储一个 lst，表示到当前询问时它最后一次出现的位置。这样就可以很好的优化。

我们针对每一次询问在权值线段树上二分寻找权值小于 l 的数，最小的满足这个条件的数即为所求。

当然如果在线询问的话改成主席树就完事了。

予观后，不禁拍手称快：此法妙矣！

时间复杂度是 O(n\log n)。空间复杂度 O(n)（线段树）。

然后关于莫队之类的分块算法，咕咕咕咕。

代码（普通权值线段树）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=2e5;

ll n,m,amt;

ll a[N+5],lst[N+5];

struct node{
    ll l,r,id,ans;
}q[N+5];

struct sgt{
    ll l,r,mi;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define mi(x) tree[x].mi
}tree[N*4+5];

void build(ll p,ll l,ll r) {
    l(p)=l;r(p)=r;
    if(l==r) {return;}
    ll mid=(l+r)>>1;
    build(p*2,l,mid);build(p*2+1,mid+1,r);
}

void add(ll p,ll x,ll y) {
    if(l(p)==r(p)) {mi(p)+=y;return;}
    ll mid=(l(p)+r(p))>>1;
    if(x<=mid) add(p*2,x,y);
    else add(p*2+1,x,y);
    mi(p)=min(mi(p*2),mi(p*2+1));
}

ll ask(ll p,ll l) {
    if(l(p)==r(p)) return r(p);
    ll mid=(l(p)+r(p))>>1;
    if(mi(p*2)<l) return ask(p*2,l);
    else
    if(mi(p*2+1)<l) return ask(p*2+1,l);
    else return r(p)+1;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

bool cmp(node x,node y) {
    if(x.r==y.r) return x.l<y.l;
    return x.r<y.r;
}

bool cmp_(node x,node y) {
    return x.id<y.id;
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();amt=max(amt,a[i]);
    }
    amt++;

    build(1,0,amt);

    for(ll i=1;i<=m;i++) {
        q[i].l=read();q[i].r=read();q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);

    for(ll i=1;i<=m;i++) {
        for(ll j=q[i-1].r+1;j<=q[i].r;j++) {
            if(lst[a[j]]) add(1,a[j],-lst[a[j]]);
            add(1,a[j],j);lst[a[j]]=j;
        }
        q[i].ans=ask(1,q[i].l);
    }

    sort(q+1,q+m+1,cmp_);
    for(ll i=1;i<=m;i++) {
        write(q[i].ans);putchar('\n');
    }

    return 0;
}

代码（树状数组套主席树 73pts）：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll int
using namespace std;

const ll N=9e6;

ll n,m,amt,tot,n1,n2;

ll rt[N+5],a[N+5],tmp1[N+5],tmp2[N+5],lst[N+5];

struct node{
    ll l,r,id,ans;
}q[N+5];

struct sgt{
    ll l,r,cnt;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define cnt(x) tree[x].cnt
}tree[N+5];

void ins(ll &rt,ll l,ll r,ll loc,ll v) {
    if(!rt) rt=++tot;
    cnt(rt)+=v;
    if(l==r) return;
    ll mid=(l+r)>>1;
    if(loc<=mid) ins(l(rt),l,mid,loc,v);
    else ins(r(rt),mid+1,r,loc,v);
}

void add(ll x,ll y) {
    for(ll i=x;i<=n;i+=i&-i) ins(rt[i],0,amt,a[x],y);
}

ll query(ll l,ll r) {
    if(l==r) return l;
    ll mid=(l+r)>>1,sum=0;
    for(ll i=1;i<=n1;i++) sum+=cnt(l(tmp1[i]));
    for(ll i=1;i<=n2;i++) sum-=cnt(l(tmp2[i]));
    if(sum<mid-l+1) {
        for(ll i=1;i<=n1;i++) tmp1[i]=l(tmp1[i]);
        for(ll i=1;i<=n2;i++) tmp2[i]=l(tmp2[i]);
        return query(l,mid);
    }
    else {
        for(ll i=1;i<=n1;i++) tmp1[i]=r(tmp1[i]);
        for(ll i=1;i<=n2;i++) tmp2[i]=r(tmp2[i]);
        return query(mid+1,r);
    }
}

ll qpre(ll r,ll l) {
    n1=n2=0;
    for(ll i=r;i;i-=i&-i) tmp1[++n1]=rt[i];
    for(ll i=l;i;i-=i&-i) tmp2[++n2]=rt[i];
    return query(0,amt);
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

bool cmp(node x,node y) {
    if(x.r==y.r) return x.l<y.l;
    return x.r<y.r;
}

bool cmp_(node x,node y) {
    return x.id<y.id;
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=n;i++) {
        a[i]=read();amt=max(amt,a[i]);
    }

    amt++;

    for(ll i=1;i<=m;i++) {
        q[i].l=read();q[i].r=read();q[i].id=i;
    }

    sort(q+1,q+m+1,cmp);

    for(ll i=1;i<=m;i++) {
        for(ll j=q[i-1].r+1;j<=q[i].r;j++) {
            if(lst[a[j]]) add(lst[a[j]],-1);
            add(j,1);lst[a[j]]=j;
        }
        q[i].ans=qpre(q[i].r,q[i].l-1);
    }

    sort(q+1,q+m+1,cmp_);

    for(ll i=1;i<=m;i++) {
        write(q[i].ans);putchar('\n');
    }

    return 0;
}