BZOJ 3262 陌上花开

发表于 | 分类于 |

萌新第一次用树套树写三维偏序，来谈一谈心得。

首先根据基本套路，我们通过排序忽略掉第一维对答案的影响。
但是注意要同时按照三维（三关键字）排序。
然后就是用树状数组维护第二维，再套 FHQ Treap 维护第三维。

一交，woc 爆 0？
找了个数据发现是没有考虑重复情况。
于是我把重复的放到一起，乱搞一下就好了。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define ls(p) p->lson
#define rs(p) p->rson
#define lowbit(x) ((x) & -(x))
using namespace std;
const int N = 1e5;
const int K = 2e5;
int n,k;
struct note
{
    int a,b,c,cnt;
    inline bool operator<(const note &o) const
    {
        if(a ^ o.a)
            return a < o.a;
        if(b ^ o.b)
            return b < o.b;
        return c < o.c;
    }
    inline bool operator==(const note &o) const
    {
        return a == o.a && b == o.b && c == o.c;
    }
} a[N + 5],b[N + 5];
struct node
{
    int val,rnd,sz;
    node *lson,*rson;
} *rt[K + 5];
inline node *new_node(int v)
{
    node *ret = new node();
    ret->val = v;
    ret->rnd = rand();
    ret->sz = 1;
    return ret;
}
inline void up(node *p)
{
    p->sz = 1;
    if(ls(p))
        p->sz += ls(p)->sz;
    if(rs(p))
        p->sz += rs(p)->sz;
}
node *merge(node *x,node *y)
{
    if(!x)
        return y;
    if(!y)
        return x;
    if(x->rnd < y->rnd)
    {
        rs(x) = merge(rs(x),y);
        up(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        up(y);
        return y;
    }
}
void split(node *p,int v,node *&x,node *&y)
{
    if(!p)
    {
        x = y = NULL;
        return ;
    }
    if(p->val <= v)
        x = p,split(rs(p),v,rs(p),y);
    else
        y = p,split(ls(p),v,x,ls(p));
    up(p);
}
void update(int x,int y)
{
    node *a,*b;
    for(;x <= k;x += lowbit(x))
    {
        split(rt[x],y,a,b);
        rt[x] = merge(merge(a,new_node(y)),b);
    }
}
int query(int x,int y)
{
    int ret = 0;
    node *a,*b;
    for(;x;x -= lowbit(x))
    {
        split(rt[x],y,a,b);
        if(a)
            ret += a->sz;
        rt[x] = merge(a,b);
    }
    return ret;
}
int ans[N + 5];
int main()
{
    srand(19260817);
    scanf("%d%d",&n,&k);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d",&b[i].a,&b[i].b,&b[i].c),b[i].cnt = 1;
    sort(b + 1,b + n + 1);
    a[1] = b[1];
    for(register int i = 2,j = 1;i <= n;++i)
        if(b[i] == b[i - 1])
            ++a[j].cnt;
        else
            a[++j] = b[i];
    for(register int i = 1;i <= n;++i)
    {
        ans[query(a[i].b,a[i].c) + a[i].cnt - 1] += a[i].cnt;
        for(register int j = 1;j <= a[i].cnt;++j)
            update(a[i].b,a[i].c);
    }
    for(register int i = 0;i < n;++i)
        printf("%d\n",ans[i]);
}

Gitalking ...