【题解】Luogu P5251 [LnOI2019]第二代图灵机

原题传送门

前置芝士：珂朵莉树

珂朵莉树的主要功能是区间赋值

这道题还算明显（操作2）

一开始看见这题觉得很毒瘤，但仔细想想发现颜色和数字之间没有什么关系

我们一共要维护三个东西：

1.区间和：树状数组就珂以了

2.区间最大值：写棵线段树

3.颜色：写珂朵莉树

查询的是连续的区间，尺取法就珂以了（尺取法就像单调队列一样）

复杂度：\(O(q\log^2n)\)(q次查询，尺取平均\(\log n\)，线段树/树状数组\(\log n\))

#include <bits/stdc++.h>
#define IT set<node>::iterator 
#define N 100005
#define inf 0x3f3f3f3f
#define getchar nc
using namespace std;
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    register int x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}
inline void write(register int x)
{
    if(!x)putchar('0');if(x<0)x=-x,putchar('-');
    static int sta[20];register int tot=0;
    while(x)sta[tot++]=x%10,x/=10;
    while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
    return a>b?a:b;
}
inline int Min(register int a,register int b)
{
    return a<b?a:b;
}
int n,m,cs;
int t[N];
inline void update(register int x,register int val)
{
    for(register int i=x;i<=n;i+=i&(-i))
        t[i]+=val;
}
inline int query(register int x)
{
    int res=0;
    for(register int i=x;i;i-=i&(-i))
        res+=t[i];
    return res;
}
inline int ask(register int l,register int r)
{
    return query(r)-query(l-1);
}
int tr[N<<3];
inline void pushup(register int x)
{
    tr[x]=Max(tr[x<<1],tr[x<<1|1]);
}
inline void updatemaxx(register int x,register int l,register int r,register int pos,register int val)
{
    if(l==r)
    {
        tr[x]=val;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid)
        updatemaxx(x<<1,l,mid,pos,val);
    else
        updatemaxx(x<<1|1,mid+1,r,pos,val);
    pushup(x);
}
inline int querymaxx(register int x,register int l,register int r,register int L,register int R)
{
    if(L<=l&&r<=R)
        return tr[x];
    int res=0,mid=l+r>>1;
    if(L<=mid)
        res=Max(res,querymaxx(x<<1,l,mid,L,R));
    if(R>mid)
        res=Max(res,querymaxx(x<<1|1,mid+1,r,L,R));
    return res;
}
struct node{
    int l,r;
    mutable int v;
    node(int L,int R=-1,int V=0):l(L),r(R),v(V){}
    bool operator<(const node& o)const{
        return l<o.l;
    }
};
set<node> s;
IT split(register int pos)
{
    IT it=s.lower_bound(node(pos));
    if(it!=s.end()&&it->l==pos)
        return it;
    --it;
    int L=it->l,R=it->r,V=it->v;
    s.erase(it);
    s.insert(node(L,pos-1,V));
    return s.insert(node(pos,R,V)).first;
}
inline void assign_val(register int l,register int r,register int val)
{
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr);
    s.insert(node(l,r,val));
}
int tex[N];
inline int query1(register int l,register int r)
{
    int ans=inf,left=cs;
    memset(tex,0,sizeof(tex));
    IT itr=split(r+1),itl=split(l),L,R;
    --itl;
    L=R=itl;
    while(R!=itr)
    {
        if(L!=itl)
        {
            if(--tex[L->v]==0)
                ++left;
        }
        ++L;
        while(left&&R!=itr)
        {
            ++R;
            if(++tex[R->v]==1)
                --left;
        }
        if(R==itr)
            break;
        while(!left&&L!=R)
        {
            if(--tex[L->v]==0)
                ++left;
            ++L;
        }
        if(left)
        {
            --L;
            ++tex[L->v];
            --left;
        }
        ans=Min(ans,ask(L->r,R->l));
    }
    return ans;
}
int p[N];
inline int query2(register int l,register int r)
{
    memset(p,0,sizeof(p));
    int ans=querymaxx(1,1,n,l,r);
    IT itr=split(r+1),itl=split(l),L,R;
    R=itl--;
    L=itl;
    while(R!=itr)
    {
        if(L!=itl)
            p[L->v]=0;
        ++L;
        p[L->v]=1;
        while(R->l<L->r)
            ++R;
        if(L==R)
            ++R;
        if(R==itr)
            break;
        while(!p[R->v]&&R!=itr&&R->l==R->r)
        {
            p[R->v]=1;
            ++R;
        }
        if(R==itr)
            --R;
        else if(!p[R->v])
            p[R->v]=1;
        else
            --R;
        if(L==R)
            continue;
        ans=Max(ans,ask(L->r,R->l));
    }
    return ans;
}
int main()
{
    n=read(),m=read(),cs=read();
    s.insert(node(0,0,-1)),s.insert(node(n+1,n+1,-1));
    for(register int i=1;i<=n;++i)
    {
        int x=read();
        update(i,x);
        updatemaxx(1,1,n,i,x);
    }
    for(register int i=1;i<=n;++i)
    {
        int x=read();
        s.insert(node(i,i,x));
    }
    int opt,l,r,x;
    while(m--)
    {
        opt=read();
        if(opt==1)
        {
            l=read(),x=read();
            update(l,x-ask(l,l));
            updatemaxx(1,1,n,l,x);
        }
        else if(opt==2)
        {
            l=read(),r=read(),x=read();
            assign_val(l,r,x);
        }
        else if(opt==3)
        {
            l=read(),r=read();
            int ans=query1(l,r);
            if(ans==inf)
                puts("-1");
            else
                write(ans),puts("");
        }
        else
        {
            l=read(),r=read();
            write(query2(l,r)),puts("");
        }
    }
    return 0;
}

【题解】Luogu P5251 [LnOI2019]第二代图灵机

原文：https://www.cnblogs.com/yzhang-rp-inf/p/10507386.html