[BZOJ 4311] 向量

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

题意简述

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

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)$ 。

#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;
}

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;

}

AC. 梦想

[BZOJ 4311] 向量

题意简述

算法讨论

快速访问

随便看看

友情链接

标签