【SDOI 2014】【BZOJ 3533】ベクトルセット
Description
ベクトルセットを維持し、オンラインで以下の操作をサポートします:“A x y(|x|,|y|<=10^8)”:ベクトル(x,y);Q x y l r(|x|,|y|<=10^8,1<=L<=R<=T,ここでTは既に加えられたベクトル個数)は、L番目からR番目に加えられたベクトルとベクトル(x,y)の点積の最大値を尋ねる.コレクションの初期値は空です.
Input
元の入力:inline int decode(int x long long lastans){return x^(lastans&Ox 7 fffffffff);}function decode beginでは、xはプログラムが読み込んだ数であり、lastansは前の最後の質問の答えである.最初の問い合わせの前にlastans=0です.
注意:ベクトル(x,y)と(z,W)の点積はxz+ywと定義されます.
Output
Q操作ごとに、整数を出力して答えを表す.
Sample Input
Sample Output
解釈:復号後の入力は
6 E
HINT
1 < =N < =4×10^5
新しいデータのセット..2015.315
Source
Round 1 Day 2
セグメントツリーは凸包をメンテナンスして3分でもバイナリグループ化してBZOJ上WAにREが表示されることがあることを知っています...
ベクトルセットを維持し、オンラインで以下の操作をサポートします:“A x y(|x|,|y|<=10^8)”:ベクトル(x,y);Q x y l r(|x|,|y|<=10^8,1<=L<=R<=T,ここでTは既に加えられたベクトル個数)は、L番目からR番目に加えられたベクトルとベクトル(x,y)の点積の最大値を尋ねる.コレクションの初期値は空です.
Input
N s， ；
N ， ， 。
s≠'E' ， 。
元の入力:inline int decode(int x long long lastans){return x^(lastans&Ox 7 fffffffff);}function decode beginでは、xはプログラムが読み込んだ数であり、lastansは前の最後の質問の答えである.最初の問い合わせの前にlastans=0です.
注意:ベクトル(x,y)と(z,W)の点積はxz+ywと定義されます.
Output
Q操作ごとに、整数を出力して答えを表す.
Sample Input
6 A
A 3 2
Q 1 5 1 1
A 15 14
A 12 9
Q 12 8 12 15
Q 21 18 19 18
Sample Output
13
17
17
解釈:復号後の入力は
6 E
A 3 2
Q 1 5 1 1
A 2 3
A 1 4
Q 1 5 1 2
Q 4 3 2 3
HINT
1 < =N < =4×10^5
新しいデータのセット..2015.315
Source
Round 1 Day 2
セグメントツリーは凸包をメンテナンスして3分でもバイナリグループ化してBZOJ上WAにREが表示されることがあることを知っています...
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 400010
#define GET (ch>='0'&&ch<='9')
#define LL long long
#define MAXINT 0x7fffffff
#define MAXLL 1ll<<60
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
#define MAXSIZE 50
using namespace std;
int n,cnt,top,top1,top2;
LL lastans;
char Flag,ch;
struct Point
{
int x,y;
friend Point operator -(Point a,Point b) {return (Point){a.x-b.x,a.y-b.y};}
friend LL operator *(Point a,Point b) {return (LL)a.x*b.x+(LL)a.y*b.y;}
friend LL operator ^(Point a,Point b) {return (LL)a.x*b.y-(LL)a.y*b.x;}
}s[MAXN],tmp[MAXN],p,sta1[MAXN<<3],sta2[MAXN<<3];
bool cmp1(Point a,Point b) {return a.x==b.x?a.y>b.y:a.x<b.x;}
bool cmp2(Point a,Point b) {return a.x==b.x?a.y<b.y:a.x<b.x;}
struct seg {int l,r,l1,r1,l2,r2;}tree[MAXN<<2];
void in(int &x)
{
char ch=getchar();x=0;int flag=1;
while (!GET) flag=ch=='-'?-1:1,ch=getchar();
while (GET) x=x*10+ch-'0',ch=getchar();x*=flag;
}
void build(int rt=1,int l=1,int r=n)
{
tree[rt].l=l;tree[rt].r=r;
if (l==r) return;
int mid=(l+r)>>1;build(lchild);build(rchild);
}
LL Dir(Point a,Point b,Point c) {Point A=b-a,B=c-b;return B^A;}//
void insert(int rt)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (R==cnt&&R-L>=MAXSIZE)
{
top=0;
for (int i=L;i<=R;i++) tmp[++top]=s[i];
sort(tmp+1,tmp+top+1,cmp1);sta1[++top1]=tmp[1];tree[rt].l1=top1;
for (int i=2;i<=top;i++)
if (tmp[i].x!=tmp[i-1].x)
{
while (top1>tree[rt].l1&&Dir(sta1[top1-1],sta1[top1],tmp[i])<=0) top1--;
sta1[++top1]=tmp[i];
}
tree[rt].r1=top1;sort(tmp+1,tmp+top+1,cmp2);sta2[++top2]=tmp[1];tree[rt].l2=top2;
for (int i=2;i<=top;i++)
if (tmp[i].x!=tmp[i-1].x)
{
while (top2>tree[rt].l2&&Dir(sta2[top2-1],sta2[top2],tmp[i])>=0) top2--;
sta2[++top2]=tmp[i];
}
tree[rt].r2=top2;
}
if (L==R) return;
if (cnt<=mid) insert(ln);else insert(rn);
}
LL ask1(int l,int r)
{
LL ret=-MAXLL;
while (l<=r)
{
int len=(r-l)/3,mid1=l+len,mid2=r-len;LL dot1=p*sta1[mid1],dot2=p*sta1[mid2];
if (dot1>dot2) r=mid2-1,ret=max(ret,dot1);
else l=mid1+1,ret=max(ret,dot2);
}
return ret;
}
LL ask2(int l,int r)
{
LL ret=-MAXLL;
while (l<=r)
{
int len=(r-l)/3,mid1=l+len,mid2=r-len;LL dot1=p*sta2[mid1],dot2=p*sta2[mid2];
if (dot1>dot2) r=mid2-1,ret=max(ret,dot1);
else l=mid1+1,ret=max(ret,dot2);
}
return ret;
}
LL query(int rt,int l,int r)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;LL ret=-MAXLL;
if (l<=L&&r>=R)
{
if (R-L<MAXSIZE) for (int i=L;i<=R;i++) ret=max(ret,p*s[i]);
else ret=max(ret,p.y>0?ask1(tree[rt].l1,tree[rt].r1):ask2(tree[rt].l2,tree[rt].r2));
return ret;
}
if (r<=mid) return query(ln,l,r);
if (l>mid) return query(rn,l,r);
return max(query(ln,l,mid),query(rn,mid+1,r));
}
void Getch(char &x) {x=getchar();while (x==' '||x=='
'||x=='\r') x=getchar();}
int calc(int x) {if (Flag!='E') x^=(lastans&MAXINT);return x;}
int main()
{
in(n);Getch(Flag);build();int l,r;
while (n--)
{
Getch(ch);
if (ch=='A') in(s[++cnt].x),in(s[cnt].y),s[cnt].x=calc(s[cnt].x),s[cnt].y=calc(s[cnt].y),insert(1);
else in(p.x),in(p.y),in(l),in(r),p.x=calc(p.x),p.y=calc(p.y),l=calc(l),r=calc(r),lastans=query(1,l,r),printf("%lld
",lastans);
}
}