2020-2021:teams:legal_string:组队训练比赛记录:contest14
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest14 [2021/08/13 10:52] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest14 [2021/08/13 19:13] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| | E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| | G | 2 | 0 | 0 | | | G | 2 | 0 | 0 | | ||
| - | | J | 0 | 0 | 0 | | + | | J | 2 | 0 | 0 | |
| | K | 0 | 0 | 0 | | | K | 0 | 0 | 0 | | ||
| | M | 0 | 0 | 0 | | | M | 0 | 0 | 0 | | ||
| 行 192: | 行 192: | ||
| } | } | ||
| enter(ans); | enter(ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== J. Histogram Sequence ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定一个序列 $h$，其中二元组 $(a,b)(a\le b)$ 的权重为 $(b-a+1)\min (h[a\sim b])$。 | ||
| + | |||
| + | 将所有 $\frac {n(n-1)}2$ 个二元组按权重从小到大排序，求第 $L\sim R$ 个二元组。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 考虑构造 $n$ 个集合，第 $i$ 个集合维护所有 $\min (h[a\sim b])=h_i$ 的 $(a,b)$ 二元组。 | ||
| + | |||
| + | 另外为了保证每个二元组恰属于一个集合，强制规定偏序：当 $h_i=h_j$ 时如果 $i\lt j$ 则 $\min(h_i,h_j)=h_i$。 | ||
| + | |||
| + | 单调栈求出每个集合对应的左边界 $L_i$ 和右边界 $R_i$。对每个集合和给定 $S$，显然可以 $O(1)$ 计算出所有满足 $w(a,b)\lt S$ 的二元组个数。 | ||
| + | |||
| + | 于是二分答案求出第 $L$ 个二元组的取值 $S$，然后将每个集合转化为类似迭代器的形式丢入优先队列，求出第 $L\sim R$ 个二元组。 | ||
| + | |||
| + | 时间复杂度 $O(n\log V+(R-L)\log n)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=3e5+5; | ||
| + | int h[MAXN],st[MAXN],vl[MAXN],vr[MAXN]; | ||
| + | LL cal(LL n,LL len){ | ||
| + | len=min(n,len); | ||
| + | return len*(n+n+1-len)/2; | ||
| + | } | ||
| + | LL check(int n,LL s){ | ||
| + | LL ans=0; | ||
| + | _rep(i,1,n){ | ||
| + | LL len=(s-1)/h[i]; | ||
| + | ans+=cal(vr[i]-vl[i]+1,len)-cal(vr[i]-i,len)-cal(i-vl[i],len); | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int cal2(int n,int len){ | ||
| + | return max(n-len+1,0); | ||
| + | } | ||
| + | struct Node{ | ||
| + | int i,curlen; | ||
| + | LL getS()const{ | ||
| + | return 1LL*curlen*h[i]; | ||
| + | } | ||
| + | int count(){ | ||
| + | return cal2(vr[i]-vl[i]+1,curlen)-cal2(vr[i]-i,curlen)-cal2(i-vl[i],curlen); | ||
| + | } | ||
| + | bool has_next(){ | ||
| + | return curlen<vr[i]-vl[i]+1; | ||
| + | } | ||
| + | bool operator < (const Node &b)const { | ||
| + | return getS()>b.getS(); | ||
| + | } | ||
| + | }; | ||
| + | int main(){ | ||
| + | int n=read_int(); | ||
| + | _rep(i,1,n)h[i]=read_int(); | ||
| + | LL ql=read_int(),qr=read_int(); | ||
| + | int tp=0; | ||
| + | _rep(i,1,n){ | ||
| + | while(tp&&h[st[tp]]>h[i])tp--; | ||
| + | vl[i]=st[tp]+1; | ||
| + | st[++tp]=i; | ||
| + | } | ||
| + | tp=0; | ||
| + | for(int i=n;i;i--){ | ||
| + | while(tp&&h[st[tp]]>=h[i])tp--; | ||
| + | if(!tp)vr[i]=n; | ||
| + | else | ||
| + | vr[i]=st[tp]-1; | ||
| + | st[++tp]=i; | ||
| + | } | ||
| + | LL lef=1,rig=MAXN*1e9,ans; | ||
| + | while(lef<=rig){ | ||
| + | LL mid=lef+rig>>1; | ||
| + | if(check(n,mid)<ql){ | ||
| + | ans=mid; | ||
| + | lef=mid+1; | ||
| + | } | ||
| + | else | ||
| + | rig=mid-1; | ||
| + | } | ||
| + | priority_queue<Node> q; | ||
| + | _rep(i,1,n){ | ||
| + | if(1LL*(vr[i]-vl[i]+1)*h[i]>=ans){ | ||
| + | Node t=Node{i,(int)(ans/h[i])}; | ||
| + | if(t.has_next()){ | ||
| + | t.curlen++; | ||
| + | q.push(t); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | LL pos=check(n,ans+1); | ||
| + | for(LL i=ql;i<=qr;i++){ | ||
| + | if(i>pos){ | ||
| + | Node t=q.top();q.pop(); | ||
| + | ans=t.getS(); | ||
| + | pos+=t.count(); | ||
| + | if(t.has_next()){ | ||
| + | t.curlen++; | ||
| + | q.push(t); | ||
| + | } | ||
| + | } | ||
| + | space(ans); | ||
| + | } | ||
| return 0; | return 0; | ||
| } | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest14.1628823143.txt.gz · 最后更改: 2021/08/13 10:52 由 jxm2001
