题解-P4137

木木！ · 2020-11-27 20:25:23 · 题解

思路和一众大佬的思路差不多，先给询问按 r 排序，就变成了扫描线问题，每次二分后查询 [0,mid] 权值中出现位置最小的值。可以直接实现 \Theta(q\log^2n) 或线段树上二分 \Theta(q\log n)。

但是注意到每次查询的最小值是权值数组上的前缀最小值，而前缀最小值可以考虑使用树状数组维护。树状数组维护前缀最小值的条件是每次修改只能往小改，那么只需要从后往前做就好了。

在树状数组上二分则类似于倍增，考虑一下询问前缀最小值的过程就可以很容易的理解这个二分方法了。

优点是码量和常数都很小，不易出错；缺点是有点难想。时间复杂度 \Theta(n\log n+q\log n)。

附 AC 代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

inline void chkmin(int& a,int b) { if(b<a) a=b; }

int getint()
{
    char ch;
    while((ch=getchar()) < '!') ;
    int x = ch^'0';
    while((ch=getchar()) > '!') x = (x*10)+(ch^'0');
    return x;
}

void putint(int x)
{
    if(x/10) putint(x/10);
    putchar((x%10)^'0');
}

int tx[200005];
const int trin = 200001;
const int logtn = 17;

int lowbit(int x) { return x&(-x); }

void init()
{
    memset(tx,0x7f,(trin+1)*sizeof(int));
}

void fix(int x,int v)
{
    while(x<=trin)
    {
        chkmin(tx[x],v);
        x += lowbit(x);
    }
}

int query(int l)  // 树状数组上二分
{
    int res = 0;
    for(int i=1<<logtn; i>=1; i>>=1)
    {
        if((res|i)<=trin && tx[res|i]>=l)
        {
            res |= i;
        }
    }
    return res;
}

struct qry
{
    int l;
    int r;
    int id;
};

bool cmp(qry a,qry b) { return a.r > b.r; }

int ai[200005];
int papx[200005];
int lapx[200005];

qry qi[200005];
int ansi[200005];

int main()
{
    const int n = getint();
    const int m = getint();
    for(int i=1; i<=n; ++i)
    {
        ai[i] = getint();
    }

    for(int i=1; i<=n; ++i)
    {
        papx[i] = lapx[ai[i]];
        lapx[ai[i]] = i;
    }

    init();
    for(int i=0; i<=trin; ++i)
    {
        fix(i+1,lapx[i]);
    }

    for(int i=1; i<=m; ++i)
    {
        qi[i].l = getint();
        qi[i].r = getint();
        qi[i].id = i;
    }
    sort(qi+1,qi+1+m,cmp);

    int qtop = 1;
    for(int i=n; i>=1; --i)
    {
        while(qi[qtop].r == i)
        {
            ansi[qi[qtop].id] = query(qi[qtop].l);
            ++qtop;
        }
        fix(ai[i]+1,papx[i]);
    }

    for(int i=1; i<=m; ++i)
    {
        putint(ansi[i]);
        putchar('\n');
    }
}