拆迁入门【牛客tracker 每日一题】

拆迁入门时间限制2秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述众所周知猫猫会推倒一切看起来不应该被推倒的东西而猫娘不一样猫娘会用一些奇怪的方式推倒它来提高你的血压。本题与《C.加法入门》共享部分题目背景这一部分我们使用特殊的格式标注。〖引用开始〗A s k a l a n a AskalanaAskalana搭建了一个n nn层的麻将塔。从上往下数第i ii层由i ii块麻将组成。每一块麻将上面都刻了一个整数记第i ii层从左往右数第j jj块麻将上的数字为a i , j a_{i,j}ai,j​。如下所示在本题中每一块麻将上的整数都各不相同且为1 11到n × ( n 1 ) 2 \frac{n×(n1)}{2}2n×(n1)​中的一个。A s k a l a n a AskalanaAskalana按整数从小到大的顺序自上而下、自左而右的搭出了一座麻将塔。如下所示〖引用结束〗除最下层外每块麻将的左、右两角分别由两块麻将支撑。这一回还没等A s k a l a n a AskalanaAskalana回房间休息猫猫小姐就快速的向k kk块麻将出爪将它们推倒了。而如果一块麻将左下、右下的两块支撑麻将都被推倒了那么这块麻将也会被推倒这就是连锁反应。A s k a l a n a AskalanaAskalana想知道如果猫猫推倒了a 1 , a 2 , … , a k a_1,a_2,…,a_ka1​,a2​,…,ak​​ 这k kk块麻将连锁反应会导致最终有多少块麻将被推倒输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 100 ) T(1≦T≦100)T(1≦T≦100)代表数据组数每组测试数据描述如下第一行输入两个正整数n , k ( 1 ≦ n ≦ 10 9 ; 1 ≦ k ≦ 3 × 10 5 ) n,k(1≦n≦10^9; 1≦k≦3×10^5)n,k(1≦n≦109;1≦k≦3×105)*代表麻将塔的层数、猫猫推倒的麻将数量。第二行输入k kk个不同的正整数a 1 , a 2 , … , a k ( 1 ≦ a i ≦ n × ( n 1 ) 2 ) a_1,a_2,…,a_k(1≦a_i≦\frac{n×(n1)}{2})a1​,a2​,…,ak​(1≦ai​≦2n×(n1)​)代表被猫猫推倒的麻将的编号。除此之外保证单个测试文件的k kk之和不超过3 × 10 5 3×10^53×105。输出描述对于每一组测试数据新起一行。输出一个整数代表连锁反应最终会导致多少块麻将被推倒。示例1输入3 5 6 11 12 14 15 8 9 3 3 4 5 6 1 1 1输出14 6 1解题思路本题核心是数学建模倒序处理区间合并解决超大层级麻将塔的连锁推倒问题。由于麻将塔层数n ≤ 10 9 n≤10^9n≤109无法模拟利用连锁规则上层麻将倒塌等价于下层两个支撑点均被覆盖将问题转化为层级区间覆盖统计。首先通过二分查找将数字映射到对应层级从下往上倒序处理被推倒的麻将用哈希表和有序集合维护连续的有效覆盖区间自动合并相邻区间减少冗余。通过数学公式快速统计区间内的倒塌数量最终累加所有有效数量得到答案。算法时间复杂度O ( k log ⁡ k ) O(k\log k)O(klogk)完美适配k ≤ 3 × 10 5 k≤3×10^5k≤3×105的数据规模。总结核心逻辑将连锁倒塌规则转化为层级区间覆盖问题规避超大n nn的暴力模拟。关键操作数字到层级的二分映射、倒序处理、区间合并维护、数学公式统计总数。效率保障仅处理输入的k kk个点时间复杂度低完美适配题目大数据约束。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;ll k;vectorllv;mapll,llmp;setpairll,llst;ll cl;ll sl;ll ans;llf(ll x){returnx*(x-1)/21;}llL(ll x){ll l1;ll rn;while(lr){ll mid(lr1)1;if(xf(mid)){rmid-1;continue;}lmid;}returnl;}voidins(ll x,ll level){ll lff(level);ll valx-lf;autoitmp.upper_bound(val);if(itmp.begin()){itmp.emplace_hint(mp.begin(),val,val1(n-level));st.emplace(1(n-level),val);sl;}else{autolitprev(it);auto[llf,lrt]*lit;ll rtlrt-(n-level);if(rtval){return;}sl;if(rtval){st.erase({lrt-llf,llf});lrt;st.insert({lrt-llf,llf});itlit;}else{itmp.emplace_hint(it,val,val1(n-level));st.emplace(1(n-level),val);}}autoritnext(it);if(rit!mp.end()){auto[rlf,rrt]*rit;if(val1rlf){st.erase({rrt-rlf,rlf});st.erase({it-second-it-first,it-first});it-secondrrt;st.insert({rrt-it-first,it-first});mp.erase(rit);}}}voiddec(ll level){while(st.size()){auto[len,lf]*st.begin();if(lenn-level){break;}ll lastLenlen-(n-cl);ans(ll)lastLen*(lastLen1)/2;sl-lastLen;mp.erase(lf);st.erase(st.begin());}ll diffcl-level;ll szmp.size();sl-sz*diff;anssl*diff;anssz*((ll)diff*(diff1)/2);cllevel;}voidsol(){cinnk;v.resize(k);for(ll i0;ik;i){cinv[i];}sort(v.begin(),v.end(),greater());cln;sl0;ans0;for(autox:v){ll levelL(x);if(levelcl){dec(level);}ins(x,level);}dec(0);coutansendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cinT;while(T--){sol();}}