爬山题解不想写了
学数数
离散化然后找到以每一个值为最大值的连续子段有多少个,然后开个桶维护
那么怎么找以每一个值为最大值的连续子段个数
方法1(我的极笨的方法)
考试时我的丑陋思路,
定义极左值为左面第一个大于当前值的值,极右值为右面第一个大于当前值的值
,找到最大值然后当前符合的子段个数就为$r-l+1+(r-now)*(now-l)$
解释一下$r-l+1$为以$now$为边界的子段,$(r-now)*(now-l)$为包含$now$的子段
那么问题又转化为了如何求边界
我们发现找极左值,极右值过程可以二分实现,
我们每次找到最大值,然后找到左右子段的最大值和$id$,这些子段的最大值边界就是当前$now$!!!!
维护最大值$id$可以线段树实现
给一下实现
简单好想个屁嘞
但是比较直观是真的
void pre(ll l,ll r,ll now,ll nowmax){ if(l>r) return ; if(l==r) { sum[nowmax]++; return ; } sum[nowmax]+=r-l+1+(r-now)*(now-l); maxn=0,ida=0; if(l<=now-1) { seg_max(1,l,now-1); pre(l,now-1,ida,maxn); } maxn=0,ida=0; if(now+1<=r) { seg_max(1,now+1,r); pre(now+1,r,ida,maxn); } }
总代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 2222222 ll n,q,mx,mn=0x7fffffffff,ida,maxn,idb; ll a[A],sum[A],b[A]; char c[10]; struct tree{ ll l,r,val,id; }tr[A]; void pushup(ll p){ if(tr[p<<1].val>tr[p<<1|1].val){ tr[p].val=tr[p<<1].val; tr[p].id=tr[p<<1].id; } else { tr[p].val=tr[p<<1|1].val; tr[p].id=tr[p<<1|1].id; } } void built(ll p,ll l,ll r){ tr[p].l=l,tr[p].r=r; if(l==r){ tr[p].val=a[l]; tr[p].id=l; return ; } ll mid=(l+r)>>1; built(p<<1,l,mid); built(p<<1|1,mid+1,r); pushup(p); } void seg_max(ll p,ll l,ll r){ // printf("p=%lld l=%lld r=%lld l=%lld r=%lld ",p,l,r,tr[p].l,tr[p].r); if(tr[p].l>=l&&tr[p].r<=r){ if(tr[p].val>maxn){ maxn=tr[p].val; ida=tr[p].id; } return ; } ll mid=(tr[p].l+tr[p].r)>>1; if(mid>=l) seg_max(p<<1,l,r); if(mid<r) seg_max(p<<1|1,l,r); } void pre(ll l,ll r,ll now,ll nowmax){ if(l>r) return ; if(l==r) { sum[nowmax]++; // printf("l=%lld nowmax=%lld ",l,nowmax); return ; } // printf("l=%lld r=%lld nowmax=%lld r-l=%lld ",l,r,nowmax,r-l+1); sum[nowmax]+=r-l+1+(r-now)*(now-l); maxn=0,ida=0; if(l<=now-1) { seg_max(1,l,now-1); pre(l,now-1,ida,maxn); } maxn=0,ida=0; if(now+1<=r) { seg_max(1,now+1,r); pre(now+1,r,ida,maxn); } } int main(){ scanf("%lld%lld",&n,&q); for(ll i=1;i<=n;i++){ scanf("%lld",&a[i]); b[i]=a[i]; if(a[i]>mx){ ida=i; mx=a[i]; } mn=min(mn,a[i]); } sort(b+1,b+n+1); ll m=unique(b+1,b+n+1)-b-1; // for(ll i=1;i<=m;i++){ // printf("b=%lld ",b[i]); // } for(ll i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b; built(1,1,n); pre(1,n,ida,a[ida]); for(ll i=1;i<=n;i++) sum[i]+=sum[i-1]; for(ll i=1,que;i<=q;i++){ scanf("%s",c+1); scanf("%lld",&que); ll nxt=(lower_bound(b+1,b+m+1,que)-b), pre=(upper_bound(b+1,b+m+1,que))-b-1; // printf("pre=%lld nxt=%lld ",pre,nxt); if(c[1]=='<'){ if(que>mx){ printf("%lld ",sum[n]); continue ; } if(que<mn){ printf("0 "); continue ; } if(pre!=nxt) printf("%lld ",sum[pre]); else printf("%lld ",sum[pre-1]); } else if(c[1]=='='){ if(que>mx||que<mn){ printf("0 "); continue ; } if(pre==nxt) printf("%lld ",sum[pre]-sum[pre-1]); else printf("0 "); } else if(c[1]=='>'){ if(que>mx){ printf("0 "); continue ; } if(que<mn){ printf("%lld ",sum[n]); continue ; } if(pre==nxt) printf("%lld ",sum[n]-sum[pre]); else printf("%lld ",sum[n]-sum[pre]); } } }
方法2
单调栈,显然可以单调栈,看到这个就必须想单调栈啊!
维护一个单调下降的栈当发现当前值比队尾小接着插,发现当前值不小$pop$,当前值的$l$就是$pop$后单调栈的栈顶,已经$pop$掉的值的$r$就是当前值
代码咕了
七十和十七
设$g[i]$为将相对大小为$i$的数插到队头要花多少步复原
注意是相对大小
以下说的1,2...都是相对大小
我们将$1$移到队头要$1$步复原,$g[1]=1$
将$2$移到队头你相对大小为$1$的也要复原$g[2]=g[1]+1$
将$3$移到队头你大小$1,2$也要复原$g[3]=g[2]+g[1]+1$
...类推
$g[n]=sumlimits {i=1}^{i<=n-1}(g[i])+1$
然后我们设$f$为移动总步数
$f[i]=f[i-1](为1的情况)+sumlimits_{j=1}^{j<=i-1} f[i-1]+(i-1)!*g[j]$
,最后再同时除以$i!$,为了方便我们设$E[i]=frac{f[i]}{i!}$
原式变为$E[i]=E[i-1]+frac{2^{i-1}-1}{i}$
我们化简移项等操作$xjb$搞就$AC$了