HDU 5775 Bubble Sort [Array] [Data Structure]

#include #define abs(x) (((x)>0)?(x):-(x))#define lalal puts("* ********")#define Rep(a,b,c) for(int a=(b);a<=(c); a++)#define Req(a,b,c) for(int a=(b);a>=(c);a--) #define Rop(a,b,c) for(int a=(b);a<(c);a++)#define s1(a) scanf("%d",&a)using namespace std;/*********************** ***************/const int N = 100000+5;#define lowbit(x) (x&-x)int sum[N],cnt,ans[N],a [N];void update(int index,int< /span> val){ for(int i=index;i<=cnt;i+=lowbit( i)) sum[i]+=val; return;}int getSum(int index){ int ans = 0; for(int i=index;i>0;i -=lowbit(i)) ans+=sum[i]; return ans;}int main() {i nt _,kc,x; while(~s1(_)){ kc=0; while(_--){ s1(cnt); memset(sum,0,sizeof(sum)); memset(ans, 0,sizeof(ans)); Rep(i, 1,cnt){ s1(a[i]); ans[a[i]] =getSum(cnt)-getSum(a[i]); update(a[i],1);} memset(sum,0,sizeof(sum)); Req(i,cnt,1){ ans[a[i]] =max( ans[a[i]],getSum(a[i])); update(a[i],1); } printf("Case #%d:",++kc); Rep(i,1,cnt) printf(" %d" ,ans[i]); puts("");}} return 0;}

Topic link: http:// acm.hdu.edu.cn/showproblem.php?pid=5775

———————————————————.
Bubble Sort

p>

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1241 Accepted Submission(s): 683

Problem Description
P is a permutation of the integers from 1 to N(index starting from 1).
Here is the code of Bubble Sort in C++.

for(int i =1;i<=N;++i)
for(int j=N,t;j>i;—j)
if(P[j-1]> P[j])
t=P[j],P[j]=P[j-1],P[j-1]=t;

After the sort, th e array is in increasing order. ?? wants to know the absolute values ​​of difference of rightmost place and leftmost place for every number it reached.

Input
The first line of the input gives the number of test cases T; T test cases follow.
Each consists of one line with one integer N, followed by another line with a permutation of the integers from 1 to N, inclusive.

limits
T <= 20
1 <= N <= 100000
N is larger than 10000 in only one case.

Output
For each test case output “Case #x: y1 y2 … YN” (without quotes), where x is the test case number (starting from 1), and yi is the difference of rightmost place and leftmost place of number i.

Sample Input
2 < br> 3
3 1 2
3
1 2 3

Sample Output
Case #1: 1 1 2
Case #2: 0 0 0

Hint
In first case, (3, 1, 2) -> (3, 1, 2) -> (1, 3, 2) -> (1, 2, 3)
the leftmost place and rightmost place of 1 is 1 and 2, 2 is 2 and 3, 3 is 1 and 3
In secon d case, the array has already in increasing order. So the answer of every number is 0.

Author
FZU

Source
2016 Multi-University Training Contest 4

————————————————————.

The main idea of ​​the topic:
is to ask each number to bubble in order The interval size of the position in the process of

The idea of ​​solving the problem:
Written by hand, the result is found to be
max (the first few are larger than a_i, and the latter are smaller than a_i);
In fact, I also really want to use the exchange rule of bubble sorting.
It is easy to calculate the left and right shifts of each number.
As for why the result is the maximum value of the two, it is also very good to think, < br> Because the difference between the two is a_i-i, it is

Other situations should be similar to this, so I won’t repeat it here/

Then use a tree array to maintain Just two times.

Attach the question code
—————————————.

#include #define abs(x) (((x)>0)?(x):-(x)) #define lalal puts("*********")#define Rep(a ,b,c) for(int a=(b);a<=(c);a++)#define Req(a,b,c) for(int a= (b);a>=(c);a--)#define Rop(a,b,c) for(int a=(b);a< (c);a++)#define s1(a) scanf("%d",&a)using  namespace std;/**** **********************************/const  int N = 100000+5 span>;#define lowbit(x) (x&-x)int sum[N],cnt, ans[N],a[N];void update(int index,int val){ for(int i=index;i<= cnt;i+=lowbit(i)) sum[i]+=val; return;}int getSum (int index){ int ans = 0; for(int i=index;i>0 ;i-=lowbit(i)) ans+=sum[i]; return ans;}int< /span> main(){ int _,kc,x; while(~s1(_)) {kc=0; while(_--){ s1(cnt); memset(sum,0,sizeof(sum)); < span class="hljs-built_in">memset(ans,0,sizeof(ans )); Rep(i,1,cnt){ s1(a[i]); ans[a[i]] =getSum(c nt)-getSum(a[i]); update(a[i],1);} memset(sum,0,sizeof(sum)); Req(i,cnt,1){ ans[a[i]] =max(ans[a[i]],getSum(a[i])); update(a[i],1);} printf("Case #%d:",++kc); Rep(i,1,cnt) printf(" %d",ans[i]); puts(""< /span>);}} return 0;}