四维偏序 cdq套cdq

(Updated: )
(16 mins to read)

问题

求解<=a&&<=b&&<=c&&<=d的四元组数量

过程

1.有四元组相同需要先合并(unique)2.对第一维排序3.cdq1,先把左半部分标记为LEFT,右半部分标记为RIGHT,然后对第二维按序归并4.cdq2,对第三维按序归并,第四维用数据结构(如bit)维护,只对左边标记为LEFT的进行修改,对右边标记为RIGHT的进行查询注:有时也可以直接sort,多一个logcdq1中的归并数组最好和cdq2不同,否则在cdq2结束后记得还原为cdq1中的顺序排序一定要彻底,否则会wa

例题

hdu5126立方体加点,立方体数点把加点看作修改操作,数点利用容斥拆成8个询问.修改和查询按照时间有序,是一个四维偏序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 4e5 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int q, c[N], tot, ans[N], id[N];
bool isq[N];
void upd(int x, int v)
{
  for(int i=x; i<=tot; i+=(i&-i)) c[i] += v;
}
int ask(int x)
{
  int ans = 0;
  for(int i=x; i>0; i-=(i&-i)) ans += c[i];
  return ans;
}
struct item
{
  int x, y, z, t, coef;
  bool tag;
}p[N], tmp[N], tmp2[N];
bool cmp(item a, item b)
{
  if(a.x==b.x)
  {
    if(a.y==b.y) return a.z==b.z ? a.t < b.t : a.z < b.z;
    return a.y < b.y;
  }
  return a.x < b.x;
}
void CDQ2(int l, int r)
{
  if(l==r) return;
  int mid = (l+r)>>1;
  CDQ2(l, mid); CDQ2(mid+1, r);
  int i = l, j = mid+1, k = l;
  while(i<=mid&&j<=r)
  {
    if(tmp[i].z<=tmp[j].z)
    {
      if(!tmp[i].tag&&!tmp[i].coef) upd(tmp[i].t, 1);
      tmp2[k++] = tmp[i++];
    }
    else
    {
      if(tmp[j].tag&&tmp[j].coef) ans[tmp[j].t] += ask(tmp[j].t-1)*tmp[j].coef;
      tmp2[k++] = tmp[j++];
    }
  }
  while(i<=mid)
  {
    if(!tmp[i].tag&&!tmp[i].coef) upd(tmp[i].t, 1);
    tmp2[k++] = tmp[i++];
  }
  while(j<=r)
  {
    if(tmp[j].tag&&tmp[j].coef) ans[tmp[j].t] += ask(tmp[j].t-1)*tmp[j].coef;
    tmp2[k++] = tmp[j++];
  }
  for(int i=l; i<=mid; i++) if(!tmp[i].tag&&!tmp[i].coef) upd(tmp[i].t, -1);
  for(int i=l; i<=r; i++) tmp[i] = tmp2[i];
}
void CDQ1(int l, int r)
{
  if(l==r) return;
  int mid = (l+r)>>1;
  CDQ1(l, mid); CDQ1(mid+1, r);
  for(int i=l; i<=mid; i++) p[i].tag = 0;
  for(int i=mid+1; i<=r; i++) p[i].tag = 1;
  int i = l, j = mid+1, k = l;
  while(i<=mid&&j<=r)
  {
    if(p[i].y<=p[j].y) tmp[k++] = p[i++];
    else tmp[k++] = p[j++];
  }
  while(i<=mid) tmp[k++] = p[i++];
  while(j<=r) tmp[k++] = p[j++];
  for(int i=l; i<=r; i++) p[i] = tmp[i];
  CDQ2(l, r);
}
void solve()
{
  scanf("%d", &q);
  tot = 0;
  for(int i=1; i<=q; i++)
  {
    int op; scanf("%d", &op);
    ans[i] = isq[i] = 0;
    if(op==1)
    {
      int x, y, z;
      scanf("%d%d%d", &x, &y, &z);
      p[++tot] = {x, y, z, i, 0};
    }
    else
    {
      int x1, y1, z1, x2, y2, z2;
      scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
      isq[i] = 1;
      p[++tot] = {x2, y2, z2, i, 1};
      p[++tot] = {x1-1, y2, z2, i, -1};
      p[++tot] = {x2, y1-1, z2, i, -1};
      p[++tot] = {x2, y2, z1-1, i, -1};
      p[++tot] = {x1-1, y1-1, z2, i, 1};
      p[++tot] = {x2, y1-1, z1-1, i, 1};
      p[++tot] = {x1-1, y2, z1-1, i, 1};
      p[++tot] = {x1-1, y1-1, z1-1, i, -1};
    }
  }
  sort(p+1, p+tot+1, cmp);
  CDQ1(1, tot);
  for(int i=1; i<=q; i++)
    if(isq[i]) printf("%d\n", ans[i]);
}
int main()
{
  int T; scanf("%d", &T);
  while(T--) solve();
  return 0;
}

p5621四维LIS树状数组维护第四维的dp前缀max,第四维要离散化,同时相同的四元组要合并注意此题要先cdq左半部分,然后统计左对右的答案,再cdq右半部分.而上一题是先cdq左右,最后再统计答案(其实也可以按本题的流程,但本题不可以这样,因为本质是一个dp,必须从左到右,而统计没这个要求).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, m;
int id[N], lsh[N];
ll c[N];
void upd(int x, ll v)
{
  for(int i=x; i<=m; i+=(i&-i)) c[i] = max(c[i], v);
}
void clear(int x)
{
  for(int i=x; i<=m; i+=(i&-i)) c[i] = 0;
}
ll ask(int x)
{
  ll ans = 0;
  for(int i=x; i>0; i-=(i&-i)) ans = max(ans, c[i]);
  return ans;
}
struct item
{
  int a, b, c, d, id;
  bool t;
  ll mx, val;
}p[N], tmp[N];
bool cmp1(item x, item y)
{
  if(x.a==y.a)
  {
    if(x.b==y.b) return x.c==y.c ? x.d < y.d : x.c < y.c;
    return x.b < y.b;
  }
  return x.a < y.a;
}
bool cmp2(item x, item y)
{
    if(x.b==y.b&&x.c==y.c&&x.d==y.d) return x.a < y.a;
  if(x.b==y.b) return x.c==y.c ? x.d < y.d : x.c < y.c;
  return x.b < y.b;
}
bool cmp3(item x, item y)
{
    if(x.c==y.c&&x.d==y.d) return x.a==y.a ? x.b < y.b : x.a < y.a;
  return x.c==y.c ? x.d < y.d : x.c < y.c;
}
void CDQ2(int l, int r)
{
  if(l==r) return;
  int mid = (l+r)>>1;
  CDQ2(l, mid);
  sort(p+l, p+mid+1, cmp3);
  sort(p+mid+1, p+r+1, cmp3);
  int i = l, j = mid+1;
  while(j<=r)
  {
    while(i<=mid && p[i].c<=p[j].c)
    {
      if(!p[i].t) upd(p[i].d, p[i].mx);
      i++;
    }
    if(p[j].t) p[j].mx = max(p[j].mx, ask(p[j].d)+p[j].val);
    j++;
  }
  for(int i=l; i<=mid; i++) if(!p[i].t) clear(p[i].d);
  for(int i=l; i<=r; i++) tmp[id[p[i].id]] = p[i];
  for(int i=l; i<=r; i++) p[i] = tmp[i];
  CDQ2(mid+1, r);
}
void CDQ1(int l, int r)
{
  if(l==r) return;
  int mid = (l+r)>>1;
  CDQ1(l, mid);
  for(int i=l; i<=mid; i++) p[i].t = 0;
  for(int i=mid+1; i<=r; i++) p[i].t = 1;
  sort(p+l, p+r+1, cmp2);
  for(int i=l; i<=r; i++) id[p[i].id] = i;
  CDQ2(l, r);
  for(int i=l; i<=r; i++) tmp[p[i].id] = p[i];
  for(int i=l; i<=r; i++) p[i] = tmp[i];
  CDQ1(mid+1, r);
}
int main()
{
  scanf("%d", &n);
  for(int i=1; i<=n; i++)
  {
    scanf("%d%d%d%d", &p[i].a, &p[i].b, &p[i].c, &p[i].d);
    scanf("%lld", &p[i].val);
    lsh[i] = p[i].d;
  }
  sort(lsh+1, lsh+n+1);
  m = unique(lsh+1, lsh+n+1) - lsh - 1;
  for(int i=1; i<=n; i++)
    p[i].d = lower_bound(lsh+1, lsh+m+1, p[i].d) - lsh;
  int tot = 1;
  sort(p+1, p+n+1, cmp1);
  for(int i=2; i<=n; i++)
  {
    if(p[i].a!=p[i-1].a||p[i].b!=p[i-1].b||p[i].c!=p[i-1].c||p[i].d!=p[i-1].d) p[++tot] = p[i];
    else p[tot].val += max(p[i].val, 0ll);
  }
  n = tot;
  for(int i=1; i<=n; i++)
  {
    p[i].id = i;
    p[i].mx = p[i].val;
  }
  CDQ1(1, n);
  ll ans = 0;
  for(int i=1; i<=n; i++) ans = max(ans, p[i].mx);
  printf("%lld\n", ans);
  return 0;
}