拆迁入门【牛客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×(n+1)}{2}2n×(n+1)中的一个。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×(n+1)}{2})a1,a2,…,ak(1≦ai≦2n×(n+1))代表被猫猫推倒的麻将的编号。
除此之外，保证单个测试文件的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个点，时间复杂度低，完美适配题目大数据约束。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n;ll k;vector<ll>v;map<ll,ll>mp;set<pair<ll,ll>>st;ll cl;ll sl;ll ans;llf(ll x){returnx*(x-1)/2+1;}llL(ll x){ll l=1;ll r=n;while(l<r){ll mid=(l+r+1)>>1;if(x<f(mid)){r=mid-1;continue;}l=mid;}returnl;}voidins(ll x,ll level){ll lf=f(level);ll val=x-lf;autoit=mp.upper_bound(val);if(it==mp.begin()){it=mp.emplace_hint(mp.begin(),val,val+1+(n-level));st.emplace(1+(n-level),val);sl++;}else{autolit=prev(it);auto&[llf,lrt]=*lit;ll rt=lrt-(n-level);if(rt>val){return;}sl++;if(rt==val){st.erase({lrt-llf,llf});lrt++;st.insert({lrt-llf,llf});it=lit;}else{it=mp.emplace_hint(it,val,val+1+(n-level));st.emplace(1+(n-level),val);}}autorit=next(it);if(rit!=mp.end()){auto&[rlf,rrt]=*rit;if(val+1==rlf){st.erase({rrt-rlf,rlf});st.erase({it->second-it->first,it->first});it->second=rrt;st.insert({rrt-it->first,it->first});mp.erase(rit);}}}voiddec(ll level){while(st.size()){auto[len,lf]=*st.begin();if(len>n-level){break;}ll lastLen=len-(n-cl);ans+=(ll)lastLen*(lastLen+1)/2;sl-=lastLen;mp.erase(lf);st.erase(st.begin());}ll diff=cl-level;ll sz=mp.size();sl-=sz*diff;ans+=sl*diff;ans+=sz*((ll)diff*(diff+1)/2);cl=level;}voidsol(){cin>>n>>k;v.resize(k);for(ll i=0;i<k;i++){cin>>v[i];}sort(v.begin(),v.end(),greater<>());cl=n;sl=0;ans=0;for(autox:v){ll level=L(x);if(level<cl){dec(level);}ins(x,level);}dec(0);cout<<ans<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cin>>T;while(T--){sol();}}