Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 好象求rank时复杂度高了些啊

Posted by daringQQ at 2006-12-27 17:47:17 on Problem 2828
In Reply To:用树状数组总是超时，帮忙看看啊，谢谢了。。。 Posted by:richardxx at 2006-12-27 17:30:32
> #include <stdio.h>
> #include <string.h>
>
> #define N 2<<18
>
> struct item
> {
>   int pos;
>   int value;
> };
>
> struct item input[N];
> int c[N];
> int a[N];
> int n;
>
> void init()
> {
>   memset(a,0,sizeof(a));
>   memset(c,0,sizeof(c));
> }
>
> int low_bit(int x)
> {
>   return x&(x^(x-1));
> }
>
> int get_sum(int x)
> {
>   int res=0;
>
>   while (x>0) {
>     res+=c[x];
>     x-=low_bit(x);
>   }
>   return res;
> }
>
> {
>   while (x<=n) {
>     c[x]+=1;
>     x+=low_bit(x);
>   }
> }
>
> void solve()
> {
>   int i,v;
>   int t,temp;
>
>   for (i=n-1;i>-1;--i) {
>     v=input[i].pos;
>     t=get_sum(v);
>     while (v+t<=n && a[v+t]) t=get_sum(v+t);
>     a[v+t]=input[i].value;
>   }
>   for (i=1;i<=n;++i)
>     printf("%d ",a[i]);
>   putchar('\n');
> }
>
> int main()
> {
>   int i;
>
>   while (scanf("%d",&n)!=EOF) {
>     init();
>     for (i=0;i<n;++i) {
>       scanf("%d %d",&input[i].pos,&input[i].value);
>       input[i].pos++;
>     }
>     solve();
>   }
>
>   return 0;
> }

Followed by: