【学习笔记】用线段树维护区间计数问题

前言

简单的区间计数问题可能直接推式子就行了。
但有些问题必须要数据结构维护。线段树就是一个比较好的处理区间的数据结构。

Gym102222L

思路

满足条件的区间特征： max ⁡ { a i } − min ⁡ { a i } + 1 − c n t = 0 \max\{a_i\}-\min\{a_i\}+1-cnt=0 max{ai​}−min{ai​}+1−cnt=0，其中 $cnt$ 代表区间内不同数字的个数。
考虑固定右端点，统计有多少个合法的左端点。
我们可以用线段树维护 m i n v = min ⁡ { max ⁡ { a i } − min ⁡ { a i } − c n t } minv=\min\{\max\{a_i\}-\min\{a_i\}-cnt\} minv=min{max{ai​}−min{ai​}−cnt} 和 $num=有多少个区间左端点可以取到minv$，答案就是 $minv=-1$ 时的 $num$
max ⁡ { a i } \max\{a_i\} max{ai​} 和 min ⁡ { a i } \min\{a_i\} min{ai​} 可以用两个单调栈维护。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct seg
{int minv,tag,cnt;seg(){minv=tag=cnt=0;}
};
vector<seg> tr;
void update(int u)
{tr[u].minv=min(tr[u<<1].minv,tr[u<<1|1].minv);if(tr[u<<1].minv==tr[u<<1|1].minv){tr[u].cnt=tr[u<<1].cnt+tr[u<<1|1].cnt;}else if(tr[u].minv==tr[u<<1].minv){tr[u].cnt=tr[u<<1].cnt;}else if(tr[u].minv==tr[u<<1|1].minv){tr[u].cnt=tr[u<<1|1].cnt;}else{assert(false);}
}
void pushdown(int u)
{if(tr[u].tag){tr[u<<1].minv+=tr[u].tag; tr[u<<1|1].minv+=tr[u].tag;tr[u<<1].tag+=tr[u].tag; tr[u<<1|1].tag+=tr[u].tag;tr[u].tag=0;}
}
void build(int u,int st,int ed)
{if(st==ed){tr[u].cnt=1;return;}int mid=st+ed>>1;build(u<<1,st,mid);build(u<<1|1,mid+1,ed);update(u);
}
void modify(int u,int st,int ed,int l,int r,int x)
{if(l<=st&&ed<=r){tr[u].minv+=x;tr[u].tag+=x;return;}pushdown(u);int mid=st+ed>>1;if(mid>=l)modify(u<<1,st,mid,l,r,x);if(mid<r)modify(u<<1|1,mid+1,ed,l,r,x);update(u);
}
int query(int u,int st,int ed,int l,int r)
{if(l<=st&&ed<=r){return tr[u].minv==-1?tr[u].cnt:0;}pushdown(u);int mid=st+ed>>1;int res=0;if(mid>=l)res=query(u<<1,st,mid,l,r);if(mid<r)res+=query(u<<1|1,mid+1,ed,l,r);return res;
}
int O_o()
{int n;cin>>n;tr.assign(n+1<<2,seg());vector<int> a(n+1),ls(n+1);map<int,int> mp;for(int i=1; i<=n; i++){cin>>a[i];ls[i]=mp[a[i]];mp[a[i]]=i;}build(1,1,n);stack<array<int,2>> sx,sy;// decrease, increaseint ans=0;for(int i=1; i<=n; i++){int x=a[i];while(sx.size()&&x>sx.top()[0]){auto [v,id]=sx.top(); sx.pop();modify(1,1,n,sx.size()?(sx.top()[1]+1):1,id,x-v);}sx.push({x,i});while(sy.size()&&x<sy.top()[0]){auto [v,id]=sy.top(); sy.pop();modify(1,1,n,sy.size()?(sy.top()[1]+1):1,id,v-x);}sy.push({x,i});modify(1,1,n,ls[i]+1,i,-1);ans+=query(1,1,n,1,i);}return ans;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;for(int i=1; i<=T; i++){cout<<"Case #"<<i<<": "<<O_o()<<"\n";}
}

2024牛客暑期多校训练营7 D

思路

首先预处理每个点要往后走到哪才会出现 $k$ 次和 $k+1$ 次
具体的，令 $L_i$ 为从点 $i$ 往后走，出现 $k$ 次 $a_i$ 的最近位置；令 $R_i$ 为从点 $i$ 往后走，出现 $k$ 次 $a_i$ 的最远位置。
考虑倒着枚举左端点，对于每个左端点考虑有多少个右端点是合法的。

我们定义点 $i$ 的合法区间为 $[L_i,R_i]\cup [1,i-1]$ （$[L_i,R_i]$ 中 $a_i$ 出现了 $k$ 次，$[1,i-1]$ 不在 $i$ 的管辖范围内），那么对于 $i$ 为左端点的答案就是 $[i,n]$ 中所有不同的数最前面的合法区间的交集。

也就是我们要维护一棵线段树，支持区间加、区间减、求区间最大值和最大值个数。这样做其实有些麻烦。
不难想到，合法区间的交集 = 不合法区间的并集的反集，求区间的并就完全可以像扫描线那样做。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct seg
{int val,len;seg(){val=len=0;}
};
vector<seg> tr;
int n;
void update(int u,int st,int ed)
{if(tr[u].val>0){tr[u].len=ed-st+1;}else{if(st==ed){tr[u].len=0;return;}tr[u].len=tr[u<<1].len+tr[u<<1|1].len;}
}
void add(int u,int st,int ed,int l,int r,int x)
{if(l>r||l>n||r>n) return;if(l<=st&&ed<=r){tr[u].val+=x;update(u,st,ed);return;}
//	pushdown(u);int mid=st+ed>>1;if(mid>=l)add(u<<1,st,mid,l,r,x);if(mid<r)add(u<<1|1,mid+1,ed,l,r,x);update(u,st,ed);
}
int query(int u,int st,int ed,int l,int r)
{if(l>r||l>n||r>n) return 0;if(l<=st&&ed<=r){return tr[u].len;}int mid=st+ed>>1;int res=0;if(mid>=l)res=query(u<<1,st,mid,l,r);if(mid<r)res+=query(u<<1|1,mid+1,ed,l,r);return res;
}
void O_o()
{int k;cin>>n>>k;map<int,vector<int>> mp;vector<int> a(n+1);for(int i=1; i<=n; i++){cin>>a[i];mp[a[i]].push_back(i);}tr.assign((n<<2)+1,seg());vector<array<int,2>> pos(n+1);vector<int> p,nxt(n+1);p.push_back(-1);for(auto [v,t]:mp){p.push_back(v);int m=t.size();for(int i=0; i<m; i++){int l,r;if(i+k-1>=m){l=n+1;}else l=t[i+k-1];if(i+k>=m){r=n+1;}else r=t[i+k];pos[t[i]]={l,r};if(i==m-1)nxt[t[i]]=n+1;else nxt[t[i]]=t[i+1];}}int ans=0;for(int i=n; i>=1; i--){if(nxt[i]!=n+1){auto [l,r]=pos[nxt[i]];add(1,1,n,nxt[i],l-1,-1);add(1,1,n,r,n,-1);}auto [l,r]=pos[i];add(1,1,n,i,l-1,1);add(1,1,n,r,n,1);int t=query(1,1,n,i,n);ans+=(n-i+1)-t;}cout<<ans<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;while(T--){O_o();}
}