rockdu
Description
有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。
Input
第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。
以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性
Output
包含N行，分别表示评级为0…N-1的每级花的数量
Sample Input
10 3 3 3 3 2 3 3 2 3 1 3 1 1 3 1 2 1 3 1 1 1 2 1 2 2 1 3 2 1 2 1
Sample Output
3 1 3 0 1 0 1 0 0 1
因为这段时间一直在写KDtree，突发奇想写了个三维偏序，原地爆炸。
一维排序+方差划分+离线操作，洛谷上会十分华丽的T成60分。但是BZOJ是可以卡线的。
虽然用cdqAC才是正常操作，但KDtree二维+一维排序仍然是一种思路，
KDtree：
#include<cstdio>
#include<algorithm>
#define max(a,b) a>b?a:b
#define abs(a) a>0?a:-a;
#define pow(a) a*a;
using namespace std;
const int maxn=2e6+100;
const int inf=0x3f3f3f3f;
int ans[maxn];
int rid[maxn];
int n;
int read(){
char c;int ret=0;
c=getchar();
while(c>'9' || c<'0')
c=getchar();
while(c>='0' && c<='9')
ret=ret*10+c-'0',c=getchar();
return ret;
}
namespace KD_tree{
struct node{
int ch[2],mn[2],mx[2],pos[3],exist,d,fa,id,sum,rank;
node(){mn[0]=mn[1]=inf;}
void init(){sum=exist=1;for(int i=0;i<2;i++) mn[i]=mx[i]=pos[i];}
}tree[maxn];
int D,cnt,root;
inline bool operator <(const node &a,const node &b){
return a.pos[D]<b.pos[D];
}
inline void push_up(int rt){
tree[rt].sum=tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].exist;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
tree[rt].mn[j]=min(tree[tree[rt].ch[i]].mn[j],tree[rt].mn[j]);
tree[rt].mx[j]=max(tree[tree[rt].ch[i]].mx[j],tree[rt].mx[j]);
}
}
inline long long Variance(int l,int r,bool type){
long long a=0,b=0,n=(r-l+1);
for(int i=l;i<=r;i++){
a+=1LL*pow(tree[i].pos[type]);
b+=1LL*tree[i].pos[type];
}
return a/n-pow(b/n);
}
inline bool judge(int l,int r){
long long _x=0,_y=0;
_x=Variance(l,r,0);
_y=Variance(l,r,1);
return _x<_y;
}
void build(int &rt,int l,int r,int fa){
if(l==r){rt=r;tree[rt].fa=fa;return ;}
int mid=(l+r)/2;D=judge(l,r);
nth_element(tree+l,tree+mid,tree+r+1);
rt=mid;tree[rt].d=D;tree[rt].fa=fa;
if(l<mid) build(tree[rt].ch[0],l,mid-1,rt);
if(r>mid) build(tree[rt].ch[1],mid+1,r,rt);
push_up(rt);
}
inline void insert(int w){
tree[w].init();
while(w) push_up(w),w=tree[w].fa;
}
inline bool in(int * mn,int * mx,node rect){
return mn[0]<=rect.mn[0] && mn[1]<=rect.mn[1] && mx[0]>=rect.mx[0] && mx[1]>=rect.mx[1];
}
inline bool intsect(int * mn,int * mx,node rect){
return (max(mn[0],rect.mn[0])<=min(mx[0],rect.mx[0]))&&(max(mn[1],rect.mn[1])<=min(mx[1],rect.mx[1]));
}
inline bool pos_in(int x,int y,int * mn,int * mx){
return (x<=mx[0] && x>=mn[0] && y<=mx[1] && y>=mn[1]);
}
int query(int rt,int * mn,int * mx){
if(in(mn,mx,tree[rt])) return tree[rt].sum;
if(intsect(mn,mx,tree[rt])){
int ret=0;
if(tree[rt].ch[0]) ret+=query(tree[rt].ch[0],mn,mx);
if(tree[rt].ch[1]) ret+=query(tree[rt].ch[1],mn,mx);
return pos_in(tree[rt].pos[0],tree[rt].pos[1],mn,mx)&&tree[rt].exist?ret+1:ret;
}else return 0;
}
}
inline bool cmp(const KD_tree::node &a,const KD_tree::node &b){
return a.pos[2]==b.pos[2]?(a.pos[0]==b.pos[0]?a.pos[1]<b.pos[1]:a.pos[0]<b.pos[0]):a.pos[2]<b.pos[2];
}
inline bool equ(KD_tree::node a,KD_tree::node b){
for(int i=0;i<3;i++)
if(a.pos[i]!=b.pos[i])
return 0;
return 1;
}
int main(){
using namespace KD_tree;
n=read();read();
for(int i=1;i<=n;i++){
tree[i].pos[2]=read();
tree[i].pos[0]=read();
tree[i].pos[1]=read();
tree[i].id=i;
}
sort(tree+1,tree+n+1,cmp);
for(int i=1;i<=n;i++)
tree[i].rank=i;
build(root,1,n,0);
for(int i=1;i<=n;i++)
rid[tree[i].rank]=i;
for(int i=1;i<=n;i++){
int cnt=1;
while(equ(tree[rid[i]],tree[rid[i+1]])){
insert(rid[i++]);
cnt++;
}
int w=rid[i];
insert(w);
int mn[]={0,0};
int mx[]={tree[w].pos[0],tree[w].pos[1]};
int t=query(root,mn,mx);
ans[t-1]+=cnt;
}
for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
return 0;
} CDQ:
#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct point {
int x, y, z, pos, id, cnt;
}rp[maxn], p[maxn], mg[maxn];
int n, k, a, b, c, ans[maxn], sum[maxn], cnt;
int mcnt, pl, pr;
inline char gc(){
static char buf[5000000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 5000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int & x) {
x = 0;static char c = gc();
while(!isdigit(c)) c = gc();
while(isdigit(c)) x = x * 10 + c - '0', c = gc();
}
void write(int x) {
if(x / 10) write(x / 10);
putchar(x % 10 + '0');
}
bool cmp_xyz(const point &a, const point &b) {
return a.x == b.x ? (a.y == b.y ? (a.z < b.z) : a.y < b.y) : a.x < b.x;
}
inline bool cmp_yzx(const point &a, const point &b) {
return a.y == b.y ? (a.z == b.z ? (a.x < b.x) : a.z < b.z) : a.y < b.y;
}
namespace BIT {
int tree[maxn << 1];
#define lowbit(x) ((x) & (-(x)))
void add(int x, int p) {while(x <= k) tree[x] += p, x += lowbit(x);}
int query(int x) {
int ans = 0;
while(x) ans += tree[x], x -= lowbit(x);
return ans;
}
}
void cdq(int l, int r) {
if(l == r) return;
int mid = l + r >> 1;
cdq(l, mid), cdq(mid + 1, r);
mcnt = 0, pl = l, pr = mid + 1;
while(pl <= mid && pr <= r)
if(cmp_yzx(p[pl], p[pr])) mg[++mcnt] = p[pl++];
else mg[++mcnt] = p[pr++];
while(pl <= mid) mg[++mcnt] = p[pl++];
while(pr <= r) mg[++mcnt] = p[pr++];
for(register int i = 1; i <= mcnt; ++i) p[l + i - 1] = mg[i];
for(register int i = l; i <= r; ++i) {
if(p[i].id <= mid) BIT::add(p[i].z, p[i].cnt);
else ans[p[i].pos] += BIT::query(p[i].z);
}
for(register int i = l; i <= r; ++i)
if(p[i].id <= mid) BIT::add(p[i].z, -p[i].cnt);
}
int main() {
read(n), read(k);
for(register int i = 1; i <= n; ++i) {
read(a), read(b), read(c);
rp[i] = (point) {a, b, c, i, 0, 1};
}
sort(rp + 1, rp + n + 1, cmp_xyz);
for(register int i = 1; i <= n; ++i) {
if(rp[i].x == rp[i - 1].x && rp[i].y == rp[i - 1].y && rp[i].z == rp[i - 1].z) ++p[cnt].cnt;
else p[++cnt] = rp[i], p[cnt].id = cnt;
}
cdq(1, cnt);
for(register int i = 1; i <= cnt; ++i)
sum[ans[p[i].pos] + p[i].cnt - 1] += p[i].cnt;
for(register int i = 0; i < n; ++i)
write(sum[i]), putchar('\n');
return 0;
}
没有帐号? 立即注册