有一种题型,是对于一个下标的值作为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所述的不为排列的情况.
京公网安备 11010502036488号