# [ACM] SCU 1555 Inversion Sequence (线段树）

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

1 2 0 1 0

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

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

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

```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

Output

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;
}
```

## 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

## 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 (多校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