Dãy a và b đặc biệt

Có hai dãy số: a và b rất đặc biệt. Dãy a là một hoán vị của 1;2;3;..;n và dãy b được tính theo dãy a như sau: phần tử b[i] bằng số lượng các phần tử đứng trước i trong a và lớn hơn i.

Ví dụ dãy a là 3 4 2 5 1 6 thì dãy b là 4 2 0 0 0 0 . Giải thích: xét với i=1, với quy luật trên đề bài thì phần tử b[i] bằng số lượng các phần tử đứng trước số 1 trong dãy a mà lớn hơn 1. Trong dãy a, có các số 3 4 2 5 đứng trước số 1, trong đó tất cả chúng đều lớn hơn 1. Vậy b[1]=4. Tương tự với các b[2],b[3]...

a) Cho dãy a, hãy tính và xuất ra dãy b.
b) Cho dãy b, hãy tính và xuất ra dãy a.

Bài này littlelee nên nói rõ giới hạn dữ liệu. Nếu n nhỏ thôi thì bài này không có gì để giải, còn nếu n >10^5 thì bài này trở nên khủng khiếp.

Hì hì. Thật ra đây chỉ là bài nho nhỏ thôi. Bài dành cho lớp 9 cơ mà.

Mình post bài này chủ yếu là để các bạn khác nghĩ ra những cách thú vị, nó nghiêng về sáng tạo. Nếu dùng dữ liệu >=10^5 thì khủng thật. Mà cũng chẳng qua là thuật toán thôi, chứ bê nguyên test 10^5 vô thì chưa chắc chi pascal đã chịu nổi.

À administrators ơi, bạn chỉ mình cách tính độ phức tạp và cách tính thời gian thực hiện đi. Đối với dữ liệu lớn thì mình chả biết tính ra là nó chạy trong bao lâu cả. Mình đã đọc tài liệu rồi, tuy nhiên nó phức tạp quá, với lại nó có một số kí tự toán học mihnf chưa học nữa. Mình chỉ cần dugnf sơ sơ thôi, nên nếu có cách hiểu nào đơn giản thì bạn giải thích cho mình nhé.

Theo cách hiểu hiện giờ của mình, nếu xét theo phép tính tích cực thì nếu nó thuộc 1 vòng lặp thì O(n) còn nếu 2 vòng thì là O(n^2). Thôi cứ tạm hiểu thế đã. Nếu với cách hiểu như thế thì bài này, câu a bỏ qua, câu b sẽ là O(n^2). Thật ra thì cách làm của mình cho bài b cũng không phức tạp lắm đâu. Nó chỉ là vận dụng một tí thôi, so với thời gian chạy câu a thì có lẽ bằng nhau. Mình dùng 2 vòng lặp lồng nhau, không dùng đệ quy gì cả.