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

## 用树状数组总是超时，帮忙看看啊，谢谢了。。。

Posted by richardxx at 2006-12-27 17:30:32 on Problem 2828
```#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: