题解：AT_donuts_2015_3 行列のできるドーナツ屋

zhangmuning1016 · 2025-06-17 14:15:46 · 题解

题意

有 N 个人在排队，每个人都有身高，要求出第 i 个人向前能看到多少个人（要满足依次越来越高）。

方法 1 思路

此题是 单调栈 模板题。用单调栈维护一个身高一次递减的序列，第 i 个答案为当前栈的长度。

代码

#include <bits/stdc++.h>
using namespace std;
stack <int> q;
int a[100001], n;
int main () {
    ios :: sync_with_stdio (0);
    cin.tie (0);
  cout.tie (0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cout << q.size () << endl;
        while (q.size () && q.top () < a[i]) q.pop ();
        q.push (a[i]);
    }
    return 0;
}

方法 2 思路

再讲一种思路，线段数。

1. 构建
   • 线段树的每个节点表示一个区间，根节点表示整个区间 [0, N-1]。每个内部节点将区间分为左右两部分，分别由左右子节点表示，直到叶子节点表示单个元素。
   • 每个节点存储区间最大值。叶子节点存储元素值，内部节点的值由其子节点的值合并得到。
2. 查询
   • 当查询某个区间 [l, r] 的信息时，从根节点开始查找。若节点的区间在查询区间内，则返回该节点值。
   • 若当前节点的区间部分包含查询区间，将查询分解为对左右子节点的查询。
3. 更新
   • 更新某个元素的值时，得向上更新路径上所有节点的值，使节点维护的始终正确。

     代码

     
     #include<bits/stdc++.h>
     using namespace std;
     struct Node {
     vector<int>g;
     int n;
     Node(const vector<int>&arr) {
     n=arr.size();
     g.resize(4*n);
     build(1,0,n-1,arr);
     }
     void build(int xx,int start,int end,const vector<int>&arr) {
     if(start==end) {
         g[xx]=arr[start];
         return;
     }
     int mid=(start+end)/2;
     build(2*xx,start,mid,arr);
     build(2*xx+1,mid+1,end,arr);
     g[xx]=max(g[2*xx],g[2*xx+1]);
     }
     int query(int l,int r) {
     return query(1,0,n-1,l,r);
     }
     int query(int xx,int start,int end,int l,int r) {
     if(r<start||l>end) {
         return 0;
     }
     if(l<=start&&end<=r) {
         return g[xx];
     }
     int mid=(start+end)/2;
     int ll=query(2*xx,start,mid,l,r);
     int rr=query(2*xx+1,mid+1,end,l,r);
     return max(ll,rr);
     }
     };
     int main() {
     ios::sync_with_stdio(0);
     cin.tie(0);
     cout.tie(0);
     int n;
     cin>>n;
     vector<int>A(n);
     for(int i=0; i<n; i++) {
     cin>>A[i];
     }
     Node segTree(A);
     stack<int>st;
     vector<int>res(n,0);
     for(int i=0; i<n; i++) {
     while(!st.empty()) {
         int j=st.top();
         int maxx=segTree.query(j+1,i-1);
         if(maxx>A[j]) {
             st.pop();
         } else {
             break;
         }
     }
     res[i]=st.size();
     st.push(i);
     }
     for(int i=0; i<n; i++) {
     cout<<res[i]<<endl;
     }
     cout<<endl;
     return 0;
     }