A703求解
2025-01-23 16:02:38
发布于：江苏
1阅读
0回复
0点赞
CSP-S 2022 求解
#include<bits/stdc++.h>
using namespace std;
int n,m,q,x,flag,ST[100005][20][5][2],cnt[5];//1:Lpos 2:Lneg 3:Qpos 4:Qneg 0:min 1:max
void build(){
for(int d=1;d<=4;d++){
for(int i=1;i<=log2(cnt[d]);i++) for(int j=1;j<=cnt[d]-(1<<i)+1;j++) ST[j][i][d][0]=min(ST[j][i-1][d][0],ST[j+(1<<(i-1))][i-1][d][0]);
for(int i=1;i<=log2(cnt[d]);i++) for(int j=1;j<=cnt[d]-(1<<i)+1;j++) ST[j][i][d][1]=max(ST[j][i-1][d][1],ST[j+(1<<(i-1))][i-1][d][1]);
}
}
int query(int l1,int r1,int l2,int r2){
int len1=log2(r1-l1+1);
int len2=log2(r2-l2+1);
if(cnt[1]&&!cnt[2]&&cnt[3]&&!cnt[4]) return max(ST[l1][len1][1][1],ST[r1-(1<<len1)+1][len1][1][1])*min(ST[l2][len2][3][0],ST[r2-(1<<len2)+1][len2][3][0]); //L+Q+
if(cnt[1]&&!cnt[2]&&!cnt[3]&&cnt[4]) return min(ST[l1][len1][1][0],ST[r1-(1<<len1)+1][len1][1][0])*min(ST[l2][len2][4][0],ST[r2-(1<<len2)+1][len2][4][0]); //L+Q-
if(!cnt[1]&&cnt[2]&&cnt[3]&&!cnt[4]) return max(ST[l1][len1][2][1],ST[r1-(1<<len1)+1][len1][2][1])*max(ST[l2][len2][3][1],ST[r2-(1<<len2)+1][len2][3][1]); //L-Q+
if(!cnt[1]&&cnt[2]&&!cnt[3]&&cnt[4]) return min(ST[l1][len1][2][0],ST[r1-(1<<len1)+1][len1][2][0])*max(ST[l2][len2][4][1],ST[r2-(1<<len2)+1][len2][4][1]); //L-Q-
if(cnt[1]&&cnt[2]&&cnt[3]&&!cnt[4]) return max(ST[l1][len1][1][1],ST[r1-(1<<len1)+1][len1][1][1])*min(ST[l2][len2][3][0],ST[r2-(1<<len2)+1][len2][3][0]); //L?Q+
if(cnt[1]&&!cnt[2]&&cnt[3]&&cnt[4]) return min(ST[l1][len1][1][0],ST[r1-(1<<len1)+1][len1][1][0])*min(ST[l2][len2][4][0],ST[r2-(1<<len2)+1][len2][4][0]); //L+Q?
if(!cnt[1]&&cnt[2]&&cnt[3]&&cnt[4]) return max(ST[l1][len1][2][1],ST[r1-(1<<len1)+1][len1][2][1])*max(ST[l2][len2][3][1],ST[r2-(1<<len2)+1][len2][3][1]); //L-Q?
if(cnt[1]&&cnt[2]&&!cnt[3]&&cnt[4]) return min(ST[l1][len1][2][0],ST[r1-(1<<len1)+1][len1][2][0])*max(ST[l2][len2][4][1],ST[r2-(1<<len2)+1][len2][4][1]); //L?Q-
int ans1=min(ST[l1][len1][1][0],ST[r1-(1<<len1)+1][len1][1][0])*min(ST[l2][len2][4][0],ST[r2-(1<<len2)+1][len2][4][0]);
int ans2=max(ST[l1][len1][2][1],ST[r1-(1<<len1)+1][len1][2][1])*max(ST[l2][len2][3][1],ST[r2-(1<<len2)+1][len2][3][1]);
return max(ans1,ans2);//L?Q?
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++){scanf("%d",&x);flag=(x>0)?1:2; ST[++cnt[flag]][0][flag][0]=ST[++cnt[flag]][0][flag][1]=x;}
for(int i=1;i<=m;i++){scanf("%d",&x);flag=(x>0)?3:4; ST[++cnt[flag]][0][flag][0]=ST[++cnt[flag]][0][flag][1]=x;}
build();
while(q--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
printf("%d\n",query(l1,r1,l2,r2));
}
return 0;
}
这里空空如也
有帮助，赞一个