第二代图灵机题解
珂朵莉+线段树方法
前缀知识：线段树，珂朵莉树（ODT），双指针
首先，这题数字和颜色之间明显没有直接的联系，并且一个珂朵莉无法处理。所以我们可以用两个结构分别储存这两个变量。数字要求最小区间和，用线段树储存；颜色区间修改，用珂朵莉储存。
构造
颜色
首先考虑颜色：对于颜色题目只有一个操作， assign()，区间平推。
数字
然后考虑数字：建立的线段树要满足下列操作：区间最大、区间最小、区间求和。区间最大和区间最小用做初始化(可能有
所以话说真的有人会在做珂朵莉骗分的时候还加一个线段树吗。
实现
操作一
- 询问区间
[l,r] ，[l,r] 中包含所有（一共c 种）颜色的区间和的最小值。
先用珂朵莉，左右界为： itr=split(r+1)， itl=split(l)。左右指针初始为 querysum(itl->r,it->l))。这个时候，考虑将左指针
#define add(x) (!cnt[x]++&&++tot)
#define del(x) (!--cnt[x]&&--tot)
inline int Q1(int l,int r)//第一种情况
{
if(c==1)//若c=1,特判,直接取区间最小值就行
return query_min(1,n,1,l,r);
memset(cnt,0,sizeof(cnt));//初始化
IT it_r=split(r+1),it_l=split(l),it=it_l;
register int t,res=INF,tot=0;
while(it!=it_r)//枚举右指针,当有c种颜色时,考虑挪动左指针
{
add(it->color);
while(tot==c)
t=query_sum(1,n,1,it_l->r,it->l),res=min(res,t),del((it_l++)->color);
it++;
}
return res==INF?-1:res;
}注： add 里面先判断，所以 ++ 在 del 里面先减，所以 -- 在 querysum 时，左指针所在区间有尾无头，右指针所在区间有头无尾，所以是 querysum(itl->r,it->l)。
操作二
- 求
[l,r] 中没有重复颜色的最大区间和。
和上一问思路差不多，同样用双指针实现。不过这一问是不断调整左指针
inline int Q2(int l,int r)//第二种情况
{
memset(cnt,0,sizeof(cnt));//初始化
IT it_r=split(r+1),it_l=split(l),it=it_l;
register int t,res=query_max(1,n,1,l,r);
while(it!=it_r)//类似的思路,不断调整左指针,保证右指针的颜色的出现数量始终为1。所以要加一个特判,如果右指针的size不为1,直接跳过,也就是令左指针直接移动到右指针的位置,右指针++
{
cnt[it->color]++;
while(it!=it_l&&cnt[it->color]>1)
cnt[(it_l++)->color]--;
if(it!=it_l)
t=query_sum(1,n,1,it_l->r,it->l),res=max(res,t);
if(it->l!=it->r)
while(it!=it_l)
cnt[(it_l++)->color]--;
it++;
}
return res;
}注意：考虑最差情况，
AC Code
#include<bits/stdc++.h>
using namespace std;
#define N 100000
#define INF 1e9
#define IT set<node>::iterator
#define add(x) (!cnt[x]++&&++tot)
#define del(x) (!--cnt[x]&&--tot)
//----------------------------------------------分割线---------------------------------------------------------------------//
int n,c,a[N+5],v[N+5],cnt[N+5];
//线段树部分
struct tree
{
int S,Mx,Mn;
inline tree(int s=0,int mx=-INF,int mn=INF):S(s),Mx(mx),Mn(mn){}
inline tree operator + (const tree& t) const//重载+,方便运算
{
return tree(S+t.S,max(Mx,t.Mx),min(Mn,t.Mn));
}
}t[N<<2];
inline void build(int l,int r,int rt)//建树
{
if(l==r)
{
t[rt]=tree(v[l],v[l],v[l]);
return ;
}
register int mid=l+r>>1;
build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
t[rt]=t[rt<<1]+t[rt<<1|1];
}
inline int query_sum(int l,int r,int rt,int ql,int qr)//区间和
{
if(ql<=l&&r<=qr) return t[rt].S;
register int mid=l+r>>1;
register int sum=0;
if(ql<=mid)
sum+=query_sum(l,mid,rt<<1,ql,qr);
if(qr>mid)
sum+=query_sum(mid+1,r,rt<<1|1,ql,qr);
return sum;
}
inline int query_max(int l,int r,int rt,int ql,int qr)//区间最大
{
if(ql<=l&&r<=qr) return t[rt].Mx;
register int t,maxx=-INF,mid=l+r>>1;
if(ql<=mid)
maxx=max(maxx,query_max(l,mid,rt<<1,ql,qr));
if(qr>mid)
maxx=max(maxx,query_max(mid+1,r,rt<<1|1,ql,qr));
return maxx;
}
inline int query_min(int l,int r,int rt,int ql,int qr)//区间最小
{
if(ql<=l&&r<=qr) return t[rt].Mn;
register int t,minn=INF,mid=l+r>>1;
if(ql<=mid)
minn=min(minn,query_min(l,mid,rt<<1,ql,qr));
if(qr>mid)
minn=min(minn,query_min(mid+1,r,rt<<1|1,ql,qr));
return minn;
}
inline void Init(int x,int* s)//输入
{
for(register int i=1;i<=x;i++)
v[i]=s[i];
build(1,x,1);
}
inline void Update(int x,int y)//更新
{
register int l=1,r=n,rt=1,mid;
while(l!=r)//二分查找
{
mid=l+r>>1;
if(x<=mid)
r=mid,rt<<=1;
else
l=mid+1,(rt<<=1)|=1;
}
t[rt]=tree(y,y,y);
while(rt>>=1)//向上更新
t[rt]=t[rt<<1]+t[rt<<1|1];
}
//----------------------------------------------分割线---------------------------------------------------------------------//
//珂朵莉树部分
struct node
{
int l,r,color;
inline node(int x=0,int y=0,int p=0):l(x),r(y),color(p){}
inline bool operator < (const node& t) const
{
return l<t.l;
}
};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 tmp=*it;
S.erase(it);
S.insert(node(tmp.l,pos-1,tmp.color));
return S.insert(node(pos,tmp.r,tmp.color)).first;
}
inline void assign(int l,int r,int color)//区间平推
{
IT it_r=split(r+1),it_l=split(l);
S.erase(it_l,it_r);
S.insert(node(l,r,color));
}
inline void _Init(int x,int* s)//输入
{
for(register int i=(s[0]=s[x+1]=-1,1),t=0;i<=x+2;++i)
s[i]^s[i-1]&&(S.insert(node(t,i-1,s[i-1])),t=i);
}
//----------------------------------------------分割线---------------------------------------------------------------------//
//问题求解部分
inline int Q1(int l,int r)//第一种情况
{
if(c==1)//若c=1,特判,直接取区间最小值就行
return query_min(1,n,1,l,r);
memset(cnt,0,sizeof(cnt));//初始化
IT it_r=split(r+1),it_l=split(l),it=it_l;
register int t,res=INF,tot=0;
while(it!=it_r)//枚举右指针,当有c种颜色时,考虑挪动左指针
{
add(it->color);
while(tot==c)
t=query_sum(1,n,1,it_l->r,it->l),res=min(res,t),del((it_l++)->color);
it++;
}
return res==INF?-1:res;//=if(res==INF) return -1;else return res;
}
inline int Q2(int l,int r)//第二种情况
{
memset(cnt,0,sizeof(cnt));//初始化
IT it_r=split(r+1),it_l=split(l),it=it_l;
register int t,res=query_max(1,n,1,l,r);
while(it!=it_r)//类似的思路,不断调整左指针,保证右指针的颜色的出现数量始终为1。所以要加一个特判,如果右指针的size不为1,直接跳过,也就是令左指针直接移动到右指针的位置,右指针++
{
cnt[it->color]++;
while(it!=it_l&&cnt[it->color]>1)
cnt[(it_l++)->color]--;
if(it!=it_l)
t=query_sum(1,n,1,it_l->r,it->l),res=max(res,t);
if(it->l!=it->r)
while(it!=it_l)
cnt[(it_l++)->color]--;
it++;
}
return res;
}
void read(int &x)//官方给的快读,不用白不用(bushi)
{
char ch;
while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
int main()
{
register int T,i,opt,l,r,col;
read(n),read(T),read(c);
for(i=1;i<=n;++i)
read(a[i]);
Init(n,a);
for(i=1;i<=n;++i)
read(a[i]);
_Init(n,a);
while(T--)
{
read(opt),read(l),read(r);
if(opt==1) Update(l,r);
if(opt==2) read(col),assign(l,r,col);
if(opt==3) printf("%d\n",Q1(l,r));
if(opt==4) printf("%d\n",Q2(l,r));
}
return 0;
}