bzoj 4430: [Nwerc2015] Guessing Camels 낙타 내기(CDQ 분할)

제목 설명

전송문

문제풀이

각 낙타용(x, y,z)은 각각 세 사람이 리스트를 추측하는 순위를 나타낸다.그리고 문제는 3차원 편차가 되어 CDQ에 직접 올라가 치료를 받는다.

코드

#include
#include
#include
#include
#include
#define N 200003
#define LL long long 
using namespace std;
struct data{
    int x,y,z,ans,pd;
}a[N];
int n,m,tr[N],pos[N];
int cmp(data a,data b){
    return a.xx;
}
int cmp1(data a,data b){
    return a.yy;
}
int lowbit(int x){
    return x&(-x);
}
void change(int x,int val)
{
    for (int i=x;i<=n;i+=lowbit(i)) tr[i]+=val;
}
int query(int x)
{
    int ans=0;
    if (!x) return 0;
    for (int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
    return ans;
}
void clear(int x)
{
    for (int i=x;i<=n;i+=lowbit(i)) tr[i]=0;
}
void divide(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)/2;
    for (int i=l;i<=mid;i++) a[i].pd=1;
    for (int i=mid+1;i<=r;i++) a[i].pd=0;
    sort(a+l,a+r+1,cmp1);
    for (int i=l;i<=r;i++)
     if (a[i].pd) change(a[i].z,1);
     else a[i].ans+=query(a[i].z);
    for (int i=l;i<=r;i++) 
     if (a[i].pd) clear(a[i].z);
    sort(a+l,a+r+1,cmp);
    divide(l,mid); divide(mid+1,r);
}
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&pos[i]),a[pos[i]].x=i;
    for (int i=1;i<=n;i++) scanf("%d",&pos[i]),a[pos[i]].y=i;
    for (int i=1;i<=n;i++) scanf("%d",&pos[i]),a[pos[i]].z=i; 
    sort(a+1,a+n+1,cmp);
//  for (int i=1;i<=n;i++) cout<x<<" "<y<<" "<1,n);
LL ans=0;
//  for (int i=1;i<=n;i++) cout<x<<" "<y<<" "<" "<for (int i=1;i<=n;i++) ans+=(LL)a[i].ans;
printf("%lld",ans);
}