首页 > 其他分享 >数据结构杂题乱记

数据结构杂题乱记

时间:2024-10-31 21:21:30浏览次数:1  
标签:rt 乱记 val int lt 区间 rn 数据结构 杂题

由于是杂题乱记所以题目大多数不会太难。

目录

P2572 [SCOI2010] 序列操作

题目内容

给你一个 \(01\) 序列,支持 \(5\) 种操作:

  • 0 l r区间赋值为 \(0\);
  • 1 l r区间赋值为 \(1\);
  • 2 l r区间取反,即 \(0\) 变 \(1\)、\(1\) 变 \(0\);
  • 3 l r询问区间 \(1\) 总数。
  • 4 l r询问区间最长 \(1\) 连续段长度。

思路

看到区间赋值,珂朵莉树板子题,然后翻看讨论区,发现珂朵莉树被Hack了,于是老老实实打线段树。同色连续段问题,对于每个节点开一个三元组,表示区间最长连续段长度,以区间左端点为左边界的最长连续段长度,以区间右端点为右边界的最长连续段长度。合并直接做即可。由于有区间翻转,所以再保存一个 \(0\) 的连续段三元组,更新时直接把 \(0,1\) 的三元组交换即可。注意如果左区间颜色完全一致,则父亲区间的左端点最长连续段长度为左区间的整体长度+右区间的左端点最长连续段长度。然后对于三个修改操作,分别记它们的 \(lazy\) 标记为 \(lazy0,lazy1,lazy2\),则有:

  • 如果当前操作为 \(0\) 或 \(1\),则清空其余标记然后赋值。

  • 如果当前操作为 \(2\) 且该区间有 \(0\) 标记,删除 \(0\) 标记改为 \(1\) 标记,进行相应的赋值,不加 \(2\) 标记;有 \(1\) 标记同理。

  • 如果当前操作为 \(2\) 且该区间没有 \(0\) 或 \(1\) 标记,则进行交换操作,然后对 \(2\) 标记取反,即无变为有、有变为无。

容易发现这样操作一个节点最多只会同时带有 \(1\) 种标记。无论是更新时的加标记还是pushdown都这么做就对了。然后这题就比较平凡了。为了直观,我把所有东西都分开写了,也许会有更简便的写法。

代码

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
int a,b,c[100001],u,v,w;
struct node
{
	int lid,rid,val;
	bool can;
	node operator +(const node &A)
	{
		register node rn;
		rn.val=max((*this).val,A.val);
		rn.val=max(rn.val,(*this).rid+A.lid);
		if((*this).can)
		{
			rn.lid=(*this).lid+A.lid;
		}
		else
		{
			rn.lid=(*this).lid;
		}
		if(A.can)
		{
			rn.rid=(*this).rid+A.rid;
		}
		else
		{
			rn.rid=A.rid;
		}
		rn.can=(*this).can&A.can;
		return rn;
	}
};
struct Segment_Tree
{
	#define N 400004
	int left[N],right[N],num2[N];
	bool lazy0[N],lazy1[N],lazy2[N];
	node num0[N],num1[N];
	il int ls(int x)
	{
		return x<<1;
	}
	il int rs(int x)
	{
		return x<<1|1;
	}
	il void pushup(int x)
	{
		num0[x]=num0[ls(x)]+num0[rs(x)];
		num1[x]=num1[ls(x)]+num1[rs(x)];
		num2[x]=num2[ls(x)]+num2[rs(x)];
	}
	il void pushdown(int x)
	{
		if(lazy0[x])
		{
			lazy0[x]=false;
			lazy1[ls(x)]=lazy2[ls(x)]=lazy1[rs(x)]=lazy2[rs(x)]=false;
			lazy0[ls(x)]=lazy0[rs(x)]=true;
			ri len=right[ls(x)]-left[ls(x)]+1;
			num0[ls(x)]={len,len,len,true};
			num1[ls(x)]={0,0,0,false};
			num2[ls(x)]=0;
			len=right[rs(x)]-left[rs(x)]+1;
			num0[rs(x)]={len,len,len,true};
			num1[rs(x)]={0,0,0,false};
			num2[rs(x)]=0;
		}
		if(lazy1[x])
		{
			lazy1[x]=false;
			lazy0[ls(x)]=lazy2[ls(x)]=lazy0[rs(x)]=lazy2[rs(x)]=false;
			lazy1[ls(x)]=lazy1[rs(x)]=true;
			ri len=right[ls(x)]-left[ls(x)]+1;
			num0[ls(x)]={0,0,0,false};
			num1[ls(x)]={len,len,len,true};
			num2[ls(x)]=len;
			len=right[rs(x)]-left[rs(x)]+1;
			num0[rs(x)]={0,0,0,false};
			num1[rs(x)]={len,len,len,true};
			num2[rs(x)]=len;
		}
		if(lazy2[x])
		{
			lazy2[x]=false;
			ri len=right[ls(x)]-left[ls(x)]+1;
			if(lazy0[ls(x)]||lazy1[ls(x)])
			{
				swap(lazy0[ls(x)],lazy1[ls(x)]);
				if(lazy0[ls(x)])
				{
					num0[ls(x)]={len,len,len,true};
					num1[ls(x)]={0,0,0,false};
					num2[ls(x)]=0;
				}
				else
				{
					num0[ls(x)]={0,0,0,false};
					num1[ls(x)]={len,len,len,true};
					num2[ls(x)]=len;
				}
			}
			else
			{
				num2[ls(x)]=len-num2[ls(x)];
				swap(num1[ls(x)],num0[ls(x)]);
				lazy2[ls(x)]^=1;
			}
			len=right[rs(x)]-left[rs(x)]+1;
			if(lazy0[rs(x)]||lazy1[rs(x)])
			{
				swap(lazy0[rs(x)],lazy1[rs(x)]);
				if(lazy0[rs(x)])
				{
					num0[rs(x)]={len,len,len,true};
					num1[rs(x)]={0,0,0,false};
					num2[rs(x)]=0;
				}
				else
				{
					num0[rs(x)]={0,0,0,false};
					num1[rs(x)]={len,len,len,true};
					num2[rs(x)]=len;
				}
			}
			else
			{
				num2[rs(x)]=len-num2[rs(x)];
				swap(num1[rs(x)],num0[rs(x)]);
				lazy2[rs(x)]^=1;
			}
		}
	}
	void build(int x,int lt,int rt)
	{
		left[x]=lt;
		right[x]=rt;
		if(left[x]==right[x])
		{
			if(c[lt])
			{
				num2[x]=1;
				num1[x]={1,1,1,true};
			}
			else
			{
				num0[x]={1,1,1,true};
			}
			return;
		}
		ri me=(lt+rt)>>1;
		build(ls(x),lt,me);
		build(rs(x),me+1,rt);
		pushup(x);
	}
	void add0(int x,int lt,int rt)
	{
		if(lt<=left[x]&&right[x]<=rt)
		{
			lazy1[x]=lazy2[x]=false;
			lazy0[x]=true;
			ri len=right[x]-left[x]+1;
			num0[x]={len,len,len,true};
			num1[x]={0,0,0,false};
			num2[x]=0;
			return;
		}
		pushdown(x);
		ri me=(left[x]+right[x])>>1;
		if(lt<=me)
		{
			add0(ls(x),lt,rt);
		}
		if(rt>me)
		{
			add0(rs(x),lt,rt);
		}
		pushup(x);
	}
	void add1(int x,int lt,int rt)
	{
		if(lt<=left[x]&&right[x]<=rt)
		{
			lazy0[x]=lazy2[x]=false;
			lazy1[x]=true;
			ri len=right[x]-left[x]+1;
			num0[x]={0,0,0,false};
			num1[x]={len,len,len,true};
			num2[x]=len;
			return;
		}
		pushdown(x);
		ri me=(left[x]+right[x])>>1;
		if(lt<=me)
		{
			add1(ls(x),lt,rt);
		}
		if(rt>me)
		{
			add1(rs(x),lt,rt);
		}
		pushup(x);
	}
	void add2(int x,int lt,int rt)
	{
		if(lt<=left[x]&&right[x]<=rt)
		{
			ri len=right[x]-left[x]+1;
			if(lazy0[x]||lazy1[x])
			{
				swap(lazy0[x],lazy1[x]);
				if(lazy0[x])
				{
					num0[x]={len,len,len,true};
					num1[x]={0,0,0,false};
					num2[x]=0;
				}
				else
				{
					num0[x]={0,0,0,false};
					num1[x]={len,len,len,true};
					num2[x]=len;
				}
			}
			else
			{
				num2[x]=len-num2[x];
				swap(num1[x],num0[x]);
				lazy2[x]^=1;
			}
			return;
		}
		pushdown(x);
		ri me=(left[x]+right[x])>>1;
		if(lt<=me)
		{
			add2(ls(x),lt,rt);
		}
		if(rt>me)
		{
			add2(rs(x),lt,rt);
		}
		pushup(x);
	}
	int find1(int x,int lt,int rt)
	{
		if(lt<=left[x]&&right[x]<=rt)
		{
			return num2[x];
		}
		pushdown(x);
		ri me=(left[x]+right[x])>>1,rn=0;
		if(lt<=me)
		{
			rn+=find1(ls(x),lt,rt);
		}
		if(rt>me)
		{
			rn+=find1(rs(x),lt,rt);
		}
		return rn;
	}
	node find2(int x,int lt,int rt)
	{
		if(lt<=left[x]&&right[x]<=rt)
		{
			return num1[x];
		}
		pushdown(x);
		ri me=(left[x]+right[x])>>1;
		register node rn1={-1,-1,-1},rn2={-1,-1,-1};
		if(lt<=me)
		{
			rn1=find2(ls(x),lt,rt);
		}
		if(rt>me)
		{
			rn2=find2(rs(x),lt,rt);
		}
		if(rn1.val>=0&&rn2.val>=0)
		{
			return rn1+rn2;
		}
		else
		{
			if(rn1.val>=0)
			{
				return rn1;
			}
			else
			{
				return rn2;
			}
		}
	}
	#undef N
}st;
int main()
{
	scanf("%d%d",&a,&b);
	for(ri i=1;i<=a;i++)
	{
		scanf("%d",&c[i]);
	}
	st.build(1,1,a);
	while(b--)
	{
		scanf("%d%d%d",&u,&v,&w);
		v++;
		w++;
		switch(u)
		{
			case 0:
			{
				st.add0(1,v,w);
				break;
			}
			case 1:
			{
				st.add1(1,v,w);
				break;
			}
			case 2:
			{
				st.add2(1,v,w);
				break;
			}
			case 3:
			{
				printf("%d\n",st.find1(1,v,w));
				break;
			}
			case 4:
			{
				printf("%d\n",st.find2(1,v,w).val);
				break;
			}
		}
	}
	return 0;
}

标签:rt,乱记,val,int,lt,区间,rn,数据结构,杂题
From: https://www.cnblogs.com/ywhhdjser-97/p/18518910

相关文章

  • 链表(数据结构)
    一.单链表1.1概念与结构再上一篇中我们讲到顺序表,但是顺序表也是有很多的问题,像申请的空间过多过少或者增容该才能不浪费空间,今天我们就来认识一个新的知识,叫做链表,链表也是线性表的一种,链表是一种物理存储结构上非连续、非顺序的存储结构,数据结构的逻辑顺序是通过链表中的......
  • Python常用数据结构
    1.列表(List)列表是Python中最灵活的数据结构之一,像个能装万物的大箱子。你可以把任何类型的对象放进来,甚至可以把列表放进列表里,真是个魔法箱!功能特性:可变:你可以随时增加、删除、修改列表中的元素。有序:元素按插入顺序排列创建和基本操作:#创建一个空列表my_list=[]......
  • 数据结构 - 散列表,三探之代码实现
    相信通过前面两章对散列表的学习,大家应该已经掌握了散列表的基础知识,今天我们就选用简单的取模方式构建散列函数,分别实现链式法和开放寻址法中的线性探测法来解决碰撞问题,而再散列法则以方法的形式分别在两种实现方法中实现。01、链式法实现1、元素定义通过前面链式......
  • 杂题随笔 10.31 两道LIS相关的题
    https://www.luogu.com.cn/problem/AT_abc354_f题意:给定一个序列a,求出所有的i使得任意一个a的最长子序列包含i。解法:我们先求这个序列的LIS的长度maxx,然后再去正着求一遍最长上升子序列和反着求一遍最长下降子序列即可,如果拼起来等于maxx那么说明i这个点是满足要求的点。注意细......
  • Day65 小贪心 & 自选杂题
    哎怎么必可公益赛被爆破了,怎么lifan还加了几道我们的训练题目作为补偿。CF不知道死了多久了,一上午都没有打成duel!今天上午精神状态明显好了很多,可能和咖啡有点关系吧。按照时间顺序写题吧。AT_arc070_b可以进行撤销背包,也可以算前后缀背包,都是记录方案数。不难的。AT_a......
  • LUOGU_进阶数据结构
    LUOGU_进阶数据结构二叉堆P10977CuttheSequence:因为DP的值是单调递增的,所以可能的决策点只有最远的合法位置与那些后缀最大值段的左端点,用单调队列+可删除堆(懒标记)做。如果\(\exista<0\),怎么做?CDQ优化DP,可以做!!并查集P10350ModernizacjaBajtocji:把二选一的居民放进一......
  • 【数据结构多彩画卷】不要只会普通的二叉树了 , 你听说过用二叉树来排序吗? 【二叉搜索
    本篇会加入个人的所谓鱼式疯言❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • 数据结构之你就背吧!(更新中)
    数据的逻辑结构在存储器中的映象有哪几种方法?顺序映象非顺序映象算法的性质及解释?有穷性:步骤或规则是有限的,在有穷步后结束。确定性:每条规则或指令无二义性;算法执行路径唯一(相同输入只能得到相同输出)。可行性:每个计算步骤能在有限时间内完成。输入:有一个或多个外部输......
  • 强连通分量学习笔记+杂题
    图论系列:前言:僕は明快さ故にアイロニー優柔不断なフォローミー後悔後悔夜の果て相关题单:戳我一.强连通分量相关定义基本摘自oiwiki,相关定义还是需要了解。(实际就是搬了个oiwiki)强连通分量主要在研究有向图可达性,针对的图类型为有向弱联通图。1.强连通定义强连通:对......
  • 14 数据结构
    算法数据存在内存的格式是什莫?数据最好是结构化的,方便读取,所以有了数据结构。1.数组(列表,向量),数组的值一个个连续存在内存里,可以把多个值存在数组变量里2.数组的亲戚是字符串,就是字母,标点符号,数字组成的数组3.多个变量打包到一起叫做结构体,4.一个结构体叫做节点,存一个变量......