小红的区间修改二时间限制1 秒空间限制1024 MB网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述本题与《小红的区间修改一》共享部分题目背景但是所求内容不同我们建议您重新阅读题面。小红拿到了一个长度为10 100 10^{100}10100的数组初始所有元素都是0 00。现在小红准备进行q qq次操作每一次小红输入一个区间[ l , r ] [l, r][l,r]随后将区间内的元素修改为x xx小红希望你在每次操作后都输出当前数组的元素种类数即统计数组中不同元素的个数。输入描述第一行输入一个整数q ( 1 ≤ q ≤ 10 5 ) q\ (1 \le q \le 10^5)q(1≤q≤105)代表操作次数。此后q qq行第i ii行输入三个整数l i , r i , x i ( 1 ≤ l i ≤ r i ≤ 10 5 ; 1 ≤ x i ≤ 10 9 ) l_i, r_i, x_i\ (1 \le l_i \le r_i \le 10^5;\ 1 \le x_i \le 10^9)li,ri,xi(1≤li≤ri≤105;1≤xi≤109)代表第i ii次操作的区间和修改值。输出描述对于每一次操作新起一行输出一个整数代表当前数组的元素种类数。示例 1输入3 1 3 1 2 5 2 5 9 3输出2 3 4说明在这个样例中数组变化如下第一次操作后数组变成{ 1 , 1 , 1 , 0 , 0 , 0 , … } \{1,1,1,0,0,0,\dots\}{1,1,1,0,0,0,…}第二次操作后数组变成{ 1 , 2 , 2 , 2 , 2 , 0 , … } \{1,2,2,2,2,0,\dots\}{1,2,2,2,2,0,…}第三次操作后数组变成{ 1 , 2 , 2 , 2 , 3 , 3 , 3 , 3 , 3 , 0 , 0 , … } \{1,2,2,2,3,3,3,3,3,0,0,\dots\}{1,2,2,2,3,3,3,3,3,0,0,…}。解题思路本题是区间覆盖推平与元素种类数统计的经典题型。数组初始全为0长度极大10 100 10^{100}10100但所有操作区间的端点均在[ 1 , 10 5 ] [1, 10^5][1,105]内。每次操作将区间[ l , r ] [l, r][l,r]全部修改为x xx并输出当前数组中不同元素的个数。由于数组长度巨大但操作范围有限实际有效的数值段只有[ 1 , 10 5 ] [1, 10^5][1,105]以及其外恒为0的部分。我们可以使用有序映射维护连续区间并配合每种值的覆盖长度计数在线性对数时间内完成每次修改和查询。1. 问题等价转化初始状态整个数组都是0因此元素种类数为1 11。每次操作将区间[ l , r ] [l, r][l,r]覆盖为x xx这相当于将若干连续相同的区间合并或替换。元素种类数统计当前数组中有多少个不同的值。由于我们维护的是区间集合每个区间内的值相同所以只需记录每种值覆盖的总长度大于0 00即存在。由于操作端点l , r ≤ 10 5 l, r \le 10^5l,r≤105超出部分恒为0可以用一个虚拟的无限长区间[1, ∞)初始值为0在实现时通常用[1, 10^51)或更长的范围来代表。代码中MAXI 100000初始cnt[0] MAXI 1表示0覆盖了从1到MAXI1的长度实际代表[1, 10^51)这一段全为0。2. 算法实现珂朵莉树 长度计数代码采用类似珂朵莉树Chtholly Tree的结构mp一个mapll, ll键为区间左端点值为该区间的值。例如mp[1]0表示从1开始直到下一个键之前的区间值均为0。cnt一个mapll, ll键为数值值为该数值在当前所有区间中覆盖的总长度。核心操作Split(x)将区间按位置x切开返回指向左端点为x的区间的迭代器。如果x已经是某个区间的左端点直接返回否则将前一个区间在x处分裂成两个区间。Modify(l, r, x)将r加1转为左闭右开区间[ l , r 1 ) [l, r1)[l,r1)。分别Split(r1)和Split(l)得到待覆盖区间的边界迭代器。遍历并删除中间的所有区间同时在cnt中减去对应值的覆盖长度。插入新区间[l, r1)值为x并在cnt[x]中加上长度r - l 1。统计答案每次操作后cnt.size()即为当前数组中不同元素的个数因为cnt中只保存覆盖长度大于0的值。3. 复杂度分析时间复杂度每次操作需要两次Split一次区间删除和一次插入。均摊时间复杂度接近O ( log q 被删除的区间数 ) O(\log q \text{被删除的区间数})O(logq被删除的区间数)。由于每次操作会将区间推平总的区间数量不会无限制增长在均摊意义下复杂度为O ( q log q ) O(q \log q)O(qlogq)对于q ≤ 10 5 q \le 10^5q≤105非常高效。空间复杂度最多保存O ( q ) O(q)O(q)个区间以及O ( q ) O(q)O(q)种不同的值空间复杂度O ( q ) O(q)O(q)。总结利用有序映射维护连续同值区间同时用另一个映射维护每种值的总覆盖长度即可在区间覆盖修改后快速得到元素种类数。该方法被称为珂朵莉树适合处理“区间推平”操作较多的场景代码简洁且效率优秀。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;constll MAXI100000;ll q;mapll,llmp{{1,0}};mapll,llcnt{{0,MAXI1}};voidAdd(ll x,ll v){cnt[x]v;}voidRemove(ll x,ll v){autoitcnt.find(x);if(!(it-second-v)){cnt.erase(it);}}autoSplit(ll x){autoitmp.lower_bound(x);if(it-firstx)returnit;returnmp.emplace_hint(it,x,prev(it)-second);}voidModify(ll l,ll r,ll x){r;autoitrSplit(r);autoitlSplit(l);for(autoititl;it!itr;itmp.erase(it)){Remove(it-second,next(it)-first-it-first);}mp.emplace_hint(itr,l,x);Add(x,r-l);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinq;while(q--){ll l,r,x;cinlrx;Modify(l,r,x);coutcnt.size()endl;}return0;}
