首页 > 代码库 > 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. 数列