1 条题解

  • 0
    @ 2025-8-24 22:08:43

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar LG_kemeng
    高考冲刺725

    搬运于2025-08-24 22:08:43，当前版本为作者最后更新于2022-11-12 20:30:16，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    珂朵莉+线段树方法

    前缀知识：线段树，珂朵莉树（ODT），双指针

    首先，这题数字和颜色之间明显没有直接的联系，并且一个珂朵莉无法处理。所以我们可以用两个结构分别储存这两个变量。数字要求最小区间和，用线段树储存；颜色区间修改，用珂朵莉储存。

    构造

    颜色

    首先考虑颜色：对于颜色题目只有一个操作， assign()，区间平推。

    数字

    然后考虑数字：建立的线段树要满足下列操作：区间最大、区间最小、区间求和。区间最大和区间最小用做初始化(可能有 c=1c = 1 的情况，初始化答案用区间最大/最小值)。区间求和是题目两问的解。

    所以话说真的有人会在做珂朵莉骗分的时候还加一个线段树吗。

    实现

    操作一

    • 询问区间 [l,r][l,r]， [l,r][l,r] 中包含所有（一共 cc 种）颜色的区间和的最小值。

    先用珂朵莉，左右界为： itr=split(r+1)， itl=split(l)。左右指针初始为 itlitl。右指针 itit 不断 ++，直到找到一个点使颜色 tottot 有 cc 种，更新答案 resres (即返回当前线段树 querysum(itl->r,it->l))。这个时候，考虑将左指针 itlitl ++，并更新 resres。最终返回 resres 即可。

    #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;
}

    注： cnticnt_i 为颜色 ii 出现次数。 add 里面先判断，所以 ++ 在 cntxcnt_x 后面。 del 里面先减，所以 -- 在 cntxcnt_x 前面。线段树 querysum 时，左指针所在区间有尾无头，右指针所在区间有头无尾，所以是 querysum(itl->r,it->l)。

    操作二

    • 求 [l,r][l,r] 中没有重复颜色的最大区间和。

    和上一问思路差不多，同样用双指针实现。不过这一问是不断调整左指针 itlitl，保证右指针的颜色的出现次数为 1。注意特判：如果右指针所在区间的 sizesize 不为 1，因为条件不符合，直接跳过该段，即将左指针移至右指针，右指针 ++，避开这个区间。

    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;
}

    注意：考虑最差情况， resres 初始赋值区间内单点最大值。

    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;
}
    • 1

    [LnOI2019] 第二代图灵机

    信息

    ID
    4209
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 20ms