P8251 题解

Jerrlee✅

2022-04-01 10:50:31

Solution

谨以此题解,纪念我第一次 NOIO TG 前 $25\%$。 ## 题意 每次向栈中加入一个二元组 $(a_i,b_i)$,先不断弹出栈顶元素直至栈空或栈顶元素 $(a_j,b_j)$ 直到其满足 $a_i \neq a_j$ 且 $b_i<b_j$,然后入栈。如果一个二元组入栈后栈内只有这一个元素,则称该二元组是“成功的”。 在 $[l,r]$ 的区间中每对元素依次做如上操作,求有多少个“成功的”二元组。 ## 思路 看到这题,可以尝试打个 $15$ 分的暴力,在此直接给出代码: ```cpp #include<iostream> #include<cstdio> #include<stack> using namespace std; #define int long long pair<int,int> a[500010]; #define fi first #define se second signed main(){ //freopen("stack.in","r",stdin); //freopen("stack.out","w",stdout); int n,q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i].fi; for(int i=1;i<=n;i++) cin>>a[i].se; while(q--){ stack<int> s,s1; int x,y,ans=0; cin>>x>>y; for(int i=x;i<=y;i++){ int tmp=a[i].fi,temp=a[i].se; if(s.empty()){ s.push(tmp); s1.push(temp); ans++; } else{ be:; if(s.empty()){ s.push(tmp); s1.push(temp); ans++; continue; } int xx=s.top(),yy=s1.top(); if(xx!=tmp&&yy>temp){ s.push(tmp); s1.push(temp); if(s.size()==1) ans++; } else{ s.pop(); s1.pop(); goto be; } } } cout<<ans<<endl; } } ``` 接下来讲正解: 我使用的算法是归并树,其实就是归并排序和线段树的结合体,利用线段树记录归并排序的步骤。 它可以用于计算某区间中比某个数小或大的数有多少个,正好适用本题。建树时递归构造子节点,回溯时构造父节点。 学习归并树可以看此篇文章:<https://www.cnblogs.com/bennettz/p/8342242.html> 为什么本题可以转化成求解某区间比某数小的数的数量呢? 这样想:每个元素可以弹出他前面的若干元素,我们计他可以弹出至 $a[i]$ 号元素。如果求解一个区间 $[l,r]$,那么如果这个区间内的某个元素 $a[i]$ 可以弹出至 $l$ 以下,就肯定可以把栈弹空,所以本题就转化为求解区间 $<l$ 的数的数量了。 在程序最开始先模拟一下题目所说的操作,用栈记录下来,然后直接套模板求解某区间比某数小的数的数量即可。 最开始读入的数据可以用一个 `pair` 记录下来,注意细节,刚开始准备的 `stack` 先将一对 `0,0` 入栈以防出错。 本代码时间复杂度大概为 $O(n \ \log^2 \ n)$。 ## 代码 ```cpp /* / / / / / / / / / written by Jerrlee 算法使用:归并树 / / / / / / / / / */ #include<iostream> #include<cstdio> #include<stack> using namespace std; #define int long long #define fi first #define se second pair<int,int> a[500010]; int c[500010],f[50][500010]; void Build(int de,int l,int r){ if(l==r){ f[de][l]=c[l]; return; } int mid=(l+r)>>1; Build(de+1,l,mid); Build(de+1,mid+1,r); for(int i=l,j=mid+1,k=l;i<=mid||j<=r;){ if(j>r) f[de][k++]=f[de+1][i++]; else if(i>mid||f[de+1][i]>f[de+1][j]) f[de][k++]=f[de+1][j++]; else f[de][k++]=f[de+1][i++]; } }//建树 int calc(int de,int L,int R,int l,int r,int x){ if(L>=l&&R<=r) return lower_bound(f[de]+L,f[de]+R+1,x)-f[de]-L; int mid=(L+R)>>1,ans=0; if(mid>=l) ans+=calc(de+1,L,mid,l,r,x); if(mid<r) ans+=calc(de+1,mid+1,R,l,r,x); return ans; }//模板部分 signed main(){ //freopen("stack.in","r",stdin); //freopen("stack.out","w",stdout); int n,q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i].fi; for(int i=1;i<=n;i++) cin>>a[i].se; stack<pair<int,int> > s,s1; s.push({0,0}); s1.push({0,0}); for(int i=1;i<=n;i++){ be: c[i]=s.top().fi; if(s.size()>1&&!(s.top().se!=a[i].fi&&s1.top().se>a[i].se)){ s.pop(); s1.pop(); goto be; } s.push({i,a[i].fi}); s1.push({i,a[i].se}); }//模拟 Build(1,1,n); while(q--){ int x,y; cin>>x>>y; cout<<calc(1,1,n,x,y,x)<<endl;//求出 x-y 区间内数字小于 x 的数量 } } ``` 注:此代码在洛谷只有 $50$ 分,需要加快读(但是我测完 CCF 的官方数据是 $100$)。 快读版:<https://www.luogu.com.cn/paste/1c5p7sdz> [AC 记录](https://www.luogu.com.cn/record/72805036)