P7230

思路

显然是数据结构题。

然后发现分块很难做（其实可以用

O(N\sqrt{N}\log N)

的分块做出，并跑到最优解第

3

），然后考虑线段树。

发现对于判断一个区间是否满足题目要求并不简单，所以考虑转话。注意到

k

很小，所以可以装压。考虑如果一个区间所有数取

2

的幂，然后并起来，如果等于

2^k-1

则一定满足，否则不满足。

难点在于合并区间的 pushup 操作。

对于线段树上的每一个节点，考虑它的答案。

具体的，分三种情况讨论。第一种和第二种是通过孩子节点转移，第三种是所有满足条件的横跨两个孩子的范围的区间的最小长度。

对于第三种情况，可以在线段树上多维护几个值方便转移。发现所有能对答案造成贡献的第三类区间，一定由左区间的不超过

k

个后缀区间和右区间的不超过

k

个前缀区间并起来。

这些能对答案造成贡献的区间一定是它里面第一次出现了一个数字的区间。

然后维护这

k

个区间，计算答案时双指针即可。

剩下的和线段树模板没有区别。

时间复杂度

O(Nk\log{N}+Qk\log{N})

，空间复杂度

O(Nk)

，无须卡常即可通过。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
typedef long long ll;
struct bit//状态和位置
{
    ll u;
    int x;
};
struct T
{
    bit l[51],r[51];
    int x,cntl,cntr;
}w[4*N];
ll m;
int a[N];
void pushup(int u,int l,int r)
{
    int mid=(l+r)>>1;
//合并左右区间的前后缀最值
    w[u].cntl=w[u<<1].cntl;
    w[u].cntr=w[u<<1|1].cntr;
    for(int i=1;i<=w[u<<1].cntl;i++)
        w[u].l[i]=w[u<<1].l[i];
    for(int i=1;i<=w[u<<1|1].cntr;i++)
        w[u].r[i]=w[u<<1|1].r[i];
    ll x=w[u<<1].l[w[u<<1].cntl].u,y=w[u<<1|1].r[w[u<<1|1].cntr].u;
    for(int i=1;i<=w[u<<1|1].cntl;i++)
        if((w[u<<1|1].l[i].u|x)>w[u].l[w[u].cntl].u)
            w[u].l[++w[u].cntl]={x|w[u<<1|1].l[i].u,mid-l+1+w[u<<1|1].l[i].x};
    for(int i=1;i<=w[u<<1].cntr;i++)
        if((w[u<<1].r[i].u|y)>w[u].r[w[u].cntr].u)
            w[u].r[++w[u].cntr]={y|w[u<<1].r[i].u,r-mid+w[u<<1].r[i].x};
//计算答案
    w[u].x=min(w[u<<1].x,w[u<<1|1].x);
    int t=1;
    for(int i=w[u<<1].cntr;i>=1;i--)
    {
        while(t<=w[u<<1|1].cntl&&(w[u<<1].r[i].u|w[u<<1|1].l[t].u)<m)t++;
        if(t>w[u<<1|1].cntl)break;
        w[u].x=min(w[u].x,w[u<<1].r[i].x+w[u<<1|1].l[t].x);
    }
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        w[u].l[++w[u].cntl]={1ll<<(a[l]-1),1};
        w[u].r[++w[u].cntr]={1ll<<(a[l]-1),1};
        if(m==1)w[u].x=1;
        else w[u].x=1e9;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u,l,r);
}
void add(int u,int l,int r,int x,int y)
{
    if(l==r)
    {
        w[u].l[1]={1ll<<(y-1),1};
        w[u].r[1]={1ll<<(y-1),1};
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=x)add(u<<1,l,mid,x,y);
    else add(u<<1|1,mid+1,r,x,y);
    pushup(u,l,r);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,T;
    cin>>n>>k>>T;
    m=(1ll<<k)-1;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(T--)
    {
        int op,x,y;
        cin>>op;
        if(op==2)
        {
            if(w[1].x==1e9)cout<<"-1\n";
            else cout<<w[1].x<<'\n';
        }
        else
        {
            cin>>x>>y;
            add(1,1,n,x,y);
        }
    }
    return 0;
}

文章操作

思路

代码

相关推荐

评论

P7230