我们先计算出， 每个点当leader所能掌控的最多人数。 然后我们把询问离线， 丢到responsibility最大的那个地方去。

然后从大到小往线段树里加人， 加入完之后处理掉当前的询问。

 

如果强制在线的话就只能树套树啦。

#include
     
      #define LL long long#define LD long double#define ull unsigned long long#define fi first#define se second#define mk make_pair#define PLL pair
      
       #define PLI pair
       
        #define PII pair
        
         #define SZ(x) ((int)x.size())#define ALL(x) (x).begin(), (x).end()#define fio ios::sync_with_stdio(false); cin.tie(0);using namespace std;const int N = 1e5 + 7;const int inf = 0x3f3f3f3f;const LL INF = 0x3f3f3f3f3f3f3f3f;const int mod = 1e9 + 7;const double eps = 1e-8;const double PI = acos(-1);template
         
           inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}template
          
            inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}template
           
             inline bool chkmax(T& a, S b) { return a < b ? a = b, true : false;}template
            
              inline bool chkmin(T& a, S b) { return a > b ? a = b, true : false;}int n, k, q;int a[N], r[N];int c[N];int hsa[N], tota;int hsr[N], totr;int ans[N];vector
             
               vc[N];vector
              
               
                > qus[N];struct Bit { int a[N]; void modify(int x, int v) { for(int i = x; i < N; i += i & -i) a[i] += v; } int sum(int x) { int ans = 0; for(int i = x; i; i -= i & -i) ans += a[i]; return ans; } int query(int L, int R) { if(L > R) return 0; return sum(R) - sum(L - 1); }} bit;struct SegmentTree {#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1 int mx[N << 2]; inline void pull(int rt) { mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]); } void update(int L, int R, int val, int l, int r, int rt) { if(R < l || r < L || R < L) return; if(L <= l && r <= R) { chkmax(mx[rt], val); return; } int mid = l + r >> 1; update(L, R, val, lson); update(L, R, val, rson); pull(rt); } int query(int L, int R, int l, int r, int rt) { if(R < l || r < L || R < L) return 0; if(L <= l && r <= R) return mx[rt]; int mid = l + r >> 1; return max(query(L, R, lson), query(L, R, rson)); }} Tree;int getPosa(int x) { return lower_bound(hsa + 1, hsa + 1 + tota, x) - hsa;}int getPosr(int x) { return lower_bound(hsr + 1, hsr + 1 + totr, x) - hsr;}int main() { memset(ans, -1, sizeof(ans)); scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), hsa[++tota] = a[i]; for(int i = 1; i <= n; i++) scanf("%d", &r[i]), hsr[++totr] = r[i]; sort(hsa + 1, hsa + 1 + tota); tota = unique(hsa + 1, hsa + 1 + tota) - hsa - 1; sort(hsr + 1, hsr + 1 + totr); totr = unique(hsr + 1, hsr + 1 + totr) - hsr - 1; for(int i = 1; i <= n; i++) { vc[lower_bound(hsa + 1, hsa + 1 + tota, a[i]) - hsa].push_back(mk(r[i], 0)); } for(int i = 1; i <= tota; i++) { for(auto& t : vc[i]) bit.modify(getPosr(t.fi), 1); for(auto& t : vc[i]) { t.se = bit.query(getPosr(t.fi - k), getPosr(t.fi + k + 1) - 1); } } scanf("%d", &q); for(int i = 1; i <= q; i++) { int x, y; scanf("%d%d", &x, &y); int maxa = max(a[x], a[y]); if(r[x] > r[y]) swap(x, y); qus[lower_bound(hsa + 1, hsa + 1 + tota, maxa) - hsa].push_back(mk(mk(r[y] - k, r[x] + k), i)); } for(int i = tota; i >= 1; i--) { for(auto& t : vc[i]) Tree.update(getPosr(t.fi), getPosr(t.fi), t.se, 1, totr, 1); for(auto& q : qus[i]) ans[q.se] = Tree.query(getPosr(q.fi.fi), getPosr(q.fi.se + 1) - 1, 1, totr, 1); } for(int i = 1; i <= q; i++) printf("%d\n", ans[i] == 0 ? -1 : ans[i]); return 0;}/**/