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

· · 题解

【题目大意】

给定数列和每个位置对应的颜色

进行以下操作

  1. 改变某个数字

  2. 对某一段颜色区间赋值

  3. 询问某段区间内包含所有颜色的子区间所对应的数字和的最小值

  4. 询问某段区间内没有重复颜色的子区间所对应的数字和的最大值

【分析】

我们的关注点在区间赋值和数据随机生成上

自然而然就想到了最可爱的珂朵莉树

于是2操作迎刃而解

有珂朵莉树的加持，其他操作暴力即可

3操作

要求子区间内要包含所有颜色，维护两个指针即可

j和i代表左右端点，显然i在此段最左边，j在此段最后边

每次i往后走一步，j根据目前数据调整

需要记录当前ij之间各个颜色的数量和颜色的种类数

求区间和可以用线段树

4操作

与3类似，同样是维护指针，但是细节更多

如果ij相等，应选择当前段内最大值，同样可以用线段树维护

如果ij不等，显然i在段左，j在段右

如果i段大小不为1，区间内就不能包含完整的i段了，应同时调整j

1操作就不用多说了，维护线段树时稍微处理一下即可

【算法】

珂朵莉树+线段树

【代码】

#include<bits/stdc++.h>
#define IN inline
#define RE register
#define IT set<node>::iterator
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
using namespace std;
const int maxn=1e5+5,maxc=105,INF=2147483647,maxt=maxn<<2;
int n,m,C;
int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
struct node{
    mutable int l,r,c;
    bool operator <(node b)const{return l<b.l;}
}a[maxn],b[maxn];
set<node> s;
int p[maxn],c[maxn];
struct tree{
    int max,s;
}t[maxt];
tree merge(tree l,tree r){
    tree ret;
    ret.s=l.s+r.s;
    ret.max=max(l.max,r.max);
    return ret;
}
void pushup(int k){
    t[k]=merge(t[ls],t[rs]);
}
void build(int k,int l,int r){
    if(l==r){
        t[k].max=t[k].s=p[l];
        return;
    }
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(k);
}
void update(int k,int l,int r,int x,int v){
    if(l==r){
        t[k].max=t[k].s=v;
        return;
    }
    if(x<=mid) update(ls,l,mid,x,v);
    else update(rs,mid+1,r,x,v);
    pushup(k);
}
tree query(int k,int l,int r,int x,int y){
    if(x<=l&&r<=y) return t[k];
    if(y<=mid) return query(ls,l,mid,x,y);
    if(mid<x) return query(rs,mid+1,r,x,y);
    return merge(query(ls,l,mid,x,mid),query(rs,mid+1,r,mid+1,y));
}
IT it1,it2,it;
IN IT split(RE int x){
    it=s.lower_bound((node){x,0,0});
    if(it!=s.end()&&it->l==x) return it;
    --it;
    int l=it->l,r=it->r,v=it->c;
    s.erase(it);
    s.insert((node){l,x-1,v});
    return s.insert((node){x,r,v}).first;
}
void assign(int l,int r,int v){
    it2=split(r+1),it1=split(l);
    s.erase(it1,it2);
    s.insert((node){l,r,v});
}
int d[maxc];
int query1(int l,int r){
    it2=split(r+1),it1=split(l);
    memset(d,0,sizeof d);
    int cnt=0,sum=0,ret=INF,tot=0;
    for(it=it1;it!=it2;++it) b[++tot]=*it;
    for(int i=1,j=1;i<=tot;i++){
        if(!d[b[i].c]) cnt++;
        d[b[i].c]++;
        while(d[b[j].c]>1) d[b[j].c]--,++j;
        if(cnt==C){
            ret=min(ret,query(1,1,n,b[j].r,b[i].l).s);
        }
    }
    return ret==INF?-1:ret;
}
int query2(int l,int r){
    it2=split(r+1),it1=split(l);
    memset(d,0,sizeof d);
    int sum=0,ret=-INF,tot=0;
    for(it=it1;it!=it2;++it){
        if(b[tot].c==it->c) b[tot].r=it->r;
        else b[++tot]=*it;
    }
    for(int i=1,j=1;i<=tot;i++){
        ret=max(ret,query(1,1,n,b[i].l,b[i].r).max);
        d[b[i].c]++;
        while(d[b[i].c]>1&&j!=i) d[b[j].c]-=b[j].r-b[j].l+1,j++;
        if(i!=j) ret=max(ret,query(1,1,n,b[j].r,b[i].l).s);
        d[b[i].c]+=b[i].r-b[i].l;
        if(b[i].r!=b[i].l) while(j!=i) d[b[j].c]-=b[j].r-b[j].l+1,j++;
    }
    return ret;
}
int main(){
    freopen("P5251.in","r",stdin);
    freopen("P5251.out","w",stdout);
    n=read(),m=read(),C=read();
    for(int i=1;i<=n;i++) p[i]=read();
    build(1,1,n); 
    for(int i=1;i<=n;i++) s.insert((node){i,i,read()});
    s.insert((node){n+1,n+1,0});
    for(int i=1,l,r,x,y;i<=m;i++){
        int k=read();
        if(k==1){
            x=read(),y=read();
            update(1,1,n,x,y);
            p[x]=y;
        }else
        if(k==2){
            l=read(),r=read(),y=read();
            assign(l,r,y);
        }else
        if(k==3){
            l=read(),r=read();
            printf("%d\n",query1(l,r));
        }
        else{
            l=read(),r=read();
            printf("%d\n",query2(l,r));
        }
    }
    return 0;
}