有一种题型,是对于一个下标的值作为max/min时,对雨某种满足题目要求性质的子段的计数,而我们知道,值满足堆的性质,下标满足二叉线索树的性质,就是笛卡尔树,处理一个区间,我们只要遍历左右里面长度小的区间,再通过预处理的东西算出结论(可能是预处理,可能是二分)

例1.Max to the Right of Min

链接

由题意我们产生了一种思路,钦定区间的最小值进行统计,如果原题不是排列,只要钦定a[idx]是区间的最小值并且左侧只能包括<a[i]的才行.

我们dfs遍历笛卡尔树,遍历左右侧长度更小的区间就行,并使用pre和suf来记录对于一个下标而言,左侧第一个比自己大的值和右侧第一个比自己大的值就行了.这样处理的话每个下标最多访问log(n)次,因为每次访问完一个小标,他所在的区间的长度肯定会翻倍,所以1个点最多访问log(n)次,总复杂度nlog(n)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db  double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e6+10;
const int base=499;
int dcmp(double x){
   if(fabs(x)<eps){
      return 0;
   }
   return x<0?-1:1;
}
void debug(){
   cout<<"Test:Wrong"<<'\n';
   exit(0);
}
//离散化情况下可以当set使用的BIT
int a[N];
struct BIT{
   vector<int>tr;
   vector<int>cnt;
   int n;
   void init(int len){
      n=len;
      tr.assign(n+5,0);
      cnt.assign(n+5,0);
   }
   int lowbit(int x){
     return x&(-x);
   }
   void update(int x,int d){
       while(x<=n){
          tr[x]+=d;
          cnt[x]+=(d>=1?1:-1);
          x+=lowbit(x);
       }
   }
   int kth(int idx){
       //寻找能>=k*a[i]的最小的 k
       //至少得是几
       int k=0;
       //return k+1;
       int sum=0;
       int ans=0;
       for(int i=18;i>=0;i--){
           int nxt=k+(1<<i);
           if(nxt<=n&&idx-1-tr[nxt]-sum<nxt*a[idx]){
               sum+=tr[nxt];
               k=nxt; 
           }else if(nxt<=n&&idx-1-tr[nxt]-sum>=nxt*a[idx]){
               ans=nxt;
           }
       }
       return ans;
   }
   int querycnt(int x){
     int ans=0;
     while(x>=1){
       ans+=cnt[x];  
       x-=lowbit(x);
     } 
     return ans;
   }
   int query(int x){
       int ans=0;
       while(x>=1){
          ans+=tr[x];  
          x-=lowbit(x);
       } 
       return ans;
   }
}bit;

int up[N];
void solve(){
   int n,q;
   cin>>n>>q;
   bit.init(n);
   for(int i=1;i<=n;i++){
        cin>>a[i];
        //return;
        up[i]=bit.kth(i);
        cout<<up[i]<<'\n';
        if(up[i]!=0)bit.update(up[i],1);
   } 
   //return;
   while(q--){
       int i,x;
       cin>>i>>x;
       if(x<up[i])cout<<"YES"<<'\n';
       else cout<<"NO"<<'\n';
   }
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T=1;
  //cin>>T;
  while(T--)solve();
  return 0;
}

例2.氟化钙(2026hdu春季联赛第一场)

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define int long long
#define i128 __int128
#define pii pair<int,int>
#define tp tuple<int,int,int>
#define db  double
const db INF=1e18;
const db pi=acos(-1);
const int mod=1e9+7;
const int inv2=500000004;
const db eps=1e-6;
const int inf=1e18;
const int N=1e5+10;
const int base=499;
int dcmp(double x){
   if(fabs(x)<eps){
      return 0;
   }
   return x<0?-1:1;
}
void debug(){
   cout<<"Test:Wrong"<<'\n';
   exit(0);
}
int a[N];
int b[N];
int stk[N];
vector<int>g[N];
int ls[N];
int rs[N];
int range[N][2];
map<int,int>mp;
int ans;
int fl(int num,int L,int R){
    //第一个>=L的位置
    int l=0,r=g[num].size()-1,idx=-1;
    while(l<=r){
         int mid=(l+r)>>1;
         if(g[num][mid]>=L){
             idx=mid;
             r=mid-1;
         }else{
             l=mid+1;
         }
    }
    return idx;
}
int fr(int num,int L,int R){
    //最后一个<=R的位置
    int l=0,r=g[num].size()-1,idx=-1;
    while(l<=r){
         int mid=(l+r)>>1;
         if(g[num][mid]<=R){
             idx=mid;
             l=mid+1;
         }else{
             r=mid-1;
         }
    }
    return idx;
}
void dfs(int x){
    range[x][0]=x;
    range[x][1]=x;
    if(ls[x]){
         dfs(ls[x]);
    }
    if(rs[x]){
         dfs(rs[x]);
    }
    if(ls[x]&&rs[x]){
       int lenl=range[ls[x]][1]-range[ls[x]][0]+1,lenr=range[rs[x]][1]-range[rs[x]][0]+1;
       int L,R;
       int l,r;
       if(lenl<=lenr){
            l=x-lenl,r=x-1;
            L=x+1,R=x+lenr;
       }else{ 
            l=x+1,r=x+lenr;
            L=x-lenl,R=x-1;
       }
       //return;
       int k=a[x];
       for(int j=l;j<=r;j++){
            if(k%2==1){
                 int now=k+1-a[j];
                 now=mp[now];
                 if(now==0)continue;  
                 int findl=fl(now,L,R);
                 int findr=fr(now,L,R);
                 if(findr>=findl&&findr!=-1&&findl!=-1){
                     ans+=findr-findl+1;
                 }
            }    
       }
       range[x][0]=range[ls[x]][0];
       range[x][1]=range[rs[x]][1];
    }else if(ls[x]){
       range[x][0]=range[ls[x]][0];
    }else if(rs[x]){
       range[x][1]=range[rs[x]][1];
    }
}
void solve(){
     //先离散化
     int n;
     cin>>n;
     int tot=0;
     ans=0;
     mp.clear();
     for(int i=1;i<=n;i++){
          ls[i]=0;
          rs[i]=0;
          range[i][0]=0;
          range[i][1]=0;
          cin>>a[i];
          if(!mp[a[i]])mp[a[i]]=++tot;
          b[i]=mp[a[i]];
          g[b[i]].push_back(i);
     }
     int top=0;
     for(int i=1;i<=n;i++){
          int k=top;
          while(top>0&&a[stk[top]]<a[i]){
              top--;
          }
          if(top)rs[stk[top]]=i;
          if(top<k)ls[i]=stk[top+1];
          stk[++top]=i;
     }
     dfs(stk[1]);
     cout<<n*n-ans*2<<'\n';
     for(int i=1;i<=tot;i++){
           g[i].clear();
     }
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int T=1;
  cin>>T;
  while(T--)solve();
  return 0;
}

这就是例1所述的不为排列的情况.