欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NEKAMELEONI —— 线段树优化

程序员文章站 2022-06-04 16:18:56
...

This way

题意:

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

题解:

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

#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;
}