抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

BZOJ3262 陌上花开

发布于：2019年8月4日

首先，以aa为第一关键字排序，bb为第二关键字排序，cc为第三关键字排序，这样从左到右扫过去，发现aia_i一定是递增的，所以只要考虑后面两维即可。

不妨考虑画一个图：

发现只有在蓝色框框里面的才是合法的解（如(bj,cj)(b_j,c_j)，(bk,ck)(b_k,c_k)） 。

Sol1

我们用树套树（线段树套动态开点线段树，又称二维线段树）来维护这个二维前缀和。

第二维用动态开点是因为防爆空间。

但是发现线段树常数太大，会超时，我们可以把第一维的线段树改成树状数组。

注意：数组开大一点。

实现的细节：考虑到可能有多个相同的花，我们统计当前相同的花的个数，等到一个不同的花加入时一起统计，相同的花只能一起统计，如果分开统计，会导致他们的ff值不一样。

时间复杂度为O(nlog⁡2n)O(n \log^2 n)代码如下：

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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int rt[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int val;
    }tree[MAXN*150];
    int tot;
    #define lc tree[i].l
    #define rc tree[i].r
    inline void pushup(int i){
        tree[i].val=tree[lc].val+tree[rc].val;
    }
    void Update(int &i,int pos,int val,int l,int r){
        if (!i) i=++tot;
        if (l==r){
            tree[i].val+=val;
            return ;
        }
        int mid=(l+r)>>1;
        if (pos<=mid) Update(lc,pos,val,l,mid);
        else Update(rc,pos,val,mid+1,r);
        pushup(i);
    }
    int Query(int i,int L,int R,int l,int r){
        if (L<=l&&r<=R){
            return tree[i].val;
        }
        int mid=(l+r)>>1,ans=0;
        if (L<=mid) ans+=Query(lc,L,R,l,mid);
        if (mid<R) ans+=Query(rc,L,R,mid+1,r);
        return ans;
    }
}
using namespace SegmentTree;
struct Flower{
    int a,b,c;
}f[MAXN];
inline bool operator < (const Flower &A,const Flower &B){
    if (A.a!=B.a)  return A.a<B.a;
    else if (A.b!=B.b) return A.b<B.b;
    return A.c<B.c;
}
#define lowbit(x) x&(-x)
int k;
inline void upd(int x,int y,int val){
    for (register int i=x;i<=k;i+=lowbit(i)){
        Update(rt[i],y,val,1,k);
    }
}
inline int qry(int x,int y){
    int ans=0;
    for (register int i=x;i>0;i-=lowbit(i)){
        ans+=Query(rt[i],1,y,1,k);
    }
    return ans;
}
int Ans[MAXN];
int main(){
    int n=read();k=read();
    for (register int i=1;i<=n;++i){
        f[i].a=read(),f[i].b=read(),f[i].c=read();
    }
    sort(f+1,f+1+n);
    int same=1;//副本
    for (register int i=1;i<=n;++i){
        if (f[i+1].a==f[i].a&&f[i+1].b==f[i].b&&f[i+1].c==f[i].c){//注意相同的时候会出锅，所以要统计副本个数
            same++;
        }
        else {//来了一个不同的，大力统计
            upd(f[i].b,f[i].c,same);
            Ans[qry(f[i].b,f[i].c)]+=same;
            same=1;//重置副本为1
        }
    }
    for (register int i=1;i<=n;++i){
        printf("%d\n",Ans[i]);
    }
}

Sol2

刚才我们用的是动态开点线段树，发现动态开点便于理解，但是大材小用了。

观察下面两句：

1
2
Update(rt[i],y,val,1,k);
ans+=Query(rt[i],1,y,1,k);

实现的是什么功能呢？插入一个数，询问比小于等于这个数的数的总数。

这不就是平衡树吗？

在刚才的代码的基础上魔改，得到以下：

（相同的数暴♂力插♂入，我实在是太懒了）

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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int rt[MAXN*150];
namespace FHQTreap{
    struct node{
        int l,r;
        int val,pri,sz;
    }tree[MAXN*150];
    int tot;
    #define lc(i) tree[i].l
    #define rc(i) tree[i].r
    inline void Update(const int &x){
        tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
    }
    inline int New(int v){
        tree[++tot].val=v;
        tree[tot].pri=rand();
        tree[tot].sz=1;
        return tot;
    }
    #define Rson rc(x),y
    #define Lson x,lc(y)
    int Merge(int x,int y){
        if (!x||!y) return x+y;
        if (tree[x].pri<tree[y].pri){
            rc(x)=Merge(Rson),Update(x);
            return x;
        }
        else {
            lc(y)=Merge(Lson),Update(y);
            return y;
        }
    }
    void Split(int i,int k,int &x,int &y){
        if (!i){//叶节点
            x=y=0;
        }
        else {
            if (tree[i].val<=k) x=i,Split(rc(i),k,Rson);
            else y=i,Split(lc(i),k,Lson);
            Update(i);
        }
    }
    inline void Insert(int &rt,int val,int num){
        for (register int i=1;i<=num;++i){//懒。。。
            int x=0,y=0;
            Split(rt,val,x,y);
            rt=Merge(Merge(x,New(val)),y);
        }
    }
    inline int GetRank(int rt,int val){
        int x=0,y=0;
        Split(rt,val,x,y);
        int ans=tree[x].sz;
        rt=Merge(x,y);
        return ans;
    }
}
using namespace FHQTreap;
struct Flower{
    int a,b,c;
}f[MAXN];
inline bool operator < (const Flower &A,const Flower &B){
    if (A.a!=B.a)  return A.a<B.a;
    else if (A.b!=B.b) return A.b<B.b;
    return A.c<B.c;
}
#define lowbit(x) x&(-x)
int k;
inline void upd(int x,int y,int val){
    for (register int i=x;i<=k;i+=lowbit(i)){
        Insert(rt[i],y,val);
    }
}
inline int qry(int x,int y){
    int ans=0;
    for (register int i=x;i>0;i-=lowbit(i)){
        ans+=GetRank(rt[i],y);
    }
    return ans;
}
int Ans[MAXN];
int main(){
    int n=read();k=read();
    for (register int i=1;i<=n;++i){
        f[i].a=read(),f[i].b=read(),f[i].c=read();
    }
    sort(f+1,f+1+n);
    int same=1;//副本
    for (register int i=1;i<=n;++i){
        if (f[i+1].a==f[i].a&&f[i+1].b==f[i].b&&f[i+1].c==f[i].c){//注意相同的时候会出锅，所以要统计副本个数
            same++;
        }
        else {//来了一个不同的，大力统计
            upd(f[i].b,f[i].c,same);
            Ans[qry(f[i].b,f[i].c)]+=same;
            same=1;//重置副本为1
        }
    }
    for (register int i=1;i<=n;++i){
        printf("%d\n",Ans[i]);
    }
}

结果，时间竟然变成3s。

所以，还是建议敲动态开点线段树吧，不仅好写好想，而且常数小。

Sol3

cdq分治，暂时咕咕

相关文章
BZOJ 3648 寝室管理这题其实就是点分治的一个扩展。CF61E Enemy is weakP4556 [Vani有约会]雨天的尾巴P4867 Gty的二逼妹子序列基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/15401cdd.html

更新于：2022年6月14日

题解

树状数组

权值线段树

评论