单调栈+按位置建树，数据结构就是解决问题时用的容器

单调栈 + 按位置建树

先求出每个点作为最大值的区间范围（用单调栈优化）
经过证明单调栈放下标更好，以后一般都用下标
单调栈：扔一次删一次，所以复杂度为O(n)
数据结构就是解决问题时用的容器
并查集也是容器

按位置建树
求某个点左边（或右边）有多少个可选的点
可以用ask求

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define low(x) x&(-x) 
int const N=1e5+7;
int INF=0x3f3f3f3f;
int n;
struct L{
    int a,l,r;
}b[N];
stack<int>s;
void pan(){
    b[0].a=INF;
    s.push(0);
    s.push(1);
    b[1].l=1;
    for(int i=2;i<=n;++i){
        while( b[i].a >= b[ s.top() ].a&&!s.empty() ) s.pop();
        b[i].l=s.top()+1;
        s.push(i);
    }
    if(!s.empty()) s.pop();
    b[n+1].a=INF;
    s.push(n+1);
    s.push(n);
    b[n].r=n;
    for(int i=n-1;i>=1;--i){
        while( b[i].a >= b[ s.top() ].a&&!s.empty() ) s.pop();
        b[i].r=s.top()-1;
        s.push(i);
    }
}
int m;
ll c[N],p[N];
void add(int i,int w){   //位置和值要分清楚 
    for(;i<=n;i+=low(i)){
        c[i]+=w;
    }
}
ll ask(int x){
    ll res=0;
    for(;x;x-=low(x)){
        res+=c[x];
    }
    return res;
}
map<ll,ll>mp; //
ll calc(int x){ //计算 MRQ(l,r)=x 的方案数 
    ll ls= ask(x)-ask(b[x].l-1) ; //ls表示以x号点为区间最大值 左边(包括x)可选的点数
    ll rs=ask(b[x].r)-ask(x-1) ;
    ll res=ls*rs*2;
    if(ask(x)-ask(x-1)==1) res--;   //如果j这个地方有点则-1
    return res;
}
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
int main(){
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> b[i].a;
    }
    pan();
    cin >> m;
    int k;
    while(m--){
        cin >> k;
        for(int i=1;i<=k;++i){
            cin >> p[i];
            add(p[i],1);
        }    
        ll sum=(ll)k*k;    //
        for(int i=1;i<=k;++i){
            mp[b[p[i]].a]=calc(p[i]);   // mp[j]表示以z值为区间最大值的方案数 
            /*还有一种情况：
            样例：3 
                  1 5 2
                  1
                  2 1 3
            此时的2号点不在可选范围，但 RMQ(1,3)=5
            以下就是去掉此种情况的代码 
            */ 
            int l=b[p[i]].l -1;    //左边界的左边l一定比b[p[i]].a大，所以其有可能成为区间最大值
            while(l>=1&&mp.find(b[l].a)==mp.end()){
                mp[b[l].a]=calc(l);
                l=b[l].l -1;
            }
            int r=b[p[i]].r +1;
            while(r<=n&&mp.find(b[r].a)==mp.end()){
                mp[b[r].a]=calc(r);
                r=b[r].r +1;
            }
        }
        for(map<ll,ll>::iterator it=mp.begin();it!=mp.end();it++){
            if((*it).second!=0) {
                ll z=gcd(sum,it->second);
                cout << (*it).first << " " << (*it).second/z << "/" << sum/z << "\n";
            }
        }
        mp.clear();
        for(int i=1;i<=k;++i){
            add(p[i],-1);
        }
    }
    return 0;
}