BZOJ 2244 拦截导弹

BZOJ 2244 拦截导弹

题源：现在没了 借luogu的用用：https://www.luogu.org/problem/P2487

sol：

是一个二维条件捆绑的dp，可以考虑cdq分治或者二维线段树去搞，二维线段树比较卡空间，但是更简单粗暴

想想cdq分治咋做。

第一个询问直接cdq分治处理，第二个询问貌似直接记转移数量好像不太行，因为相同的答案转移的时候可能是并行关系而不是前驱后继关系。

一个点可能被打下来，当且仅当这个点在一个合法的答案序列里，现在出现了新问题，如何确定一个点一定在一个合法序列里。

可以想到一个点在合法序列里，当且仅当正着做\(LDS\)和反着做\(LIS\)到这个点的时候的答案加起来-1是最后答案，假设\(g_{i,0/1}\)表示到\(i\)这个点正/反做的方案数，明显这个点在的合法序列个数是\(g_{i,0}\times g_{i,1}\)。

然后就是用动态开点线段树去查前缀最大值捆绑一个方案数

注意cdq的顺序，同时正着cdq完了之后别忘了先对序列反着排一遍序保证第一维正确性

减少码量的方法是打翻转标记和重载的时候分类讨论

记得回收空间，这样不会有复杂度损失

这里有个小细节，cdq分治处理点的贡献的时候，注意一个当前答案为1的点不能被答案0+1更新，如果更新的话方案数会记重复，如果这个点为0可以用之前的一个点去更新。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
const int N = 1e5+7;
#define R register
#define debug printf("GG\n")
typedef double LL;
struct SEGT {
  int lc, rc;
  struct MAX {
    int val, x;
    LL k;
    //MAX(){}
    inline MAX(int a = 0, int b = 0, LL c = 0) {
      val = a, x = b, k = c;
    }
  } p;
} t[N*25];
int cnt = 1;
SEGT I;
void clear(int u) {
  if (!u) return;
  t[u].p = SEGT::MAX(0, 0, 0);
  clear(t[u].lc), clear(t[u].rc);
  t[u].lc = t[u].rc = 0;
  if(u == 1) cnt = 1;
}
inline void pushup(int u) {
  if (t[t[u].lc].p.x == t[t[u].rc].p.x) {
    t[u].p = SEGT::MAX(t[t[u].lc].p.val, t[t[u].rc].p.x, t[t[u].lc].p.k + t[t[u].rc].p.k);
  } else {
    if (t[t[u].lc].p.x < t[t[u].rc].p.x) 
      t[u].p = SEGT::MAX(t[t[u].rc].p.val, t[t[u].rc].p.x, t[t[u].rc].p.k);
    else t[u].p = SEGT::MAX(t[t[u].lc].p.val, t[t[u].lc].p.x, t[t[u].lc].p.k);
  }
}
void ins(int &u, int l, int r, int pos, int x, LL k) { // pos 最大值 方案数 
  if (!u) u = ++cnt;
  if (l == r) {
    if (t[u].p.x == x) t[u].p.k += k;
    else if (t[u].p.x < x) t[u].p = SEGT::MAX(pos, x, k);
    return;
  }
  int MID = (l + r) >> 1;
  if (pos <= MID) ins(t[u].lc, l, MID, pos, x, k);
  else ins(t[u].rc, MID + 1, r, pos, x, k);
  pushup(u);
}
inline SEGT query(int u, int l, int r, int sl, int sr) {
  if (!u) return t[u];
  if (sl == l && sr == r) return t[u];
  int MID = (l + r) >> 1;
  if (sr <= MID) return query(t[u].lc, l, MID, sl, sr);
  else if (sl > MID) return query(t[u].rc, MID + 1, r, sl, sr);
  else {
    SEGT LC = query(t[u].lc, l, MID, sl, MID), RC = query(t[u].rc, MID + 1, r, MID + 1, sr);
    if (LC.p.x == RC.p.x) {
      LC.p.k += RC.p.k;
      return LC;
    } else {
      if (LC.p.x >= RC.p.x) return LC;
      else return RC;
    }
  }
}
int n, m;
struct Node {
  int ai, bi, ci, aci;
  int f[2];
  LL g[2]; // f 转移max g方案数 
} p[N*2];
bool flip = 0;
inline int cmp1(Node a, Node b) {
  if (flip) {
    if (a.bi == b.bi) return a.ai > b.ai;
    return a.bi < b.bi;
  }
  if (a.bi == b.bi) return a.ai < b.ai;
  return a.bi > b.bi;
}
inline int cmp2(Node a, Node b) {
  if (flip) return a.ai > b.ai;
  return a.ai < b.ai;
}
int RT = 1;
void cdq(int l, int r, int o) {
  //printf("%d %d\n", l, r);
  if (l == r) {
    if (!p[l].f[o]) {
      //if (!o) printf("%dx", l);
      p[l].f[o] = p[l].g[o] = 1;
    }
    return;
  }
  int MID = (l + r) >> 1;
  std :: sort(p + l, p + MID + 1, cmp2);
  cdq(l, MID, o);
  std :: sort(p + l, p + MID + 1, cmp1);
  std :: sort(p + MID + 1, p + r + 1, cmp1);
  clear(1);
  int pl = l, pr = MID + 1, nx;
  while (pl <= MID && pr <= r) {
    if (flip) {
      if (p[pl].bi <= p[pr].bi) ins(RT, 1, m, p[pl].aci, p[pl].f[o], p[pl].g[o]), pl++;
      else {
        SEGT nx = query(1, 1, m, 1, p[pr].aci);
        if (!nx.p.x) nx.p.k = 1;
        if (p[pr].f[o] == nx.p.x + 1 && nx.p.x > 0) p[pr].g[o] += nx.p.k;
        else if (p[pr].f[o] < nx.p.x + 1) p[pr].f[o] = nx.p.x + 1, p[pr].g[o] = nx.p.k;
        pr++;
      }
    } else {
      if (p[pl].bi >= p[pr].bi) ins(RT, 1, m, p[pl].aci, p[pl].f[o], p[pl].g[o]), pl++;
      else {
        SEGT nx = query(1, 1, m, p[pr].aci, m);
        if (!nx.p.x) nx.p.k = 1;
        if (p[pr].f[o] == nx.p.x + 1 && nx.p.x > 0) p[pr].g[o] += nx.p.k;
        else if (p[pr].f[o] < nx.p.x + 1) p[pr].f[o] = nx.p.x + 1, p[pr].g[o] = nx.p.k;
        pr++;
      }
    }
  }
  while (pr <= r) {
    SEGT nx = flip > 0 ? query(RT, 1, m, 1, p[pr].aci) : query(RT, 1, m, p[pr].aci, m);
    if (!nx.p.x) nx.p.k = 1;
    if (p[pr].f[o] == nx.p.x + 1 && nx.p.x > 0) p[pr].g[o] += nx.p.k;
    else if (p[pr].f[o] < nx.p.x + 1) p[pr].f[o] = nx.p.x + 1, p[pr].g[o] = nx.p.k;
    pr++;
  } 
  std :: sort(p + MID + 1, p + r + 1, cmp2);
  cdq(MID + 1, r, o);
}
int tmp[N];
void cerr() {
  printf("F's VAL : \n");
  for (R int i = 1; i <= n; i++)
    printf("%d %d\n", p[i].g[0], p[i].g[1]);
}
int main() {
  scanf("%d", &n);
  for (R int i = 1; i <= n; i++)
    scanf("%d%d", &p[i].bi, &p[i].ci), p[i].ai = i, tmp[i] = p[i].ci;
  // lower_bound
  std :: sort(tmp + 1, tmp + n + 1);
  m = std :: unique(tmp + 1, tmp + n + 1) - (tmp + 1);
  for (R int i = 1; i <= n; i++)
    p[i].aci = std :: lower_bound(tmp + 1, tmp + m + 1, p[i].ci) - tmp;
  // cdq
  cdq(1, n, 0); flip = 1; clear(1); std :: sort(p + 1, p + n + 1, cmp2); cdq(1, n, 1);
  //
  int anx = 0;
  LL pmax = 0;
  std :: sort(p + 1, p + n + 1, cmp2);
  for (R int i = 1; i <= n; i++)
    if (p[i].f[0] > anx) anx = p[i].f[0], pmax = p[i].g[0];
    else if (p[i].f[0] == anx) pmax += p[i].g[0] * p[i].g[1];
  //cerr();
  printf("%lld\n", anx);
  flip = 0, std :: sort(p + 1, p + n + 1, cmp2);
  for (R int i = 1; i <= n; i++) {
    if (p[i].f[0] + p[i].f[1] - 1 == anx)
      printf("%lf ", (1.0 * p[i].g[0] * p[i].g[1]) / (1.0 * pmax));
    else printf("0.00000 ");
  }
  
}

BZOJ 2244 拦截导弹

原文：https://www.cnblogs.com/cjc030205/p/11715082.html