rt

在一半的点 TLE，其他也不是很正常

#include<bits/stdc++.h>
#define R register
using namespace std;
inline void read(int &x){
	char ch;
	while(ch = getchar(), ch < '!'); x = ch - 48;
	while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
const int MAXN=1e5+5;
const int inf=1e9;
int n,m,c;
int a[MAXN],b[MAXN];
struct Tree{
    int sum,mx,mn;
    Tree(int sum=0,int mx=-inf,int mn=inf):sum(sum),mx(mx),mn(mn){};
    inline friend Tree operator +(Tree a,Tree b){return Tree(a.sum+b.sum,max(a.mx,b.mx),min(a.mn,b.mn));}
}tr[MAXN<<2];
inline void build(int l,int r,int q){
    if(l==r){
        tr[q]=Tree(a[l],a[l],a[l]);
        return ;
    }
    R int mid=l+r>>1;
    build(l,mid,q*2);
    build(mid+1,r,q*2+1);
    tr[q]=tr[q*2]+tr[q*2+1];
}
inline int query_sum(int l,int r,int ql,int qr,int q){
    if(l==r)return tr[q].sum;
    R int mid=l+r>>1,ans=0;
    if(ql<=mid)ans+=query_sum(l,mid,ql,qr,q*2);
    if(mid<qr)ans+=query_sum(mid+1,r,ql,qr,q*2+1);
    return ans;
}
inline int query_mx(int l,int r,int ql,int qr,int q){
    if(l==r)return tr[q].mx;
    R int mid=l+r>>1,ans=-inf;
    if(ql<=mid)ans=max(ans,query_mx(l,mid,ql,qr,q*2));
    if(mid<qr)ans=max(ans,query_mx(mid+1,r,ql,qr,q*2+1));
    return ans;
}
inline int query_mn(int l,int r,int ql,int qr,int q){
    if(l==r)return tr[q].mn;
    R int mid=l+r>>1,ans=inf;
    if(ql<=mid)ans=min(ans,query_mn(l,mid,ql,qr,q*2));
    if(mid<qr)ans=min(ans,query_mn(mid+1,r,ql,qr,q*2+1));
    return ans;
}
inline void update(int l,int r,int ql,int q,int k){
    if(l==r){
        tr[q]=Tree(k,k,k);
        return ;
    }
    R int mid=l+r>>1;
    if(ql<=mid)update(l,mid,ql,q*2,k);
    else update(mid+1,r,ql,q*2+1,k);
    tr[q]=tr[q*2]+tr[q*2+1];
}
#define iter set<ODT>::iterator
struct ODT{
    int l,r;mutable int v;
    ODT(int l,int r=0,int v=0):l(l),r(r),v(v){};
    inline friend bool operator <(ODT a,ODT b){
        return a.l<b.l;
    }
};
set<ODT>s;
inline iter split(int pos){
    iter it=--s.upper_bound(ODT(pos));
    if(it->l==pos)return it;
    int l=it->l,r=it->r,v=it->v;
    s.erase(it);
    s.insert(ODT(l,pos-1,v));
    return s.insert(ODT(pos,r,v)).first;
}
inline void assign(int l,int r,int x){
    iter ir=split(r+1),il=split(l);
    s.erase(il,ir);
    s.insert(ODT(l,r,x));
}
int cnt[MAXN];
inline int R1(int l,int r){
    if(c==1)return query_mn(1,n,l,r,1);
    memset(cnt,0,sizeof cnt);
    iter ir=split(r+1),il=split(l),i=il;
    int cntt=0,ans=inf,tot=0;
    while(i!=ir){
        if(!cnt[i->v])tot++;cnt[i->v]++;
        while(tot==c){
            cntt=query_sum(1,n,il->r,i->l,1);
            ans=min(ans,cntt);
            cnt[il->v]--;if(!cnt[il->v])tot--;
            il++;
        }
        i++;
    }
    if(ans==inf)return -1;
    return ans;
}
inline int R2(int l,int r){
    memset(cnt,0,sizeof cnt);
    iter ir=split(r+1),il=split(l);
    int cntt=0,ans=query_mx(1,n,l,r,1);
    iter i=il;
    while(i!=ir){
        cnt[i->v]++;
        while(i!=il&&cnt[i->v]>1)cnt[(il++)->v]--;
        if(i!=il){
            cntt=query_sum(1,n,il->r,i->l,1);
            ans=max(ans,cntt);
        }
        if(i->l!=i->r){
            while(i!=il)
                cnt[(il++)->v]--;
        }
        i++;
    }
    return ans;
}
int main(){
    read(n),read(m),read(c);
    for(R int i=1;i<=n;i++)read(a[i]);
    build(1,n,1);
    for(R int i=1;i<=n;i++)read(b[i]);
    int lst=1;
    b[n+1]=-1;
    for(R int i=1;i<=n+1;i++)
        if(b[lst]!=b[i]){
            s.insert(ODT(lst,i-1,b[lst]));
            lst=i;
        }
    for(R int i=1,opt,l,r,x;i<=m;i++){
        read(opt);
        if(opt==1){
            read(l),read(r);
            update(1,n,l,1,r);
        }
        if(opt==2){
            read(l),read(r),read(x);
            assign(l,r,x);
        }
        if(opt==3){
            read(l),read(r);
            printf("%d\n",R1(l,r));
        }
        if(opt==4){
            read(l),read(r);
            printf("%d\n",R2(l,r));
        }
    }
}