UVALive 7141 BombX

2014上海區域賽的D題，十分複雜的感覺。

按照x坐标排序，對于炸彈來說，不考慮y坐标的情況，可以看成數軸上的一個線段，

當線段向右移動的時候，可以知道每一個時刻，線段上有多少的點，這一點顯然可以用twopoint搞定O(n)得到。

然後對于每一個時刻，炸彈能炸的最多的數量，顯然是目前線上段上的點，以及不線上段上的點裡，

用H能覆寫的最多的情況，當然，要去掉不能覆寫的那些位置。

這一點，可以在y坐标上的建立線段樹，對于一個在y坐标為a的點，顯然可以給上端在[a,a+H-1]的線段+1，對于不能覆寫的情況，就讓[a,a+H-1]區間減去n

線段樹的節點記錄最大值，那麼此時的根節點就是y坐标上的貢獻，加上之前計算好的線段上的點就是此時的答案。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,int>
#define inone(x) scanf("%d", &x);
#define intwo(x,y) scanf("%d%d", &x, &y);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int T, n, W, H, m, ans, cas = 0;
pii a[N];

int L[N * 30], R[N * 30], t;
LL A[N * 30], F[N * 30];

void clear() { F[0] = F[1] = A[1] = L[1] = R[1] = 0; t = 2; }

int node()
{
  F[t] = A[t] = L[t] = R[t] = 0; return t++;
}

void add(int x, int l, int r, int ll, int rr, int v)
{
  if (ll <= l&&r <= rr)
  {
    A[x] += v;  F[x] += v; return;
  }
  else
  {
    int mid = l + r >> 1;
    if (ll <= mid)
    {
      if (!L[x]) L[x] = node();
      add(L[x], l, mid, ll, rr, v);
    }
    if (rr > mid)
    {
      if (!R[x]) R[x] = node();
      add(R[x], mid + 1, r, ll, rr, v);
    }
    F[x] = max(F[L[x]], F[R[x]]) + A[x];
  }
}

int main()
{
  inone(T);
  while (T--)
  {
    inone(n); intwo(W, H);
    ans = m = 0;
    clear();
    rep(i, 1, n)
    {
      intwo(a[i].ff, a[i].ss);
      m = max(m, a[i].ss);
    }
    if (!W || !H) goto end;
    m += H - 1;
    sort(a + 1, a + n + 1);
    rep(i, 1, n) add(1, 0, m, a[i].ss, a[i].ss + H - 1, 1);
    for (int i = 1, j = 1; i <= n; i++)
    {
      if (i == 1 || a[i].ff != a[i - 1].ff && (j > n || a[j].ff - a[i - 1].ff > W)) ans = max(1LL * ans, j - i + max(0LL, F[1]));
      for (int k; j <= n&&a[j].ff - a[i].ff < W; j = k)
      {
        for (k = j; k <= n&&a[j].ff == a[k].ff; k++)
        {
          add(1, 0, m, a[k].ss, a[k].ss + H - 1, -n);
        }
        ans = max(1LL * ans, k - i + max(0LL, F[1]));
      }
      add(1, 0, m, a[i].ss, a[i].ss + H - 1, n);
    }
    end:printf("Case #%d: %d\n", ++cas, ans);
  }
  return 0;
}