G 题数组笑传之查查表 求hack数据

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <math.h>
#include <map>
#include <set> 
#include <queue>
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, mod = 1e17 + 7;

int n, m;
int a[N], b[N];
struct Node
{
    int val, id, cnt; //值 编号 前cnt个 后cnt个
    bool operator > (const Node &t) const
    {
        return val > t.val;
    }
    bool operator < (const Node &t) const
    {
        return val < t.val;
    }
}side[N];

int tr[N];
int ans[N];

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

void insert(int x, int d)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i ; i -= lowbit(i)) res += tr[i];
    return res;
}

int find(int d)
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(query(mid) > d) r = mid - 1;
        else l = mid;
    }
    return l;
}

void solve() 
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    
    priority_queue<Node, vector<Node>, greater<Node>> q;
    
    for(int i = 1; i <= n; i++) 
    {
        side[i] = {a[i], i, b[i]};
        q.push(side[i]);
    }
    
    sort(side + 1, side + 1 + n);

    for(int i = 1; i <= n; i++)
    {
        auto [val, id, cnt] = side[i];
        // cout << val <<endl;
        while(q.size() && q.top().val < val)
        {
            auto tmp = q.top();
            q.pop();
            insert(tmp.id, 1);
        }
        int sum = query(n);
        if(cnt >= sum)
        {
            ans[id] = sum;
            continue;
        }
        // if(sum == 0) continue;
        
        int dl = cnt, dr = sum - cnt + 1; // 前面 和后面的位置
        int l = find(dl), r = find(dr);
        if(l < r) continue; // 没有交点
        
        ans[id] = query(l) - query(r - 1);
    }
    for(int i = 1; i <= n; i++) cout << ans[i] << " ";
}
//牛客小白---->>>> 97 <<<<----
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) 
    {
        solve();
    }
    return 0;
}

int dl = cnt, dr = sum - cnt ; // 前面 和后面的位置        
int l = find(dl), r = find(dr);        
if(l < r) continue; // 没有交点                 
ans[id] = query(l) - query(r);
写成这样就过掉了 为什么