题目链接
题意
求三元组的严格上升子序列
思路
先考虑暴力(dp)一下
for(int i = 1;i <= n;++i) for(int j = 1;j < i;++j) if(x[i] > x[j] && y[i] > y[j] && z[i] > z[j]) f[i] = max(f[i],f[j] + 1)
考虑用(cdq)分治优化这个(dp)。
大体思路是,先按照第一维排序,保证第一维是严格上升的。然后(cdq)一下第二维。树状数组维护第三维(需要先离散化)。这里用到的是树状数组维护前缀最大值。
有两个(bug)调了很久。
bug1
直接套用了三维偏序的板子。其实这个题在(cdq)的时候是不能像这样的
void cdq(int l,int r) { if(r <= l) return; cdq(l,mid),cdq(mid + 1,r); //…… }
因为在(cdq)右边之前,必须保证右边已经从左边获取过答案了。这就是求(lis)与求三维偏序不同的地方。
正确操作应该是
void cdq(int l,int r){ if(r <= l) return; cdq(l,mid); //…… cdq(mid + 1,r) }
其实这个(bug)挺(low)的,感觉自己智障了2333
bug2
因为题目中说必须是严格递增的。所以(mid)的位置就不能直接取中间了。
需要找到一个(x[mid])与(x[mid + 1])不同的位置。
代码
/* * @author: wxyww * @date: 2019-02-15 10:45:05 * @last modified time: 2019-02-16 15:29:12 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 300000 + 10; map<int,int>ma; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } int ls[n],tree[n]; struct node { int x[10],ans; }a[n]; ll a,p,n; int js; void clear(int pos) { while(pos <= js) { tree[pos] = 0; pos += pos & -pos; } } void update(int pos,int x) { while(pos <= js) { tree[pos] = max(x,tree[pos]); pos += pos & -pos; } } int query(int pos) { int ret = 0; while(pos) { ret = max(ret,tree[pos]); pos -= pos & -pos; } return ret; } node tmp[n]; bool cmp(node x,node y) { if(x.x[1] != y.x[1]) return x.x[1] < y.x[1]; if(x.x[2] != y.x[2]) return x.x[2] < y.x[2]; return x.x[3] < y.x[3]; } bool cmy(node x,node y) { if(x.x[2] != y.x[2]) return x.x[2] < y.x[2]; return x.x[3] < y.x[3]; } void cdq(int l,int r) { if(r <= l) return; //保证右边第一维严格大于左边 sort(a + l,a + r + 1,cmp); int mid = (l + r) >> 1; int tt = 1e9; for(int i = l;i < r;++i) if(a[i].x[1] != a[i + 1].x[1] && abs(mid - i) < abs(mid - tt)) tt = i; if(tt == 1e9) return; mid = tt; //保证两边第二维分别有序 cdq(l,mid); sort(a + l,a + mid + 1,cmy); sort(a + mid + 1,a + r + 1,cmy); int l = l,r = mid + 1,now = l; while(l <= mid && r <= r) { if(a[l].x[2] <= a[r].x[2]) { update(a[l].x[3],a[l].ans); ++l; } else a[r].ans = max(a[r].ans,query(a[r].x[3] - 1) + 1),++r; } while(r <= r) a[r].ans = max(a[r].ans,query(a[r].x[3] - 1) + 1),++r; for(int i = l;i <= l;++i) clear(a[i].x[3]); cdq(mid + 1,r); } int main() { a = read(),p = read(),n = read(); ll now = 1; int tot = 0; for(int i = 1;i <= n;++i) for(int j = 1;j <= 3;++j) ls[++tot] = a[i].x[j] = now = now * a % p,a[i].ans = 1; sort(ls + 1,ls + tot + 1); ma[ls[1]] = ++js; for(int i = 2;i <= tot;++i) if(ls[i] != ls[i - 1]) ma[ls[i]] = ++js; for(int i = 1;i <= n;++i) { for(int j = 1;j <= 3;++j) a[i].x[j] = ma[a[i].x[j]]; sort(a[i].x + 1,a[i].x + 4); } cdq(1,n); int ans = 0; for(int i = 1;i <= n;++i) ans = max(ans,a[i].ans); cout<<ans; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605184.html