题解：AtCoder AT_awc0063_e Number of Blocks in an Interval

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderE - Number of Blocks in an Interval【题目描述】Takahashi manages a coloring sheet consisting ofN NNcells arranged in a horizontal row. The cells are numbered from1 11toN NNfrom left to right.高桥管理着一个由N NN个单元格横向排列组成的填色纸。单元格从左到右编号为1 11到N NN。Each celli iiis painted with colorC i C_iCi​. In a sequence of cells, a maximal consecutive interval of the same color that cannot be extended further is called ablock. Thenumber of blocksin an interval[ L , R ] [L, R][L,R]is the number of blocks when the cell sequenceC L , C L 1 , … , C R C_L, C_{L1}, \dots, C_RCL​,CL1​,…,CR​is divided into blocks.每个单元格i ii被涂上了颜色C i C_iCi​。在单元格序列中一个无法再扩展的最大、连续、同颜色的区间被称为块。区间[ L , R ] [L, R][L,R]的块数是将单元格序列C L , C L 1 , … , C R C_L, C_{L1}, \dots, C_RCL​,CL1​,…,CR​划分为块后得到的块的数量。For example, if the sequence is1 , 1 , 2 , 2 , 2 , 1 1, 1, 2, 2, 2, 11,1,2,2,2,1, the blocks are( 1 , 1 ) , ( 2 , 2 , 2 ) , ( 1 ) (1, 1), (2, 2, 2), (1)(1,1),(2,2,2),(1), giving3 33blocks, so the number of blocks is3 33.例如如果序列是1 , 1 , 2 , 2 , 2 , 1 1, 1, 2, 2, 2, 11,1,2,2,2,1则块为( 1 , 1 ) , ( 2 , 2 , 2 ) , ( 1 ) (1, 1), (2, 2, 2), (1)(1,1),(2,2,2),(1)共3 33个块因此块数为3 33。Aoki performs a total ofQ QQoperations of the following two types. Process each operation in order and answer the queries.青木将执行总共Q QQ次以下两种类型的操作。按顺序处理每个操作并回答查询。1 L R X: Change the color of all cells in the interval[ L , R ] [L, R][L,R]toX XX.1 L R X将区间[ L , R ] [L, R][L,R]内所有单元格的颜色更改为X XX。2 L R: Output the number of blocks in the current interval[ L , R ] [L, R][L,R].2 L R输出当前区间[ L , R ] [L, R][L,R]的块数。【输入】N NNQ QQC 1 C_1C1​C 2 C_2C2​… \dots…C N C_NCN​T 1 T_1T1​T 2 T_2T2​⋮ \vdots⋮T Q T_QTQ​The first line contains the number of cellsN NNand the number of operationsQ QQ, separated by a space.The second line contains the initial colors of each cellC 1 , C 2 , … , C N C_1, C_2, \dots, C_NC1​,C2​,…,CN​, separated by spaces.Thei ii-th of the followingQ QQlines contains thei ii-th operationT i T_iTi​. Each operation is in one of the following formats:1 L R X: Change the color of all cells in the interval[ L , R ] [L, R][L,R]toX XX.2 L R: A query to find the number of blocks in the current interval[ L , R ] [L, R][L,R].【输出】For each operation2 L R, output the number of blocks in that interval, one per line.【输入样例】6 6 1 1 2 2 2 1 2 1 6 2 2 5 1 3 5 1 2 1 6 1 2 4 3 2 1 6【输出样例】3 2 1 3【算法标签】#线段树#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN200005;intn,q;intw[N];// 线段树节点结构structNode{intl,r;// 节点表示的区间 [l, r]intlc,rc;// 区间左端点的值区间右端点的值intdt;// 懒标记-1 表示没有懒标记intcnt;// 区间内连续颜色段的数量}tr[N*4];// 向上更新节点信息voidpushup(intu){// 左端点值来自左子节点tr[u].lctr[u1].lc;// 右端点值来自右子节点tr[u].rctr[u1|1].rc;// 合并左右子节点的颜色段数量tr[u].cnttr[u1].cnttr[u1|1].cnt;// 如果左子节点的右端点值等于右子节点的左端点值说明中间是连续的需要合并if(tr[u1].rctr[u1|1].lc){tr[u].cnt--;}}// 向下传递懒标记voidpushdown(intu){autoroottr[u],ltr[u1],rtr[u1|1];// 如果有懒标记if(root.dt!-1){// 将懒标记传递给左子节点l.dtroot.dt;l.lcroot.dt;l.rcroot.dt;l.cnt1;// 区间内所有值相同只有一个颜色段// 将懒标记传递给右子节点r.dtroot.dt;r.lcroot.dt;r.rcroot.dt;r.cnt1;// 区间内所有值相同只有一个颜色段// 清除当前节点的懒标记root.dt-1;}}// 构建线段树voidbuild(intu,intl,intr){if(lr)// 叶子节点{tr[u]{l,r,w[l],w[l],-1,1};// 单个元素颜色段数量为1}else{tr[u]{l,r,0,0,-1,0};// 初始化非叶子节点intmid(lr)1;// 递归构建左右子树build(u1,l,mid);build(u1|1,mid1,r);// 向上更新节点信息pushup(u);}}// 区间更新voidupdate(intu,intl,intr,intd){// 如果当前节点区间完全包含在更新区间内if(tr[u].lltr[u].rr){// 设置懒标记tr[u].dtd;// 更新区间左右端点值tr[u].lcd;tr[u].rcd;// 整个区间变为同一种颜色颜色段数量为1tr[u].cnt1;}else{// 向下传递懒标记pushdown(u);intmid(tr[u].ltr[u].r)1;// 递归更新左子区间if(lmid){update(u1,l,r,d);}// 递归更新右子区间if(rmid){update(u1|1,l,r,d);}// 向上更新节点信息pushup(u);}}// 区间查询Nodequery(intu,intl,intr){// 如果当前节点区间完全包含在查询区间内if(tr[u].lltr[u].rr){returntr[u];}else{// 向下传递懒标记pushdown(u);intmid(tr[u].ltr[u].r)1;// 如果查询区间完全在左子树if(rmid){returnquery(u1,l,r);}// 如果查询区间完全在右子树if(lmid){returnquery(u1|1,l,r);}// 查询区间横跨左右子树Node leftquery(u1,l,r);Node rightquery(u1|1,l,r);Node res;// 合并左右子树的结果res.lcleft.lc;// 左端点值来自左子树res.rcright.rc;// 右端点值来自右子树res.cntleft.cntright.cnt;// 合并颜色段数量// 如果左子树的右端点值等于右子树的左端点值说明中间连续需要合并if(left.rcright.lc){res.cnt--;}returnres;}}signedmain(){cinnq;for(inti1;in;i){cinw[i];}// 构建线段树build(1,1,n);while(q--){intop,l,r,x;cinoplr;if(op1)// 更新操作{cinx;update(1,l,r,x);}else// 查询操作{coutquery(1,l,r).cntendl;}}return0;}【运行结果】6 6 1 1 2 2 2 1 2 1 6 3 2 2 5 2 1 3 5 1 2 1 6 1 1 2 4 3 2 1 6 3