随机生成数据之类的题

“小鸡有一个由 𝑛 个值域为 [1,𝑚] 的正整数构成的数组 {𝑎1,𝑎2,…,𝑎𝑛}，每个元素都是在值域中独立均匀随机生成的。”题目中带有类似的看似无用的东西，就在告诉这道题所有的组合情况并不会真正的到达n^2，而是nlogn种，具体怎么证明，可以看寒假训练营6 E题解 很神奇。

代码也有很多细节，ST表+二分

#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using db = double;
const int N=1e5+10;
int a[N],n,m,q;
int dp_min[N][50],dp_max[N][50];
void init(){
    for(int i=1;i<=n;i++){
        dp_min[i][0]=a[i];
        dp_max[i][0]=a[i];
    }
    int p=log2(n);
    for(int k=1;k<=p;k++){
        for(int s=1;s+(1<<k)<=n+1;s++){
            dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
            dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
        }
    }
}
pii query(int L,int R){
    int k=log2(R-L+1);
    int mn=min(dp_min[L][k],dp_min[R-(1<<k)+1][k]);
    int mx=max(dp_max[L][k],dp_max[R-(1<<k)+1][k]);
    return {mx,mn};
}
signed main(){
    std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    init();
    map<ll,int> mp;
    for(int i=1;i<=n;i++){
        int j=i;
        while(j<=n){
            pii now=query(i, j);
            int l=j,r=n;
            ll ans=j;
            while(l<=r){
                ll mid=(l+r)>>1;
                if(query(i, mid)==now){
                    l=mid+1;
                    ans=mid;
                }else{
                    r=mid-1;
                }
            }
            mp[now.first*now.second]+=ans-j+1;
            j=ans+1;
        }
    }
    ll sum=0;
    map<ll,ll> pre;
    for(auto [x,y]:mp){
        // cout<<x<<" "<<y<<endl;
        sum+=y;
        pre[x]=sum;
    }
    while(q--){
        ll k;
        cin>>k;
        auto pos=mp.lower_bound(k);
        if(pos==mp.begin()){
            cout<<sum<<endl;
            continue;
        }
        pos--;
        auto [x,y]=*pos;
        cout<<sum-pre[x]<<endl;
    }
    return 0;
}