[ACM] SCU 1555 Inversion Sequence (线段树)

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1555

输入5个数

1 2 0 1 0

表示1前面有1个比它大的数,2前面有2个比它大的数…..

求一个1~n的排列,比如这个就输出3 1 5 2 4

1前面有1个比它大的数,那么1肯定在第二位

2前面有2个比它大的数,那么2肯定排在第四位,有一位被1占了。

3前面有0个比它大的数,那么3肯定在第一位

维护线段树,叶子结点的值为1,维护和。从左到右找第多少个1就可以了。

比如1前面有1个比它大的数,那么只要从左到右找到第二个1,就是1的位置,找到后,叶子结点设为0.更新。接着找。

typedef long long ll;
const int maxn=10010;
int ci[maxn];
int ans[maxn];
int n;
struct ST
{
    int l,r;
    int sum;
}st[maxn<<2];
bool ok;
int tot;
int pos;
void pushup(int i)
{
    st[i].sum=st[i<<1].sum+st[(i<<1)|1].sum;
}

void build(int i,int l,int r)
{
    st[i].l=l;
    st[i].r=r;
    if(st[i].l==st[i].r)
    {
        st[i].sum=1;
        return;
    }
    int mid=(st[i].l+st[i].r)>>1;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
    pushup(i);
}

void query(int i,int t)
{
    if(t>st[i].sum)
    {
        ok=0;
        return;
    }
    if(st[i].l==st[i].r)
    {
        pos=st[i].l;
        st[i].sum=0;
        return;
    }
    if(t<=st[i<<1].sum)
        query(i<<1,t);
    else
        query((i<<1)|1,t-st[i<<1].sum);
    pushup(i);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        ok=1;
        build(1,1,n);
        tot=0;
        int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            if(!ok)
                continue;
            query(1,x+1);
            ans[pos]=i;
        }
        if(!ok)
        {
            printf("No solution\n");
            continue;
        }
        printf("%d",ans[1]);
        for(int i=2;i<=n;i++)
            printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}

类似的一个题,给出逆序数,把它还原成原数列。

http://acm.fzu.edu.cn/problem.php?pid=2184

每组数据第一行为一个整数N(1<=N<=1000),表示该序列的数字个数。

第二行为N个整数,第i个数字表示排在ai之后比ai小的数字个数。

Output

输出为一行N个整数,表示原数列。

Sample Input

5

2 0 1 0 0

Sample Output

3 1 4 2 5

const int maxn=1110;
int ans[maxn];
bool vis[maxn];
int n;

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        int x;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            int cnt=0;
            int pos;
            for(int j=1;j<=n;j++)
            {
                if(cnt==x+1)
                {
                    vis[pos]=1;
                    break;
                }
                if(!vis[j])
                {
                    pos=j;
                    cnt++;
                }
            }
            ans[i]=pos;
        }
        cout<<ans[1];
        for(int i=2;i<=n;i++)
            printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}
时间: 04-04

[ACM] SCU 1555 Inversion Sequence (线段树)的相关文章

CSUOJ 1555 Inversion Sequence 线段树

Inversion Sequence Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%lld & %llu Description For sequence i1, i2, i3, … , iN, we set aj to be the number of members in the sequence which are prior to j and greater to j at the same time.

HDOJ 4893 Wow! Such Sequence! 线段树

http://acm.hdu.edu.cn/showproblem.php?pid=4893 题意:10万的区间,初始都为0,10万次操作,三种操作为单点修改,区间将每个数改成最近的斐波那契数,以及区间求和. 分析:用一个flag记录该段是否被改成斐波那契数,同时多维护一个sum1表示如果该段改成斐波那契数,区间和为多少.开始sum1为区间长度,之后在单点做了修改以后对其更新,需要的时候用其覆盖sum. 1 #include<cstdio> 2 #include<cstring>

Minimum Inversion Number(线段树单点更新+逆序数)

Minimum Inversion Number(线段树单点更新+逆序数) Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit Status Description The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy

2014多校3 Wow! Such Sequence!线段树

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4893 这题实在是让人纠结啊--好久不写线段树的题了,因为这几天学伸展树,然后觉得线段树小case了.没想到栽在这题上了.尼玛-- 自己把自己给搞晕了--想复杂了,都不懂得预处理一下,唉--还得怒刷几十道啊!! #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #in

HDU 1394 Minimum Inversion Number.(线段树)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394 ~~~~ 早起一发线段树,开心又快乐.这题暴力也能水过,同时线段树的效率也就体现的尤为明显了,看了大牛的博客,说是还可以用树状数组,点树和合并序列写,现在还不懂,留着以后在写吧. ~~~~ 大致题意:给定一个数字序列,同时由此可以得到n个序列, 要求从n个序列中找到逆序数最小的序列,输出最小逆序数. 首先介绍下逆序数的概念: 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面

CSUOJ 1555 Inversion Sequence

1555: Inversion Sequence Time Limit: 2 Sec  Memory Limit: 256 MBSubmit: 107  Solved: 34 Description For sequence i1, i2, i3, … , iN, we set aj to be the number of members in the sequence which are prior to j and greater to j at the same time. The seq

hdu 4893 Wow! Such Sequence!(线段树)

题目链接:hdu 4983 Wow! Such Sequence! 题目大意:就是三种操作 1 k d, 修改k的为值增加d 2 l r, 查询l到r的区间和 3 l r, 间l到r区间上的所以数变成最近的斐波那契数,相等的话取向下取. 解题思路:线段树,对于每个节点新增一个bool表示该节点以下的位置是否都是斐波那契数. #include <cstdio> #include <cstring> #include <cstdlib> #include <algor

hdu 4893 (多校1007)Wow! Such Sequence!(线段树&amp;二分&amp;思维)

Wow! Such Sequence! Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 352    Accepted Submission(s): 104 Problem Description Recently, Doge got a funny birthday present from his new friend, Prot

Hdu1394Minimum Inversion Number线段树

这个网上一搜一大堆,就是先求一个,其余的for一遍搞出来. #include<stdio.h> #include<stdlib.h> #define max 5555 int sum[max * 4]; int min(int a, int b) { if (a>b) return b; else return a; } void fuqin(int a) { sum[a] = sum[a * 2] + sum[a * 2 + 1]; } void build(int l,