题解：P1638 逛画展

· · 题解

主要思路：线段树

我们对 m 维护一个线段树，树上第 i 个点表示第 i 个人的画最近一次出现的位置。初始时全部值都赋成 0 然后执行如下操作。

我们从小到大遍历所有的画，不断更新树上节点的值。假设我们遍历到当前点满足了答案，可以证明，当所有画的位置都距离当前点最近时，答案是最优的。

这样做还有一个好处：我们可以直接求出这个最优的答案。每次更新节点之后，我们对树上全部节点取一个最小值，假如这个最小值是 0，那么说明尚有未遍历到的节点。否则说明全部点都遍历到了，符合答案要求，此时，从这个最小值到当前节点就是所求区间。

注意到，因为我们只需要查询根节点的最值，因此这个线段树是 O(log\ m) 修改，O(1) 查询的。核心代码复杂度 O(n\ log\ m)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[1000001];
struct tree{
    int l,r;
    int min;
}t[8001];
#define tol (id*2)
#define tor (id*2+1)
#define mid(l,r) mid=((l)+(r))/2
void build(int id,int l,int r){
    t[id].l=l;t[id].r=r;t[id].min=0;
    if(l==r){
        return;
    }
    int mid(l,r);
    build(tol,l,mid);
    build(tor,mid+1,r);
}
void change(int id,int p,int val){
    if(t[id].l==t[id].r){
        t[id].min=val;return;
    }
    if(p<=t[tol].r) change(tol,p,val);
    else change(tor,p,val);
    t[id].min=min(t[tol].min,t[tor].min);
}
int ask(){
    return t[1].min;
}
int main(){
    int cnt=0;int l=0,r=0;
    ios::sync_with_stdio(false);
    cin>>n>>k;int x,y;
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    build(1,1,k);
    int ans=0x7fffffff;
    for(int i=1;i<=n;++i){
        change(1,a[i],i);
        if(ask()!=0){
            if(ans>i-ask()){
                l=ask();r=i;
                ans=r-l;
            }
        }
    }
    cout<<l<<" "<<r;
}