哈理工oj 1390Leyni, LOLI and Numbers解题报告

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1390

这道题，真的挺厉害，虽然用到的东西都不难，但是考察了很多方面，树状数组和二分，这个全用到了，并且还要记录是否访问过

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100005
 4 int a[N];
 5 int used[N];
 6 int n;
 7 int lowbit(int x)
 8 {
 9     return x&-x;
10 }
11 void add(int x)
12 {
13     while(x<=n)
14     {
15         a[x]++;
16         x+=lowbit(x);
17     }
18 }
19 void sub(int x)
20 {
21     while(x<=n)
22     {
23         a[x]--;
24         x+=lowbit(x);
25     }
26 }
27 int getsum(int x)
28 {
29     int sum=0;
30     while(x>=1)
31     {
32         sum+=a[x];
33         x-=lowbit(x);
34     }
35     return sum;
36 }
37 int main()
38 {
39     int t,i,j,k,t1;
40     scanf("%d",&t);
41     while(t--)
42     {
43         memset(a,0,sizeof(a));
44         memset(used,0,sizeof(used));
45         scanf("%d",&n);
46         for(i=1;i<=n;i++)
47         add(i);
48         int temp=n;
49         int sum;
50         int g=0;
51         for(i=0;i<n;i++)
52         {
53             scanf("%d",&t1);
54             if(g)
55             sum=getsum(g);
56             else
57             sum=0;
58             t1=(sum+t1)%temp;
59             if(t1==0)
60             t1=temp;
61             int low=1;
62             int high=n;
63             int mid;
64             while(low<=high)
65             {
66                 //printf("%d %d\n",low,high);
67                 mid=(low+high)/2;
68                 sum=getsum(mid);
69                 if(sum==t1)
70                 {
71                     if(used[mid])
72                     {
73                         high=mid-1;
74                         continue;
75                     }
76                     break;
77                 }
78                 if(sum>t1)
79                 high=mid-1;
80                 else
81                 low=mid+1;
82             }
83             if(i)
84             printf(" ");
85             printf("%d",mid);
86             sub(mid);
87             used[mid]=1;
88             g=mid;
89             temp--;
90         }
91         printf("\n");
92     }
93     return 0;
94 }