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

· · 题解

数据结构套路题，就是用的数据结构好多。。。

树状数组维护区间和

线段树维护区间最大值

ODT 维护区间染色信息

然后把三个板子放上来再写一下询问就好了

话说不知道 Sooke 大仙为什么跑这么快

//by Judge
#include<set>
#include<cstring>
#include<iostream>
#define IT std::set<node>::iterator
const int inf=2e9+7;
const int M=1e5+3;
typedef int arr[M];
#ifndef Judge
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
char buf[1<<21],*p1=buf,*p2=buf;
inline void cmax(int& a,int b){if(a<b)a=b;}
inline void cmin(int& a,int b){if(a>b)a=b;}
inline int Max(int a,int b){return a>b?a:b;}
inline int read(){ int x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;
} char sr[1<<21],z[20];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(int x,char chr='\n'){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]=chr;
} int n,m,q; arr ap,f,w; int t[M<<2];
namespace ODT{
    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& b)const{return l<b.l;}
    }; std::set<node> s;
    inline IT split(int pos){ IT it=s.lower_bound(node(pos));
        if(it!=s.end()&&it->l==pos) return it; --it;
        node lit=node(it->l,pos-1,it->v),rit=node(pos,it->r,it->v);
        s.erase(it),s.insert(lit); return s.insert(rit).first; 
    }
    inline void assign(int l,int r,int val=0){
        IT rit=split(r+1),lit=split(l);
        s.erase(lit,rit),s.insert(node(l,r,val));
    }
} using namespace ODT;
namespace seg_tree{
    #define ls k<<1
    #define rs k<<1|1
    #define mid (l+r>>1)
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    #define lowbit(x) (x&-x)
    void update(int k,int l,int r,int x,int v){ if(l==r) return t[k]=v,void();
        if(x<=mid) update(lson,x,v); else update(rson,x,v); t[k]=Max(t[ls],t[rs]);
    }
    int query(int k,int l,int r,int L,int R){
        if(L>r||l>R) return 0; if(L<=l&&r<=R) return t[k];
        return Max(query(lson,L,R),query(rson,L,R));
    }
} using namespace seg_tree;
namespace BIT{
    inline void update(int x,int v){for(;x<=n;x+=lowbit(x)) f[x]+=v;}
    inline int query(int x,int s=0){for(;x;x^=lowbit(x)) s+=f[x]; return s;}
    inline int ask(int l,int r){return query(r)-query(l-1);}
} using namespace BIT;
inline int query1(int l,int r){
    int ans=inf,lef; memset(ap,0,sizeof ap);
    IT rit=split(r+1),lit=split(l),L,R; --lit;
    for(L=R=lit,lef=m;R!=rit;){
        if(L!=lit) --ap[L->v],lef+=!ap[L->v];
        for(++L;lef&&R!=rit;)++R,lef-=!ap[R->v],++ap[R->v];
        if(R==rit) break;
        for(;!lef&&L!=R;++L) --ap[L->v],lef+=!ap[L->v];
        if(lef) --L,++ap[L->v],--lef;
        cmin(ans,ask(L->r,R->l));
    } return ans;
}
inline int query2(int l,int r){
    memset(ap,0,sizeof ap);
    int ans=query(1,1,n,l,r);
    IT rit=split(r+1),lit=split(l),L,R;
    for(L=R=lit;R!=rit;++R){ ++ap[R->v];
        for(;L!=R&&ap[R->v]>1;++L) --ap[L->v];
        if(L!=R) cmax(ans,ask(L->r,R->l));
        for(;L!=R&&R->l!=R->r;++L) --ap[L->v];
    } return ans;
}
int main(){
    n=read(),q=read(),m=read();
    s.insert(node(0,0,-1));
    for(int i=1,x;i<=n;++i) x=read(),
        update(i,x),update(1,1,n,i,x);
    for(int i=1,x;i<=n;++i) x=read(),
        s.insert(node(i,i,x));
    for(int op,l,r,x,ans;q;--q){ op=read();
        if(op==1) l=read(),r=read(),
            update(l,r-ask(l,l)),update(1,1,n,l,r);
        else if(op==2) l=read(),r=read(),
            x=read(),assign(l,r,x);
        else if(op==3) l=read(),r=read(),
            ans=query1(l,r),print(ans==inf?-1:ans);
        else l=read(),r=read(),print(query2(l,r));
    } return Ot(),0;
}