用kd-tree水过的cdq分治
bzoj2253 纸箱堆叠
求三维严格上升子序列长度
sort 一维，然后上kd-tree就好。。。随机数据kd-tree跑得飞快
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define inf 0x7f7f7f7f
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
typedef double db;
const int MAXN=50005;
int D;
struct node{
int d[2],id;
inline bool operator<(const node&o)const{
return d[D]<o.d[D];
}
}kd[MAXN];
int p[MAXN],ch[MAXN][2],val[MAXN];
int mx[MAXN][2][2],mxv[MAXN];
bool ban[MAXN];
inline void update(int x){
rep(i,0,2){
mx[x][i][0]=ban[x]?inf:kd[x].d[i];
mx[x][i][1]=ban[x]?-inf:kd[x].d[i];
}
mxv[x]=ban[x]?-inf:val[x];
int y;
rep(d,0,2)
if((y=ch[x][d])){
rep(i,0,2){
Max(mx[x][i][1],mx[y][i][1]);
Min(mx[x][i][0],mx[y][i][0]);
}
Max(mxv[x],mxv[y]);
}
}
int build(int l,int r,int d){
if(l>r)return 0;
int x=(l+r)>>1;
D=d,nth_element(kd+l,kd+x,kd+r+1);
ch[x][0]=build(l,x-1,d^1);
ch[x][1]=build(x+1,r,d^1);
rep(i,0,2)p[ch[x][i]]=x;
return update(x),x;
}
int ans,qy[2][2];
inline bool out(int x){
if(!x)return 1;
rep(i,0,2){
if(mx[x][i][1]<qy[i][0])return 1;
if(mx[x][i][0]>qy[i][1])return 1;
}
return 0;
}
inline bool in(int x){
rep(i,0,2){
if(mx[x][i][1]>qy[i][1])return 0;
if(mx[x][i][0]<qy[i][0])return 0;
}
return 1;
}
void query(int x){
if(out(x))return;
if(mxv[x]<=ans)return;
if(in(x)){
ans=mxv[x];
return;
}
if(!ban[x]&&val[x]>ans){
bool flag=1;
rep(i,0,2){
if(kd[x].d[i]<qy[i][0])flag=0;
if(kd[x].d[i]>qy[i][1])flag=0;
}
if(flag)ans=val[x];
}
bool d=mxv[ch[x][1]]>mxv[ch[x][0]];
query(ch[x][d]),query(ch[x][d^1]);
}
int rt,pos[MAXN];
int a,P,n,dp[MAXN];
inline int rand_a(){
static int x=1;
return x=1ll*x*a%P;
}
struct data{
int x,y,z;
inline void scan(){
x=rand_a(),y=rand_a(),z=rand_a();
int tx=max(x,max(y,z));
int tz=min(x,min(y,z));
int ty=1ll*x+y+z-tx-tz;
x=tx,y=ty,z=tz;
}
inline bool operator<(const data&o)const{
return x<o.x;
}
}d[MAXN];
inline void Init(){
Scan(a),Scan(P),Scan(n);
rep(i,1,n+1)d[i].scan();
}
inline void modify(int x,int y){
x=pos[x],ban[x]=0,val[x]=y;
for(int i=x;i;i=p[i])update(i);
}
inline void Solve(){
sort(d+1,d+1+n);
rep(i,1,n+1){
kd[i].d[0]=d[i].y;
kd[i].d[1]=d[i].z;
kd[i].id=i;
ban[i]=1;
}
rt=build(1,n,0);
rep(i,1,n+1)pos[kd[i].id]=i;
int res=1,ans1=1;
rep(i,1,n+1){
if(d[i].x!=d[res].x){
for(;res<i;++res)modify(res,dp[res]);
}
ans=0;
qy[0][0]=0,qy[0][1]=d[i].y-1;
qy[1][0]=0,qy[1][1]=d[i].z-1;
query(rt);
dp[i]=ans+1;
Max(ans1,dp[i]);
}
printf("%d\n",ans1);
}
int main(){
Init(); Solve(); return 0;
}
bzoj3262 陌上花开
每朵花有3个属性，求每朵花优于(3个属性都大于等于)多少朵花。
还是sort 一维，这题数据不随机，kd-tree只能贴线低飞。。。
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define inf 0x7f7f7f7f
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
typedef double db;
const int MAXN=100005;
int D;
struct node{
int d[2],id;
inline bool operator<(const node&o)const{
return d[D]<o.d[D];
}
}kd[MAXN];
int p[MAXN],ch[MAXN][2];
int mx[MAXN][2][2],sum[MAXN];
bool ban[MAXN];
inline void update(int x){
rep(i,0,2){
mx[x][i][0]=ban[x]?inf:kd[x].d[i];
mx[x][i][1]=ban[x]?-inf:kd[x].d[i];
}
sum[x]=ban[x]?0:1;
int y;
rep(d,0,2)
if((y=ch[x][d])){
rep(i,0,2){
Max(mx[x][i][1],mx[y][i][1]);
Min(mx[x][i][0],mx[y][i][0]);
}
sum[x]+=sum[y];
}
}
int build(int l,int r,int d){
if(l>r)return 0;
int x=(l+r)>>1;
D=d,nth_element(kd+l,kd+x,kd+r+1);
ch[x][0]=build(l,x-1,d^1);
ch[x][1]=build(x+1,r,d^1);
rep(i,0,2)p[ch[x][i]]=x;
return update(x),x;
}
int ans,qy[2][2];
inline bool out(int x){
if(!x)return 1;
rep(i,0,2){
if(mx[x][i][1]<qy[i][0])return 1;
if(mx[x][i][0]>qy[i][1])return 1;
}
return 0;
}
inline bool in(int x){
rep(i,0,2){
if(mx[x][i][1]>qy[i][1])return 0;
if(mx[x][i][0]<qy[i][0])return 0;
}
return 1;
}
void query(int x){
if(out(x))return;
if(in(x)){
ans+=sum[x];
return;
}
if(!ban[x]){
bool flag=1;
rep(i,0,2){
if(kd[x].d[i]<qy[i][0])flag=0;
if(kd[x].d[i]>qy[i][1])flag=0;
}
if(flag)++ans;
}
query(ch[x][0]),query(ch[x][1]);
}
int n,k,rt,pos[MAXN];
struct data{
int x,y,z;
inline void scan(){
Scan(x),Scan(y),Scan(z);
}
inline bool operator<(const data&o)const{
if(x!=o.x)return x<o.x;
return y!=o.y?y<o.y:z<o.z;
}
inline bool operator==(const data&o)const{
return x==o.x&&y==o.y&&z==o.z;
}
}d[MAXN];
inline void Init(){
Scan(n),Scan(k);
rep(i,1,n+1)d[i].scan();
}
inline void modify(int x){
x=pos[x],ban[x]=0;
for(int i=x;i;i=p[i])update(i);
}
int cnt[MAXN];
inline void Solve(){
sort(d+1,d+1+n);
rep(i,1,n+1){
kd[i].d[0]=d[i].y;
kd[i].d[1]=d[i].z;
kd[i].id=i;
ban[i]=1;
}
rt=build(1,n,0);
rep(i,1,n+1)pos[kd[i].id]=i;
rep(i,1,n+1){
ans=0;
qy[0][1]=d[i].y;
qy[1][1]=d[i].z;
query(rt);
rep(j,i+1,n+1)
if(d[i]==d[j])++ans;
else break;
++cnt[ans+1];
modify(i);
}
rep(i,1,n+1)printf("%d\n",cnt[i]);
}
int main(){
Init(); Solve(); return 0;
}
评论 (0)
