~~如果你用线段树我应该会帮你~~
~~还有你的压行~~
by FuncoF9 @ 2023-08-04 17:16:28
@[aaaadou](https://www.luogu.com.cn/user/550935) 那你帮我看看行吗
by lsx1234 @ 2023-08-04 17:17:54
@[aaaadou](https://www.luogu.com.cn/user/550935)
```
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q,a[100005],b[100005];
struct node{
int max_positive,max_negative,minp,minn;
}treea[100005],treeb[100005];
node ask(int x,int lx,int rx,int l,int r,node tree[]){
if(lx>=l && rx<=r){
return tree[x];
}
int mid=(lx+rx)>>1;
if(r<=mid){
return ask(x<<1,lx,mid,l,r,tree);
}
if(l>=mid){
return ask(x<<1+1,mid+1,rx,l,r,tree);
}
node tmpl=ask(x<<1,lx,mid,l,r,tree);
node tmpr=ask(x<<1|1,mid+1,rx,l,r,tree);
node tmp;
tmp.max_positive=max(tmpl.max_positive,tmpr.max_positive);
if(tmpl.max_negative>=0){
tmp.max_negative=tmpr.max_negative;
}else if(tmpr.max_negative>=0){
tmp.max_negative=tmpl.max_negative;
}else{
tmp.max_negative=max(tmpl.max_negative,tmpr.max_negative);
}
if(tmpl.minp<0){
tmp.minp=tmpr.minp;
}
else if(tmpr.minp<0){
tmp.minp=tmpl.minp;
}
else{
tmp.minp=min(tmpl.minp,tmpr.minp);
}
tmp.minn=min(tmpl.minn,tmpr.minn);
return tmp;
}
void push(int x,node tree[]){
tree[x].max_positive=max(tree[x<<1].max_positive,tree[x<<1|1].max_positive);
if(tree[x<<1].max_positive>=0){
tree[x].max_negative=tree[x<<1|1].max_negative;
}else if(tree[x<<1+1].max_negative>=0){
tree[x].max_negative=tree[x<<1].max_negative;
}else{
tree[x].max_negative=max(tree[x<<1].max_negative,tree[x<<1|1].max_negative);
}
if(tree[x<<1].minp<0){
tree[x].minp=tree[x<<1|1].minp;
}else if(tree[x<<1|1].minp<0){
tree[x].minp=tree[x<<1].minp;
}else{
tree[x].minp=min(tree[x<<1].minp,tree[x<<1|1].minp);
}
tree[x].minn=min(tree[x<<1].minn,tree[x<<1|1].minn);
}
void build(int x,int l,int r,int c[],node tree[]){//建树
if(l==r){
if(c[l]>=0){
tree[x].max_positive=tree[x].minn=c[l];
}
else{
tree[x].max_negative=tree[x].minn=c[l];
tree[x].max_positive=tree[x].minp=-1;
}
}
else{
int mid=(l+r)>>1;
build(x<<1,l,mid,c,tree);
build(x<<1|1,mid+1,r,c,tree);
push(x,tree);
}
return ;
}
int main(){
cin>>n>>m>>q;
for(int i=1;i<=n;++i){
cin>>a[i];
}
for(int i=1;i<=m;++i){
cin>>b[i];
}
build(1,1,n,a,treea);
build(1,1,m,b,treeb);
for(int i=1;i<=q;++i){
int l1,r1,l2,r2,ans;
cin>>l1>>r1>>l2>>r2;
node tmpa=ask(1,1,n,l1,r1,treea);
int mpa=tmpa.max_positive,mna=tmpa.max_negative,ipa=tmpa.minp,ina=tmpa.minn;
node tmpb=ask(1,1,m,l1,r1,treeb);
int mpb=tmpb.max_positive,mnb=tmpb.max_negative,ipb=tmpb.minp,inb=tmpb.minn;
int sua=0,sub=0;
if(inb>=0) {
if(mpa>=0){
sua=mpa;
}
else{
sua=mna;
}
}
else{
if(mnb<0){
if(ina<0){
sua=ina;
}
else{
sua=ipa;
}
}
else{
if(mpa<0){
sua=mna;
}
else if(mna>=0){
sua=mpa;
}
else if(inb*ipa>mnb*mna){
sua=ina;
}
else{
sua=mna;
}
}
}
if(sua>=0){
if(inb<0){
sub=inb;
}
else{
sub=inb;
}
}
else{
if(mnb>=0){
sub=mnb;
}
else{
sub=mnb;
}
}
cout<<sua*sub<<endl;
}
return 0;
}
```
by lsx1234 @ 2023-08-04 17:18:41
by ACPC @ 2023-08-04 17:19:04
这么强，都用线段树
by ACPC @ 2023-08-04 17:20:12
@[A_Passing_Creeper](/user/540363)
## Code:
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
char ch=getchar();int x=0, f=1;
while(!isdigit(ch)) f=(ch=='-')?-1:f, ch=getchar();
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0', ch=getchar();
return x*f;
}
const int N=1e5+5;
int n, m, q, p[2][N];
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)
struct node{
int Mxz, Mnz;
int Mxf, Mnf;
int type(){
if(Mxf==0&&Mnf==0) return 1;
if(Mxz==0&&Mnz==0) return 3;
return 2;
}
void print(){
printf("type %d : +(%d %d), -(%d %d)\n", type(), Mxz, Mnz, Mxf, Mnf);
}
}tr[2][N*4];
node init(int x){return (node){max(0, x), max(0, x), min(0, x), min(0, x)};}
int MN(int x, int y){
if(!x&&!y) return 0;
if(x&&y) return min(x, y);
return x?x:y;
}
int MX(int x, int y){
if(!x&&!y) return 0;
if(x&&y) return max(x, y);
return x?x:y;
}
node operator + (node L, node R){
node res;
res.Mxz=max(L.Mxz, R.Mxz);
res.Mnz=MN(L.Mnz, R.Mnz);
res.Mxf=MX(L.Mxf, R.Mxf);
res.Mnf=min(L.Mnf, R.Mnf);
return res;
}
void build(int k, int l, int r, int op){
if(l==r) return (void)(tr[op][k]=init(p[op][l&r]));
build(ls, l, mid, op), build(rs, mid+1, r, op);
tr[op][k]=tr[op][ls]+tr[op][rs];
// printf("for tr[%d] range [%d %d]\n", op, l, r);tr[op][k].print();
}
node query(int k, int l, int r, int x, int y, int op){
if(x>r||y<l) return init(0);
if(x<=l&&r<=y) return tr[op][k];
return query(ls, l, mid, x, y, op)+query(rs, mid+1, r, x, y, op);
}
#undef ls
#undef rs
#undef mid
#define lowbit(x) ((x)&(-x))
int bit[2][N];
void add(int x, int up, int op, int v){for(; x<=up; x+=lowbit(x)) bit[op][x]+=v;}
int query(int x, int op){int res=0;for(; x; x-=lowbit(x)) res+=bit[op][x];return res;}
#undef lowbit
signed main(){
n=read(), m=read(), q=read();
for(int i=1; i<=n; ++i) p[0][i]=read(), add(i, n, 0, (p[0][i]==0));
for(int i=1; i<=m; ++i) p[1][i]=read(), add(i, n, 1, (p[1][i]==0));
build(1, 1, n, 0), build(1, 1, m, 1);
for(int i=1; i<=q; ++i){
int l_1=read(), r_1=read(), l_2=read(), r_2=read();
node A=query(1, 1, n, l_1, r_1, 0);
node B=query(1, 1, m, l_2, r_2, 1);
ll ans;//A.print(), B.print();
if(A.type()==1){
if(B.type()==1) ans=1ll*A.Mxz*B.Mnz;
if(B.type()==2) ans=1ll*A.Mnz*B.Mnf;
if(B.type()==3) ans=1ll*A.Mnz*B.Mnf;
}
if(A.type()==2){
if(B.type()==1) ans=1ll*A.Mxz*B.Mnz;
if(B.type()==2) ans=max(1ll*A.Mnz*B.Mnf, 1ll*A.Mxf*B.Mxz);
if(B.type()==3) ans=1ll*A.Mnf*B.Mxf;
}
if(A.type()==3){
if(B.type()==1) ans=1ll*A.Mxf*B.Mxz;
if(B.type()==2) ans=1ll*A.Mxf*B.Mxz;
if(B.type()==3) ans=1ll*A.Mnf*B.Mxf;
}
if(query(r_1, 0)-query(l_1-1, 0)) ans=max(ans, 0ll);
if(query(r_2, 1)-query(l_2-1, 1)) ans=min(ans, 0ll);
printf("%lld\n", ans);
}
return 0;
}
```
by 2012GFKKKZ @ 2023-08-04 17:22:59
@[fendigao](/user/1037866) 可是我不想要线段树啊
by ACPC @ 2023-08-04 17:23:56
不如这个：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxlogn=17,maxn=100000,SIZE[20]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,37268,65536,131072,262144,524288},maxq=100000;
const double ERR=1e-7;
ll st[11][maxlogn+5][maxn+5];
ll n,m,a[maxn+9],b[maxn+9],top1,top2,q,left1[maxq+1],right1[maxq+1],left2[maxq+1],right2[maxq+1];
string SSSS[9]={"","amax","bmax","amin","bmin","+amin","+bmin","-amax","-bmax"};
void first(){
for(int i=1;i<=n;i++) st[1][1][i]=a[i];
for(int i=2;i<=top1;i++)
for(int j=1;j<=n-SIZE[i-1]+1;j++) st[1][i][j]=max(st[1][i-1][j],st[1][i-1][j+SIZE[i-2]]);
}
void second(){
for(int i=1;i<=m;i++) st[2][1][i]=b[i];
for(int i=2;i<=top2;i++)
for(int j=1;j<=m-SIZE[i-1]+1;j++) st[2][i][j]=max(st[2][i-1][j],st[2][i-1][j+SIZE[i-2]]);
}
void third(){
for(int i=1;i<=n;i++) st[3][1][i]=a[i];
for(int i=2;i<=top1;i++)
for(int j=1;j<=n-SIZE[i-1]+1;j++) st[3][i][j]=min(st[3][i-1][j],st[3][i-1][j+SIZE[i-2]]);
}
void fourth(){
for(int i=1;i<=m;i++) st[4][1][i]=b[i];
for(int i=2;i<=top2;i++)
for(int j=1;j<=m-SIZE[i-1]+1;j++) st[4][i][j]=min(st[4][i-1][j],st[4][i-1][j+SIZE[i-2]]);
}
void fifth(){
for(int i=1;i<=n;i++)
if(a[i]>=0) st[5][1][i]=a[i];
else st[5][1][i]=3e9;
for(int i=2;i<=top1;i++)
for(int j=1;j<=n-SIZE[i-1]+1;j++) st[5][i][j]=min(st[5][i-1][j],st[5][i-1][j+SIZE[i-2]]);
}
void sixth(){
for(int i=1;i<=m;i++)
if(b[i]>=0) st[6][1][i]=b[i];
else st[6][1][i]=3e9;
for(int i=2;i<=top2;i++)
for(int j=1;j<=m-SIZE[i-1]+1;j++) st[6][i][j]=min(st[6][i-1][j],st[6][i-1][j+SIZE[i-2]]);
}
void seventh(){
for(int i=1;i<=n;i++)
if(a[i]<=0) st[7][1][i]=a[i];
else st[7][1][i]=-3e9;
for(int i=2;i<=top1;i++)
for(int j=1;j<=n-SIZE[i-1]+1;j++) st[7][i][j]=max(st[7][i-1][j],st[7][i-1][j+SIZE[i-2]]);
}
void eighth(){
for(int i=1;i<=m;i++)
if(b[i]<=0) st[8][1][i]=b[i];
else st[8][1][i]=-3e9;
for(int i=2;i<=top2;i++)
for(int j=1;j<=m-SIZE[i-1]+1;j++) st[8][i][j]=max(st[8][i-1][j],st[8][i-1][j+SIZE[i-2]]);
}
void gettop(){
for(int i=0;i<=19;i++)
if(n>=SIZE[i]) top1=i+1;
for(int i=0;i<=19;i++)
if(m>=SIZE[i]) top2=i+1;
}
void input(){
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=q;i++) cin>>left1[i]>>right1[i]>>left2[i]>>right2[i];
}
bool anoup(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[1][flr][l]<=0;
if(l+SIZE[flr-1]-1>r) return anoup(l,r,flr-1);
return st[1][flr][l]<=0&&anoup(l+SIZE[flr-1],r,flr-1);
}
bool anodown(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[3][flr][l]>=0;
if(l+SIZE[flr-1]-1>r) return anodown(l,r,flr-1);
return st[3][flr][l]>=0&&anodown(l+SIZE[flr-1],r,flr-1);
}
bool bnoup(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[2][flr][l]<=0;
if(l+SIZE[flr-1]-1>r) return bnoup(l,r,flr-1);
return st[2][flr][l]<=0&&bnoup(l+SIZE[flr-1],r,flr-1);
}
bool bnodown(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[4][flr][l]>=0;
if(l+SIZE[flr-1]-1>r) return bnodown(l,r,flr-1);
return st[4][flr][l]>=0&&bnodown(l+SIZE[flr-1],r,flr-1);
}
ll amax(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[1][flr][l];
if(l+SIZE[flr-1]-1>r) return amax(l,r,flr-1);
return max(st[1][flr][l],amax(l+SIZE[flr-1],r,flr-1));
}
ll bmax(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[2][flr][l];
if(l+SIZE[flr-1]-1>r) return bmax(l,r,flr-1);
return max(st[2][flr][l],bmax(l+SIZE[flr-1],r,flr-1));
}
ll amin(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[3][flr][l];
if(l+SIZE[flr-1]-1>r) return amin(l,r,flr-1);
return min(st[3][flr][l],amin(l+SIZE[flr-1],r,flr-1));
}
ll bmin(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[4][flr][l];
if(l+SIZE[flr-1]-1>r) return bmin(l,r,flr-1);
return min(st[4][flr][l],bmin(l+SIZE[flr-1],r,flr-1));
}
ll apmin(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[5][flr][l];
if(l+SIZE[flr-1]-1>r) return apmin(l,r,flr-1);
return min(st[5][flr][l],apmin(l+SIZE[flr-1],r,flr-1));
}
ll bpmin(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[6][flr][l];
if(l+SIZE[flr-1]-1>r) return bpmin(l,r,flr-1);
return min(st[6][flr][l],bpmin(l+SIZE[flr-1],r,flr-1));
}
ll admax(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[7][flr][l];
if(l+SIZE[flr-1]-1>r) return admax(l,r,flr-1);
return max(st[7][flr][l],admax(l+SIZE[flr-1],r,flr-1));
}
ll bdmax(ll l,ll r,ll flr){
if(l+SIZE[flr-1]-1==r) return st[8][flr][l];
if(l+SIZE[flr-1]-1>r) return bdmax(l,r,flr-1);
return max(st[8][flr][l],bdmax(l+SIZE[flr-1],r,flr-1));
}
void doallup(ll id){
cout<<amax(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmin(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doalldown(ll id){
cout<<amin(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmax(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doaupbdown(ll id){
cout<<apmin(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmin(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doadownbup(ll id){
cout<<admax(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmax(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doaup(ll id){
cout<<apmin(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmin(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void dobup(ll id){
cout<<amax(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bpmin(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doadown(ll id){
cout<<admax(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmax(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void dobdown(ll id){
cout<<amin(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bdmax(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR))<<endl;
}
void doallhave(ll id){
ll dd1=apmin(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmin(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR));
ll dd2=admax(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR))*bmax(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR));
cout<<max(dd1,dd2)<<endl;
}
void query(ll id){
bool A=anoup(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR));
bool B=bnoup(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR));
bool C=anodown(left1[id],right1[id],floor(log2(right1[id]-left1[id]+1)+1+ERR));
bool D=bnodown(left2[id],right2[id],floor(log2(right2[id]-left2[id]+1)+1+ERR));
if(1){
if(C&&D){
doallup(id);
return;
}
if(A&&B){
doalldown(id);
return;
}
if(A&&D){
doadownbup(id);
return;
}
if(B&&C){
doaupbdown(id);
return;
}
if(A){
doadown(id);
return;
}
if(B){
dobdown(id);
return;
}
if(C){
doaup(id);
return;
}
if(D){
dobup(id);
return;
}
doallhave(id);
return;
}
}
int main(){
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
input();
gettop();
first();
second();
third();
fourth();
fifth();
sixth();
seventh();
eighth();
for(int i=1;i<=q;i++) query(i);
return 0;
}
```
by fenwicktree @ 2023-08-04 17:24:57
@A_Passing_Creeper可我也没办法呀
by 2012GFKKKZ @ 2023-08-04 17:26:05
@[lsx1234](/user/718658) 你这个代码问题还挺多。。
贪心部分可以自己想想。
把我的代码中线段树的贴一下；
```cpp
struct SegmentTree
{
int l, r;
int maxp, maxn, minp, minn;
// positive negative
int flagz;
} ta[N * 4], tb[N * 4];
int a[N], b[N];
void pushupa(int p)
{
ta[p].maxp = max(ta[p * 2].maxp, ta[p * 2 + 1].maxp);
ta[p].minp = min(ta[p * 2].minp, ta[p * 2 + 1].minp);
ta[p].maxn = max(ta[p * 2].maxn, ta[p * 2 + 1].maxn);
ta[p].minn = min(ta[p * 2].minn, ta[p * 2 + 1].minn);
ta[p].flagz = ta[p * 2].flagz || ta[p * 2 + 1].flagz;
}
void builda(int p, int l, int r)
{
ta[p].l = l, ta[p].r = r;
if (l == r)
{
if (a[l] > 0)
{
ta[p].maxp = ta[p].minp = a[l];
ta[p].maxn = -INF;
ta[p].minn = INF;
ta[p].flagz = 0;
}
else if (a[l] == 0)
{
ta[p].maxp = ta[p].maxn = -INF;
ta[p].minp = ta[p].minn = INF;
ta[p].flagz = 1;
}
else
{
ta[p].maxn = ta[p].minn = a[l];
ta[p].maxp = -INF;
ta[p].minp = INF;
ta[p].flagz = 0;
}
return;
}
int mid = (l + r) / 2;
builda(p * 2, l, mid);
builda(p * 2 + 1, mid + 1, r);
pushupa(p);
}
void pushupb(int p)
{
tb[p].maxp = max(tb[p * 2].maxp, tb[p * 2 + 1].maxp);
tb[p].minp = min(tb[p * 2].minp, tb[p * 2 + 1].minp);
tb[p].maxn = max(tb[p * 2].maxn, tb[p * 2 + 1].maxn);
tb[p].minn = min(tb[p * 2].minn, tb[p * 2 + 1].minn);
tb[p].flagz = tb[p * 2].flagz || tb[p * 2 + 1].flagz;
}
void buildb(int p, int l, int r)
{
tb[p].l = l, tb[p].r = r;
if (l == r)
{
if (b[l] > 0)
{
tb[p].maxp = tb[p].minp = b[l];
tb[p].maxn = -INF;
tb[p].minn = INF;
tb[p].flagz = 0;
}
else if (b[l] == 0)
{
tb[p].maxp = tb[p].maxn = -INF;
tb[p].minp = tb[p].minn = INF;
tb[p].flagz = 1;
}
else
{
tb[p].maxn = tb[p].minn = b[l];
tb[p].maxp = -INF;
tb[p].minp = INF;
tb[p].flagz = 0;
}
return;
}
int mid = (l + r) / 2;
buildb(p * 2, l, mid);
buildb(p * 2 + 1, mid + 1, r);
pushupb(p);
}
SegmentTree querya(int p, int l, int r)
{
if (l <= ta[p].l && ta[p].r <= r)
{
return ta[p];
}
int mid = (ta[p].l + ta[p].r) / 2;
if (l > mid) return querya(p * 2 + 1, l, r);
if (r <= mid) return querya(p * 2, l, r);
if (l <= mid && r > mid)
{
SegmentTree a = querya(p * 2, l, r), b = querya(p * 2 + 1, l, r), res;
res.maxp = max(a.maxp, b.maxp);
res.minp = min(a.minp, b.minp);
res.maxn = max(a.maxn, b.maxn);
res.minn = min(a.minn, b.minn);
res.flagz = a.flagz || b.flagz;
return res;
}
}
SegmentTree queryb(int p, int l, int r)
{
if (l <= tb[p].l && tb[p].r <= r)
{
return tb[p];
}
int mid = (tb[p].l + tb[p].r) / 2;
if (l > mid) return queryb(p * 2 + 1, l, r);
if (r <= mid) return queryb(p * 2, l, r);
if (l <= mid && r > mid)
{
SegmentTree a = queryb(p * 2, l, r), b = queryb(p * 2 + 1, l, r), res;
res.maxp = max(a.maxp, b.maxp);
res.minp = min(a.minp, b.minp);
res.maxn = max(a.maxn, b.maxn);
res.minn = min(a.minn, b.minn);
res.flagz = a.flagz || b.flagz;
return res;
}
}
```
by FuncoF9 @ 2023-08-04 17:26:06