[线段树] UOJ119. 【UR #8】决战圆锥曲线

思路比较好。

若有两点 \((x_1,y_1), (x_2,y_2)\) ,\(x_1\le x_2\) \(y_1 \le y_2\) ,则 \((x1,y1)\) 显然是没用的。

有这样一个结论,随机的一个数列,跑个单调栈,最后栈长度的期望是 \(O(\log n)\) 的。

也就是说,关键点个数是 \(O(\log n)\) 级别。

然后就好做了,线段树维护区间可能的最大值,即\(f(R,\max_{[L,R]}y)\)

先做右边,再左边。如果一个区间不可能更新答案,就不下去。复杂度是有保证的两个 \(log\)

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
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^'0'), ch=gc();
return res*ff;
}
typedef long long LL;
const int maxn=100005;
int n,m,a[maxn];
int N_seg,Min[maxn*2],Max[maxn*2],rev[maxn*2],ch[maxn*2][2];
int newnode(){
N_seg++; ch[N_seg][0]=ch[N_seg][1]=0;
return N_seg;
}
int Rev(int p){
Min[p]=100000-Min[p]; Max[p]=100000-Max[p];
swap(Min[p],Max[p]);
rev[p]^=1;
}
void pushdown(int p){
if(!rev[p]) return;
Rev(ch[p][0]); Rev(ch[p][1]); rev[p]=0;
}
void maintain(int p){
Min[p]=min(Min[ch[p][0]],Min[ch[p][1]]);
Max[p]=max(Max[ch[p][0]],Max[ch[p][1]]);
}
int Build(int L,int R){
int p=newnode();
if(L==R){ Min[p]=Max[p]=a[L]; return p; }
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
maintain(p); return p;
}
void Update_p(int p,int L,int R,int pos,int val){
if(pos<L||R<pos) return;
if(L==R){ Min[p]=Max[p]=val; return; }
int mid=(L+R)>>1; pushdown(p);
Update_p(ch[p][0],L,mid,pos,val); Update_p(ch[p][1],mid+1,R,pos,val);
maintain(p);
}
void Update_r(int p,int L,int R,int qL,int qR){
if(qR<L||R<qL) return;
if(qL<=L&&R<=qR){ Rev(p); return; }
int mid=(L+R)>>1; pushdown(p);
Update_r(ch[p][0],L,mid,qL,qR); Update_r(ch[p][1],mid+1,R,qL,qR);
maintain(p);
}
LL ans,_A,_B,_C;
LL F(LL x,LL y){
return _A*x+_B*y+_C*x*y;
}
void Query(int p,int L,int R,int qL,int qR){
if(qR<L||R<qL) return;
if(F(R,Max[p])<=ans) return;
if(L==R){ ans=max(ans,F(L,Max[p])); return; }
int mid=(L+R)>>1; pushdown(p);
Query(ch[p][1],mid+1,R,qL,qR); Query(ch[p][0],L,mid,qL,qR);
}
int _X0;
int getrdm(){
_X0=((LL)100000005*_X0+20150609)%998244353;
return _X0/100;
}
int main(){
n=getint(); m=getint(); _X0=getint();
for(int i=1;i<=n;i++) a[i]=getrdm()%100001;
Build(1,n);
while(m--){
char ch=gc(); while(!('A'<=ch&&ch<='Z')) ch=gc();
if(ch=='C'){
int p=getrdm()%n+1, y=getrdm()%100001;
Update_p(1,1,n,p,y);
}
else if(ch=='R'){
int L=getrdm()%n+1,R=getrdm()%n+1; if(L>R) swap(L,R);
Update_r(1,1,n,L,R);
} else{
_A=getint(); _B=getint(); _C=getint();
int L=getrdm()%n+1,R=getrdm()%n+1; if(L>R) swap(L,R);
ans=0; Query(1,1,n,L,R);
printf("%lld\n",ans);
}
}
return 0;
}