UVALive - 6667 Longest Chain CDQ3维问题

题意：现在有一个点堆，一开始先给你m个点，然后再用题目中的rand函数生成剩下的n个点，问在这个点堆中可以找到的最长严格递增序列的长度是多少。

题解：

很常见的一个3维CDQ。

先按照z轴 sort 一遍，然后对于当前的序列去cdq分治。对于CDQ的每一层来说，都是用左边的点的值去更新右边点的值，对于每一层来说，我们按照x轴sort， sort的时候注意，当同x的时候，一定是右边的询问点要在左边的修改点前面，不然就不能保证前面的都是合法点，对于每一个添加点来说，我们在其y轴对应的位置更新他的长度值，对于每一个询问点来说，我们在查询其y轴对应的位置的下面的地方去询问最长值。

但是题目中要求的是严格递增序列。

我们发现，会有中间的那一部分存在同z值的情况导致，中间偏左的点不能去更新中间偏右的点，但是我们可以发现，这个情况只会出现一个位置，对于每一次分治来说，那么我们开2个树状数组，去维护这个东西，一个梳妆数组存下左边的所有的更新点的值，另一个梳妆数组维护除去前面中间偏左不能维护中间偏右的那些点以外的值。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

 #define LL long long

 #define ULL unsigned LL

 #define fi first

 #define se second

 #define pb push_back

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 #define lch(x) tr[x].son[0]

 #define rch(x) tr[x].son[1]

 #define max3(a,b,c) max(a,max(b,c))

 #define min3(a,b,c) min(a,min(b,c))

 typedef pair<int,int> pll;

 const int inf = 0x3f3f3f3f;

 const LL INF = 0x3f3f3f3f3f3f3f3f;

 const LL mod =  (int)1e9+;

 const int N = 3e5 + ;

 int ans[N];

 int a, b, C = ~(<<), M = (<<)-;

 int r(){

     a =  * (a & M) + (a >> );

     b =  * (b & M) + (b >> );

     return (C&((a<<)+b)) % ;

 }

 struct Node{

     int id, x, y, z;

 }q[N], tmp[N];

 bool cmp1(Node & n1, Node & n2){

     return n1.z < n2.z;

 }

 bool cmp2(Node & n1, Node & n2){

     if(n1.x != n2.x) return n1.x < n2.x;

     return n1.id > n2.id;

 }

 int yyy[N];

 int tree[][N];

 void Add(int x, int val, int op){

     for(int i = x; i < N; i+=i&(-i))

         tree[op][i] = max(tree[op][i], val);

     return ;

 }

 int query(int x, int op){

     int ret = ;

     for(int i = x; i > ; i -= i&(-i))

         ret = max(tree[op][i], ret);

     return ret;

 }

 void Clear(int x, int op){

     for(int i = x; i < N; i+=i&(-i))

         tree[op][i] = ;

     return ;

 }

 void cdq(int l,int r){

     if(l == r) {

         ans[l] = max(ans[l], );

         return ;

     }

     int m = l+r >> ;

     cdq(l, m);

     for(int i = l; i <= r; i++)

         tmp[i] = q[i];

     int midz = q[m+].z;

     sort(tmp+l, tmp+r+, cmp2);

     for(int i = l; i <= r; i++){

         if(tmp[i].id <= m){

             Add(tmp[i].y,ans[tmp[i].id],);

             if(tmp[i].z != midz) Add(tmp[i].y,ans[tmp[i].id],);

         }

         else{

             int val;

             if(tmp[i].z != midz) val = query(tmp[i].y-, );

             else val = query(tmp[i].y-,);

             ans[tmp[i].id] = max(ans[tmp[i].id], val+);

         }

     }

     for(int i = l; i <= r; i++){

         if(tmp[i].id <= m){

             Clear(tmp[i].y, );

             if(tmp[i].z != midz) Clear(tmp[i].y,);

         }

     }

     cdq(m+, r);

 }

 int main(){

     int m, n, A, B;

     while(~scanf("%d%d%d%d", &n, &m, &A, &B) && n+m+A+B){

         a = A, b = B;

         for(int i = ; i <= n; i++){

             scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].z);

             yyy[i] = q[i].y;

         }

         for(int i = n+; i <= n+m; i++){

             q[i].x = r(); q[i].y = r(); q[i].z = r();

             yyy[i] = q[i].y;

         }

         sort(yyy+, yyy++n+m);

         sort(q+, q++n+m, cmp1);

         int ysz = unique(yyy+,yyy++n+m) - yyy - ;

         for(int i = ; i <= n+m; i++){

             q[i].id = i;

             q[i].y = lower_bound(yyy+,yyy++ysz,q[i].y) - yyy;

             ans[i] = ;

         }

         cdq(, n+m);

         int fans = ;

         for(int i = ; i <= n+m; i++)

             fans = max(fans, ans[i]);

         printf("%d\n", fans);

     }

     return ;

 }

巴特西

UVALive - 6667 Longest Chain CDQ3维问题

最新文章

热门文章