AcWing 244. Enigmatic cow (tree array + binary search)

The question ：

Ideas ：

We use it h[] I can infer the height of all cows ,a[i] Indicates the current i How many cows are low on the left of the cow ,c[] Represents a tree array .

We found that , if The first i On the left side of the cow a[i] A cow is shorter than it , So its height h[i] Two conditions have to be met ：

• ① In numbers 1~n Middle ranking The first a[i] + 1 Small .

• ② Not in the h[i+1],h[i+2],…,h[n] in There have been .

• （ Because we use reverse order traversal ,h[i+1]~h[n] These are i The height of all cows on the right of the cow has been determined , Of course not ）

General process ：

We Traverse each number in reverse order a[i]：

• ① Each time from Of the remaining numbers Find No k=a[i]+1 Small number （ This is the law we found above ）.

• ② Delete The number of .

analysis ：

The answer can already be found by performing the above two steps , But the range of observation data ：n<=1e5, step ① in Because when traversing each number, you have to find the target value from the remaining numbers , need O(n^2) Level of complexity , We obviously need to optimize , Consider using Tree array plus two points To optimize .

First, let a[1]~a[n] All for 1, Express We can use this height once more , Use Tree array c stay O(logn) Within the time complexity of maintenance a[1]~a[n] Of The prefix and （ Tree arrays are used to maintain prefixes and ）, If you want to Delete a number Subtract directly from this position 1 that will do （ Single point modification , It's also O(logn),add(x, -1)）

In the subject ,ask(x) Indicates the interval 1~x in How many numbers are left , If we want to be in the rest ask(x) Find the number k Small number , What should be looked for is the smallest x, bring ask(x)=k.

That's the step ② It is equivalent to finding the smallest x, bring ask(x)=k.（ask(x)<k Express 1~x Moderate deficiency k Number , Surely not ）

because ask(x) Obviously monotonous , Therefore, we can use dichotomy to find the above search process .

To sum up ： in other words , We want to Maintain one in real time 01 Sequence , Support Query the first k individual 1 The location of （ Binary search left boundary ）, as well as Modify a value in the sequence .

（01 Sequence It's constantly changing , therefore Left and right boundaries of binary search It always includes the whole 1~n Region ）

Time complexity ：

O(n(logn^2))（ Tree arrays and binary constants are very small , Maybe faster than the balance tree ）

Code ：（ The code details are reflected in the above problem solution ）

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+10;
int h[N], a[N], c[N];
int n;

inline int lowbit(int x) {return x&(-x);}

int ask(int x)
{
        int ans = 0;
        while(x) {ans+=c[x], x-=lowbit(x);}
        return ans;
}

int add(int x, int y)
{
        for(; x<=n; x+=lowbit(x)) c[x]+=y;
}

int main()
{
        cin>>n;
        add(1, 1);
        for(int i=2;i<=n;++i)
        {
                scanf("%d", &a[i]);
                add(i, 1);
        }

        for(int i=n; i>=1; --i)
        {
                int k = a[i]+1;
                int l = 1, r = n;//01 The sequence is constantly changing , Therefore, the left and right boundaries of binary search always contain the whole 1~n Region 
                while(l<r)
                {
                        int mid = l+r>>1;
                        if(ask(mid)>=k) r = mid;
                        else l = mid + 1;
                }
                h[i] = l;
                add(l, -1);
        }

        for(int i=1;i<=n;++i) printf("%d\n", h[i]);

        return 0;
}