题意简述
维护一个向量集合,支持以下操作:
1. 插入一个向量
。
2. 删除插入的第
个向量。
3. 查询当前集合与
点积的最大值是多少。如果当前是空集输出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 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; } |