首页 > 代码库 > 【COGS2479】 HZOI2016—偏序
【COGS2479】 HZOI2016—偏序
http://cogs.pro/cogs/problem/problem.php?pid=2479 (题目链接)
题意
四维偏序。
Solution
CDQ套CDQ。
细节
第二次分治不能直接按照mid分离两类数了。
代码
// cogs2479#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483600#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=50010;int n,ans,f[maxn],c[maxn];struct data {int x,y,z,id,op;}q[maxn],nq[maxn],p[maxn],np[maxn];bool cmp(data a,data b) {return a.id<b.id;}bool CMP(data a,data b) {return a.y<b.y;}int lowbit(int x) { return x&-x;}void modify(int x,int val) { for (int i=x;i<=n;i+=lowbit(i)) c[i]+=val;}int query(int x) { int res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res;}void solve2(int l,int r) { if (l==r) return; int mid=(l+r)>>1; sort(p+l,p+r+1,CMP); solve2(l,mid);solve2(mid+1,r); for (int i=l,j=mid+1,k=l;i<=mid || j<=r;) { if (j>r || (i<=mid && p[i].id<p[j].id)) { if (p[i].op==0) modify(p[i].z,1); np[k++]=p[i++]; } else { if (p[j].op==1) f[p[j].id]+=query(p[j].z-1); np[k++]=p[j++]; } } for (int i=l;i<=mid;i++) if (p[i].op==0) modify(p[i].z,-1); for (int i=l;i<=r;i++) p[i]=np[i];}void solve(int l,int r) { if (l==r) {ans+=f[q[l].id];return;} int mid=(l+r)>>1,l1=l,l2=mid+1; for (int i=l;i<=r;i++) q[i].x<=mid ? nq[l1++]=q[i] : nq[l2++]=q[i]; for (int i=l;i<=r;i++) q[i]=nq[i]; solve(l,mid); for (int i=l;i<=r;i++) p[i]=q[i],p[i].op=i>mid; sort(p+l,p+r+1,cmp); solve2(l,r); solve(mid+1,r);}int main() { free("partial_order"); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&q[i].x); for (int i=1;i<=n;i++) scanf("%d",&q[i].y); for (int i=1;i<=n;i++) scanf("%d",&q[i].z); for (int i=1;i<=n;i++) q[i].id=i; solve(1,n); printf("%d",ans); fclose(stdin);fclose(stdout); return 0;}
【COGS2479】 HZOI2016—偏序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。