AC. 梦想

frank_c1

[BZOJ 4311] 向量

发布于2017年01月22日 | 暂无评论 | 1,617阅读 | 分治

题意简述

维护一个向量集合，支持以下操作：

1. 插入一个向量(x,y)。

2. 删除插入的第i个向量。

3. 查询当前集合与(x,y)点积的最大值是多少。如果当前是空集输出0。

1 \le n \le 200000, 1 \le x,y \le 10^6

算法讨论

考虑每一个向量，如果在时间轴上看，存在时间都对应一段区间。

对时间分治，运用线段树的思想把向量定位到O(\log n)个结点上，与此同时将询问下传更新答案即可。

时间复杂度O(n \log n)。

BZOJ4311
C++
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <bitset>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i=(a);i<=(b);i++)
#define PER(i,a,b) for(int i=(a);i>=(b);i--)
#define RVC(i,S) for(int i=0;i<(S).size();i++)
#define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
      
template<class T> inline
void read(T& num) {
    bool start=false,neg=false;
    char c;
    num=0;
    while((c=getchar())!=EOF) {
        if(c=='-') start=neg=true;
        else if(c>='0' && c<='9') {
            start=true;
            num=num*10+c-'0';
        } else if(start) break;
    }
    if(neg) num=-num;
}
/*============ Header Template ============*/
const int maxn=(int)(5e5)+5;
struct node {
    int x,y;
    node(int a=0,int b=0):x(a),y(b) {}
};
inline bool operator < (node a,node b) {
    return a.x!=b.x?a.x<b.x:a.y<b.y;
}
inline node operator + (node a,node b) {
    return node(a.x+b.x,a.y+b.y);
}
inline node operator - (node a,node b) {
    return node(a.x-b.x,a.y-b.y);
}
inline LL _dot(node a,node b) {
    return 1LL*a.x*b.x+1LL*a.y*b.y;
}
inline LL _cross(node a,node b) {
    return 1LL*a.x*b.y-1LL*a.y*b.x;
}
inline LL cross(node a,node b,node c) {
    return _cross(b-a,c-a);
}
struct mnode {
    node c;
    int l,r;
};
struct qnode {
    int x,y,ps,id;
};
LL res[maxn];
node pt[maxn],ch[maxn];
vector<mnode> p[maxn<<2];
vector<qnode> q[maxn<<2];
int qt,tot;
inline void calcAll() {
    sort(pt+1,pt+tot+1);
    int tmp=0;
    REP(i,1,tot) {
        while(tmp>1 && cross(ch[tmp-1],ch[tmp],pt[i])>=0) tmp--;ch[++tmp]=pt[i];
    } tot=tmp;
}
inline LL calc(node a) {
    int l=1,r=tot;LL res=0;
    while(r-l>3) {
        int li=(l+l+r)/3,ri=(l+r+r)/3;
        LL ai=_dot(a,ch[li]),bi=_dot(a,ch[ri]);
        res=max(res,max(ai,bi));
        if(ai<bi) l=li; else r=ri;
    } REP(i,l,r) res=max(res,_dot(a,ch[i]));
    return res;
}
void solve(int x,int l,int r) {
    if(q[x].empty()) return;
    int mid=(l+r)>>1;tot=0;
    for(int i=0;i<p[x].size();i++) {
        mnode w=p[x][i];
        if(w.l<=l && r<=w.r) {
            pt[++tot]=w.c;
        } else {
            if(w.l<=mid) p[x<<1].push_back(w);
            if(mid<w.r) p[x<<1|1].push_back(w);
        }
    } p[x].clear();calcAll();
    for(int i=0;i<q[x].size();i++) {
        qnode w=q[x][i];
        res[w.id]=max(res[w.id],calc(node(w.x,w.y)));
        if(w.ps<=mid) q[x<<1].push_back(w);
        else q[x<<1|1].push_back(w);
    } q[x].clear();
    if(l==r) return;
    solve(x<<1,l,mid);solve(x<<1|1,mid+1,r);
}
int main() {
    int n;
    read(n);
    REP(i,1,n) {
        int opt;
        read(opt);
        if(opt==1) {
            mnode tmp;
            read(tmp.c.x);read(tmp.c.y);tmp.l=i;tmp.r=n;p[1].push_back(tmp);
        } else if(opt==2) {
            int x;
            read(x);--x;p[1][x].r=i-1;
        } else if(opt==3) {
            ++qt;qnode tmp;
            read(tmp.x);read(tmp.y);tmp.ps=i;tmp.id=qt;q[1].push_back(tmp);
        }
    }
    solve(1,1,n);
    REP(i,1,qt) printf("%lld\n",res[i]);
    return 0;
}

快速访问

    分类目录：

    文章归档：

随便看看

标签

Copyright © 2016 AC. 梦想 版权所有 | Powered By WordPress | Theme By YeLook