题解 P5251 【[LnOI2019]第二代图灵机】
珂朵莉树+线段树+树状数组。
好毒瘤的题……卡了一页的常数……常数大真的伤不起啊……
首先题目已经非常明显告诉你要用珂朵莉树了，那么我们考虑其他的东西怎么存。
首先要维护区间和，用线段树可以做，但是我们考虑一下还是用树状数组吧，空间常数比较小一点……然后要维护区间最值，这个直接用线段树就行了，不谈。
至于如何查询，建议百度“尺取法”进行学习。
// luogu-judger-enable-o2
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define MAXN 100005
#define inf 2147483647
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
char sr[1<<21],z[20];
int C=-1,Z;
using namespace std;
int n,m,col,a[MAXN];
template <typename T> void Read(T &x)
{
x=0;
register int fu=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') fu=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch-48);
x*=fu;
}
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]='-';
x=-x;
}
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);
sr[++C]=chr;
}
struct TreeArray
{
int c[MAXN];
inline int lowbit(register int x)
{
return x&-x;
}
inline void Modify(register int x,register int val)
{
for(;x<=n;x+=lowbit(x)) c[x]+=val;
}
inline int Get(register int x)
{
register int res=0;
for(;x;x-=lowbit(x)) res+=c[x];
return res;
}
inline int Query(register int l,register int r)
{
return Get(r)-Get(l-1);
}
}TA;
struct SegmentTree
{
int t[MAXN<<3];
inline void PushUp(register int rt)
{
t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
void Modify(register int rt,register int l,register int r,register int pos,register int val)
{
if(l==r)
{
t[rt]=val;
return;
}
register int mid=l+r>>1;
if(pos<=mid) Modify(rt<<1,l,mid,pos,val);
else Modify(rt<<1|1,mid+1,r,pos,val);
PushUp(rt);
}
int Query(register int rt,register int l,register int r,register int tl,register int tr)
{
if(tl<=l && r<=tr) return t[rt];
register int mid=l+r>>1,res=0;
if(tl<=mid) res=max(res,Query(rt<<1,l,mid,tl,tr));
if(tr>mid) res=max(res,Query(rt<<1|1,mid+1,r,tl,tr));
return res;
}
}T;
#define iter set<Node>::iterator
struct Node
{
int l,r;
mutable int val;
friend bool operator < (const Node &x,const Node &y)
{
return x.l<y.l;
}
};
set <Node> s;
inline iter Split(register int pos)
{
iter it=s.lower_bound((Node){pos,pos,-1});
if(it!=s.end() && it->l==pos) return it;
--it;
Node x=*it;
s.erase(it);
s.insert((Node){x.l,pos-1,x.val});
return s.insert((Node){pos,x.r,x.val}).first;
}
inline void Assign(register int l,register int r,register int val)
{
iter R=Split(r+1),L=Split(l);
s.erase(L,R);
s.insert((Node){l,r,val});
}
inline int Query1(register int l,register int r)
{
memset(a,0,sizeof(a));
register int res=inf,cnt=col;
iter R=Split(r+1),L=Split(l);
--L;
iter i=L,j=L;
while(j!=R)
{
if(i!=L && --a[i->val]==0) ++cnt;
++i;
while(cnt && j!=R)
{
++j;
if(++a[j->val]==1) --cnt;
}
if(j==R) break;
while(!cnt && i!=j)
{
if(--a[i->val]==0) ++cnt;
++i;
}
if(cnt)
{
--i;
--cnt;
++a[i->val];
}
res=min(res,TA.Query(i->r,j->l));
}
return res;
}
inline bool Check(iter l,iter r)
{
if(l==r) return 1;
++l;
for(iter it=l;it!=r;++it) if(it->r!=it->l) return 0;
return 1;
}
inline int Query2(register int l,register int r)
{
memset(a,0,sizeof(a));
register int res=T.Query(1,1,n,l,r);
iter R=Split(r+1),L=Split(l);
iter i=L,j=L;
while(j!=R)
{
++a[j->val];
while(!Check(i,j))
{
--a[i->val];
++i;
}
while(i!=j && a[j->val]>1)
{
--a[i->val];
++i;
}
if(i!=j) res=max(res,TA.Query(i->r,j->l));
++j;
}
return res;
}
int main()
{
Read(n);
Read(m);
Read(col);
s.insert((Node){0,0,-1});
s.insert((Node){n+1,n+1,-1});
for(register int i=1;i<=n;++i)
{
register int x;
Read(x);
TA.Modify(i,x);
T.Modify(1,1,n,i,x);
}
for(register int i=1;i<=n;++i)
{
register int x;
Read(x);
s.insert((Node){i,i,x});
}
while(m--)
{
register int opt,x,y,z;
Read(opt);
Read(x);
Read(y);
if(opt==1)
{
TA.Modify(x,y-TA.Query(x,x));
T.Modify(1,1,n,x,y);
}
else if(opt==2)
{
Read(z);
Assign(x,y,z);
}
else if(opt==3)
{
register int res=Query1(x,y);
Print(res==inf?-1:res);
}
else if(opt==4)
{
register int res=Query2(x,y);
Print(res);
}
}
return Ot(),0;
}