暴力求调,nlog2n过不了
查看原帖
暴力求调,nlog2n过不了
304613
liuhaodong886楼主2024/11/11 14:51
#include<bits/stdc++.h>
using namespace std;
#define int long long
char *p1,*p2;
char buf[1<<16];
inline char gc(){
    if(p1==p2)
        p2=(p1=buf)+fread(buf,1,1<<16,stdin);
    return (p1==p2)?EOF:*p1++;
}
inline int read(){
	register int x=0,w=1;
	register char ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			w=-1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9') {
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc();
	}
	return x*w;
}
inline void write(int x) {
	register int sta[25];
	register int top=0;
	if(x<0){
		putchar('-');
		x=-x;
	}
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
  	while(top)
		putchar(sta[--top]+48);
}
const int N=5e5 + 5;
struct node{
    int a,b,c,num; 
}e[N];
int n,a[N],b[N],c[N],tree[N*4],ans,sum[N];
bool cmp1(node s1,node s2){
    return s1.a<s2.a;
}
bool cmp2(node s1,node s2){
    return s1.b<s2.b;
}
int lowbit(int x){
    return x&(-x);
}
void upd(int x,int op){
    for(;x<=n;x+=lowbit(x)){
        tree[x]+=op;
    }
}
int query(int x){
    int ret=0;
    for(;x;x-=lowbit(x)){
        ret+=tree[x];
    }
    return ret;
}
void cdq(int l,int r){
    if(l==r){
        return ;
    }
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    sort(e+l,e+mid+1,cmp2);
    sort(e+mid+1,e+r+1,cmp2);
    int i=l,j=mid+1;
    for(;j<=r;++j){
        while(i<=mid&&e[i].b<=e[j].b){
            upd(e[i].c,1);
            i++;
        }
        sum[e[j].a]+=query(e[j].c);
    }
    for(int s=l;s<i;++s){
        upd(e[s].c,-1);
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        int x;
        x=read();
    }
    for(int i=1;i<=n;++i){
        a[i]=read();
        e[a[i]].a=i;
    }
    for(int i=1;i<=n;++i){
        b[i]=read();
        e[b[i]].b=i;
    }
    for(int i=1;i<=n;++i){
        c[i]=read();
        e[c[i]].c=i;
    }
    sort(e+1,e+n+1,cmp1);
    cdq(1,n);
    for(int i=1;i<=n;++i){
        ans+=sum[i];
    }
    write(ans);
    putchar('\n');
    return 0;
}
2024/11/11 14:51
加载中...