首页 > 代码库 > COGS 859. 数列
COGS 859. 数列
/*先来说一下第一眼看到想出的奇葩方法23333..找每个数左右有几个比他小的前几天刚学了区间第k小的求法然后...枚举中间的那个点 对于左区间 二分找到他是第几大 右区间同理然后 *起来 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 50010#define maxm 50010*18*5#define ll long longusing namespace std;ll n,cnt,root[maxn],order[maxn],a[maxn],ans;struct node{ ll lc,rc,sum;}t[maxm];ll init(){ ll x=0;char s=getchar(); while(s<‘0‘||s>‘9‘)s=getchar(); while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x;}ll Build(ll S,ll L,ll R){ ll k=++cnt;t[k].sum=S; t[k].lc=L;t[k].rc=R; return k;}void Insert(ll &root,ll pre,ll pos,ll l,ll r){ root=Build(t[pre].sum+1,t[pre].lc,t[pre].rc); if(l==r)return; ll mid=l+r>>1; if(pos<=mid)Insert(t[root].lc,t[pre].lc,pos,l,mid); else Insert(t[root].rc,t[pre].rc,pos,mid+1,r);}ll Query(ll L,ll R,ll k,ll l,ll r){ if(l==r)return l; ll sum=t[t[R].lc].sum-t[t[L].lc].sum; ll mid=l+r>>1; if(k<=sum)return Query(t[L].lc,t[R].lc,k,l,mid); else return Query(t[L].rc,t[R].rc,k-sum,mid+1,r);}int main(){ //freopen("queueb.in","r",stdin); //freopen("queueb.out","w",stdout); n=init(); for(ll i=1;i<=n;i++){ a[i]=init(); order[i]=a[i]; } sort(order+1,order+1+n); ll num=n,pos,l,r,x,s1,s2; for(ll i=1;i<=n;i++){ pos=lower_bound(order+1,order+1+n,a[i])-order; Insert(root[i],root[i-1],pos,1,num); } for(ll i=1;i<=n;i++){ x=a[i];s1=s2=0; l=1;r=i; while(l<=r){ ll mid=l+r>>1; pos=Query(root[0],root[i],mid,1,num); if(order[pos]<x){ s1=mid;l=mid+1; } else r=mid-1; } l=1;r=n-i+1; while(l<=r){ ll mid=l+r>>1; pos=Query(root[i-1],root[n],mid,1,num); if(order[pos]<x){ s2=mid;l=mid+1; } else r=mid-1; } ans+=s1*s2; } printf("%lld\n",ans); return 0;}
/*其实求左右各有几个比他小的 可以用树状数组逆序对是求左边几个比他大的这个一样啊注意右边的时候离散化排序和左边不一样 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 50010#define ll long longusing namespace std;int n,b[maxn],t[maxn],l[maxn],r[maxn];ll ans;struct node{ int o,x;}a[maxn];int init(){ int x=0;char s=getchar(); while(s<‘0‘||s>‘9‘)s=getchar(); while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x;}int cmp1(const node &a,const node &b){ if(a.x==b.x)return a.o>b.o; return a.x<b.x;}int cmp2(const node &a,const node &b){ if(a.x==b.x)return a.o<b.o; return a.x<b.x;}void Add(int pos,int data){ while(pos<=n){ t[pos]+=data; pos+=pos&(-pos); }}int find(int pos){ int r=0; while(pos){ r+=t[pos]; pos-=pos&(-pos); } return r;}int main(){ freopen("queueb.in","r",stdin); freopen("queueb.out","w",stdout); n=init(); for(int i=1;i<=n;i++){ a[i].x=init(); a[i].o=i; } sort(a+1,a+1+n,cmp1); for(int i=1;i<=n;i++) b[a[i].o]=i; for(int i=1;i<=n;i++){ Add(b[i],1); l[i]=find(b[i]-1); } memset(t,0,sizeof(t)); sort(a+1,a+1+n,cmp2); for(int i=1;i<=n;i++) b[a[i].o]=i; for(int i=n;i>=1;i--){ Add(b[i],1); r[i]=find(b[i]-1); } for(int i=1;i<=n;i++) ans+=(ll)l[i]*r[i]; printf("%lld\n",ans); return 0;}
COGS 859. 数列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。