NEKAMELEONI —— 线段树优化

This way

题意：

给你n个数，每个数的值不超过k，接下来有m个询问，有两种操作：
1 x v表示将位置x的值变成v
2 输出包含1~k的所有值的区间

题解：

这个一看就是尺取，但是尺取的时间复杂度太大，然后又有单点更新，然后的话又可以将状态合并，可以用线段树优化。
线段树求答案的时候肯定是左子树的后缀加上右子树的前缀来搞，那么我们就需要维护前后缀上每个值的位置，但是如果单个值去维护的话，检查又要花掉时间。此时发现k=50，那么可以用longlong来维护所有的状态，这里不是说$2^{50}$250种状态都放到线段树里，而是前缀中包含50个数的最多50个状态。然后后缀也是。
线段树合并的时候，先将左子树的前缀赋给这个点，然后再枚举右子树的所有状态，看是否要进行合并，因为左子树的前缀一定是比右子树的前缀更优的，那么只有右子树有了左子树没有的值的时候才进行合并。后缀同样。
最后进行尺取，尺取肯定是左子树的后缀和右子树的前缀进行尺取。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5,M=55;
struct node{
    ll s;
    int p;
}pre[N*4][M],suf[N*4][M];
int ans[N*4],num[N*4],a[N];
ll mx;

void push_up(int root){
    ans[root]=min(ans[root<<1],ans[root<<1|1]);
    
    for(int i=1;i<=num[root<<1];i++)
        pre[root][i]=pre[root<<1][i];
    int top=num[root<<1];
    for(int i=1;i<=num[root<<1|1];i++)
        if((pre[root][top].s&pre[root<<1|1][i].s)!=pre[root<<1|1][i].s)
            pre[root][++top]={pre[root][top-1].s|pre[root<<1|1][i].s,pre[root<<1|1][i].p};
            
    num[root]=top;
    for(int i=1;i<=num[root<<1|1];i++)
        suf[root][i]=suf[root<<1|1][i];
    top=num[root<<1|1];
    for(int i=1;i<=num[root<<1];i++)
        if((suf[root][top].s&suf[root<<1][i].s)!=suf[root<<1][i].s)
            suf[root][++top]={suf[root][top-1].s|suf[root<<1][i].s,suf[root<<1][i].p};
            
    int p=1;
    for(int i=num[root<<1];i;i--){
        while(p<=num[root<<1|1]&&(suf[root<<1][i].s|pre[root<<1|1][p].s)<mx)p++;
        if(p<=num[root<<1|1])
            ans[root]=min(ans[root],pre[root<<1|1][p].p-suf[root<<1][i].p+1);
    }
}
void build(int l,int r,int root){
    if(l==r){
        pre[root][1]=suf[root][1]={1ll<<(a[l]-1),l};
        num[root]=1;
        ans[root]=1e9;
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    push_up(root);
}
void update(int l,int r,int root,int p,int v){
    if(l==r){
        pre[root][1]=suf[root][1]={1ll<<(v-1),l};
        return ;
    }
    int mid=l+r>>1;
    if(mid>=p)
        update(l,mid,root<<1,p,v);
    else
        update(mid+1,r,root<<1|1,p,v);
    push_up(root);
}
int main()
{
    int n,k,m;
    scanf("%d%d%d",&n,&k,&m);
    mx=(1ll<<k)-1;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,n,1);
    while(m--){
        int op;
        scanf("%d",&op);
        if(op==1){
            int v,p;
            scanf("%d%d",&p,&v);
            update(1,n,1,p,v);
        }
        else
            printf("%d\n",ans[1]<=n?ans[1]:-1);
    }
    return 0;
}