山西手机版建站系统开发,网站建设基础学习,上海网站建设-新闻动态,宁波seo网络推广产品服务前言
简单的区间计数问题可能直接推式子就行了。 但有些问题必须要数据结构维护。线段树就是一个比较好的处理区间的数据结构。
Gym102222L 思路
满足条件的区间特征#xff1a; max { a i } − min { a i } 1 − c n t 0 \max\{a_i\}-\min\{a_i\}1-cnt0 max{ai}…前言
简单的区间计数问题可能直接推式子就行了。 但有些问题必须要数据结构维护。线段树就是一个比较好的处理区间的数据结构。
Gym102222L 思路
满足条件的区间特征 max { a i } − min { a i } 1 − c n t 0 \max\{a_i\}-\min\{a_i\}1-cnt0 max{ai}−min{ai}1−cnt0其中 c n t cnt cnt 代表区间内不同数字的个数。 考虑固定右端点统计有多少个合法的左端点。 我们可以用线段树维护 m i n v min { max { a i } − min { a i } − c n t } minv\min\{\max\{a_i\}-\min\{a_i\}-cnt\} minvmin{max{ai}−min{ai}−cnt} 和 n u m 有多少个区间左端点可以取到 m i n v num有多少个区间左端点可以取到 minv num有多少个区间左端点可以取到minv答案就是 m i n v − 1 minv-1 minv−1 时的 n u m num num max { a i } \max\{a_i\} max{ai} 和 min { a i } \min\{a_i\} min{ai} 可以用两个单调栈维护。
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e67,inf1e18;
struct seg
{int minv,tag,cnt;seg(){minvtagcnt0;}
};
vectorseg tr;
void update(int u)
{tr[u].minvmin(tr[u1].minv,tr[u1|1].minv);if(tr[u1].minvtr[u1|1].minv){tr[u].cnttr[u1].cnttr[u1|1].cnt;}else if(tr[u].minvtr[u1].minv){tr[u].cnttr[u1].cnt;}else if(tr[u].minvtr[u1|1].minv){tr[u].cnttr[u1|1].cnt;}else{assert(false);}
}
void pushdown(int u)
{if(tr[u].tag){tr[u1].minvtr[u].tag; tr[u1|1].minvtr[u].tag;tr[u1].tagtr[u].tag; tr[u1|1].tagtr[u].tag;tr[u].tag0;}
}
void build(int u,int st,int ed)
{if(sted){tr[u].cnt1;return;}int midsted1;build(u1,st,mid);build(u1|1,mid1,ed);update(u);
}
void modify(int u,int st,int ed,int l,int r,int x)
{if(lstedr){tr[u].minvx;tr[u].tagx;return;}pushdown(u);int midsted1;if(midl)modify(u1,st,mid,l,r,x);if(midr)modify(u1|1,mid1,ed,l,r,x);update(u);
}
int query(int u,int st,int ed,int l,int r)
{if(lstedr){return tr[u].minv-1?tr[u].cnt:0;}pushdown(u);int midsted1;int res0;if(midl)resquery(u1,st,mid,l,r);if(midr)resquery(u1|1,mid1,ed,l,r);return res;
}
int O_o()
{int n;cinn;tr.assign(n12,seg());vectorint a(n1),ls(n1);mapint,int mp;for(int i1; in; i){cina[i];ls[i]mp[a[i]];mp[a[i]]i;}build(1,1,n);stackarrayint,2 sx,sy;// decrease, increaseint ans0;for(int i1; in; i){int xa[i];while(sx.size()xsx.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()xsy.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);ansquery(1,1,n,1,i);}return ans;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(12);int T1;cinT;for(int i1; iT; i){coutCase #i: O_o()\n;}
}2024牛客暑期多校训练营7 D 思路
首先预处理每个点要往后走到哪才会出现 k k k 次和 k 1 k1 k1 次 具体的令 L i L_i Li 为从点 i i i 往后走出现 k k k 次 a i a_i ai 的最近位置令 R i R_i Ri 为从点 i i i 往后走出现 k k k 次 a i a_i ai 的最远位置。 考虑倒着枚举左端点对于每个左端点考虑有多少个右端点是合法的。
我们定义点 i i i 的合法区间为 [ L i , R i ] ∪ [ 1 , i − 1 ] [L_i,R_i]∪[1,i-1] [Li,Ri]∪[1,i−1] [ L i , R i ] [L_i,R_i] [Li,Ri] 中 a i a_i ai 出现了 k k k 次 [ 1 , i − 1 ] [1,i-1] [1,i−1] 不在 i i i 的管辖范围内那么对于 i i i 为左端点的答案就是 [ i , n ] [i,n] [i,n] 中所有不同的数最前面的合法区间的交集。
也就是我们要维护一棵线段树支持区间加、区间减、求区间最大值和最大值个数。这样做其实有些麻烦。 不难想到合法区间的交集 不合法区间的并集的反集求区间的并就完全可以像扫描线那样做。
代码
#includebits/stdc.h
#define int long long
using namespace std;
const int N1e67,inf1e18;
struct seg
{int val,len;seg(){vallen0;}
};
vectorseg tr;
int n;
void update(int u,int st,int ed)
{if(tr[u].val0){tr[u].lened-st1;}else{if(sted){tr[u].len0;return;}tr[u].lentr[u1].lentr[u1|1].len;}
}
void add(int u,int st,int ed,int l,int r,int x)
{if(lr||ln||rn) return;if(lstedr){tr[u].valx;update(u,st,ed);return;}
// pushdown(u);int midsted1;if(midl)add(u1,st,mid,l,r,x);if(midr)add(u1|1,mid1,ed,l,r,x);update(u,st,ed);
}
int query(int u,int st,int ed,int l,int r)
{if(lr||ln||rn) return 0;if(lstedr){return tr[u].len;}int midsted1;int res0;if(midl)resquery(u1,st,mid,l,r);if(midr)resquery(u1|1,mid1,ed,l,r);return res;
}
void O_o()
{int k;cinnk;mapint,vectorint mp;vectorint a(n1);for(int i1; in; i){cina[i];mp[a[i]].push_back(i);}tr.assign((n2)1,seg());vectorarrayint,2 pos(n1);vectorint p,nxt(n1);p.push_back(-1);for(auto [v,t]:mp){p.push_back(v);int mt.size();for(int i0; im; i){int l,r;if(ik-1m){ln1;}else lt[ik-1];if(ikm){rn1;}else rt[ik];pos[t[i]]{l,r};if(im-1)nxt[t[i]]n1;else nxt[t[i]]t[i1];}}int ans0;for(int in; i1; i--){if(nxt[i]!n1){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 tquery(1,1,n,i,n);ans(n-i1)-t;}coutans\n;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);coutfixedsetprecision(12);int T1;cinT;while(T--){O_o();}
}
