珂朵莉树的主要功能是区间赋值
这道题还算明显（操作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;
}
