题目概述给定数组A,B矩阵C{i,j}Ai*Bj。每轮给定 A、B 各一个区间小 L 先选 A 区间元素小 Q 后选 B 区间元素L 想乘积尽可能大Q 想乘积尽可能小两人均最优策略求每轮最终乘积。思路分析25分当A、B数组均为正数的时候直接输出A的最大值与B的最小值的乘积。#includebits/stdc.husingnamespacestd;longlongn,m,q;longlonga[1005],b[1005];intmain(){cinnmq;for(inti1;in;i){cina[i];}for(inti1;im;i){cinb[i];}while(q--){intl1,l2,r1,r2;cinl1r1l2r2;longlongmaxnLONG_LONG_MIN,minnLONG_LONG_MAX;for(intil1;ir1;i){maxnmax(maxn,a[i]);}for(intil2;ir2;i){minnmin(minn,b[i]);}coutmaxn*minnendl;}return0;}60分当我们细心地分析了所有的情况后如下图由此可得这份代码将会有一大堆if…#includebits/stdc.husingnamespacestd;longlongn,m,q,a[1005],b[1005];longlongcheck(intl1,intr1,intl2,intr2){inttypea00,typeb00;inttypea0,typeb0;longlongmaxaz0,minaz1e17,maxaf-1e17,minaf0;longlongmaxbz0,minbz1e17,maxbf-1e17,minbf0;longlongans0;for(intil1;ir1;i){if(a[i]0){maxafmax(maxaf,a[i]);minafmin(minaf,a[i]);}elseif(a[i]0){maxazmax(maxaz,a[i]);minazmin(minaz,a[i]);}elsetypea01;if(typea3)continue;if(a[i]0typea2)typea3;elseif(a[i]0typea0)typea1;elseif(a[i]0typea0)typea2;elseif(a[i]0typea1)typea3;}for(intil2;ir2;i){if(b[i]0){maxbfmax(maxbf,b[i]);minbfmin(minbf,b[i]);}elseif(b[i]0){maxbzmax(maxbz,b[i]);minbzmin(minbz,b[i]);}elsetypeb01;if(typeb3)continue;if(b[i]0typeb2)typeb3;elseif(b[i]0typeb0)typeb1;elseif(b[i]0typeb0)typeb2;elseif(b[i]0typeb1)typeb3;}if(typea1){if(typeb1)ansmaxaz*minbz;elseif(typeb2)ansminaz*minbf;elseansminaz*minbf;}elseif(typea2){if(typeb1)ansmaxaf*maxbz;elseif(typeb2)ansminaf*maxbf;elseansmaxaf*maxbz;}else{if(typeb1)ansmaxaz*minbz;elseif(typeb2)ansminaf*maxbf;elseansmax(minaz*minbf,maxaf*maxbz);}if(typea0)ansmax(ans,0ll);if(typeb0)ansmin(ans,0ll);returnans;}intmain(){cinnmq;for(inti1;in;i)cina[i];for(inti1;im;i)cinb[i];while(q--){intl1,r1,l2,r2;cinl1r1l2r2;coutcheck(l1,r1,l2,r2)endl;}return0;}AC思路只是将60分代码中的查询换成了ST表。#includebits/stdc.husingnamespacestd;usinglllonglong;constintMAXN1e55;constintLOG17;constll INF1e17;intn,m,q;ll a[MAXN],b[MAXN];//st表intlg2[MAXN];ll stazmax[LOG][MAXN];ll stazmin[LOG][MAXN];ll stafmax[LOG][MAXN];ll stafmin[LOG][MAXN];ll stbzmax[LOG][MAXN];ll stbzmin[LOG][MAXN];ll stbfmax[LOG][MAXN];ll stbfmin[LOG][MAXN];ll pa[MAXN];ll pb[MAXN];voidinitlog(intn){//lg2的预处理lg2[1]0;for(inti2;in;i)lg2[i]lg2[i/2]1;}voidbuildst(ll stmax[LOG][MAXN],ll stmin[LOG][MAXN],intlen){for(intk1;(1k)len;k){inth1(k-1);for(inti1;i(1k)-1len;i){stmax[k][i]max(stmax[k-1][i],stmax[k-1][ih]);stmin[k][i]min(stmin[k-1][i],stmin[k-1][ih]);}}}llqmax(ll st[LOG][MAXN],intl,intr){intklg2[r-l1];inth1k;returnmax(st[k][l],st[k][r-h1]);}llqmin(ll st[LOG][MAXN],intl,intr){intklg2[r-l1];inth1k;returnmin(st[k][l],st[k][r-h1]);}llcheck(intl1,intr1,intl2,intr2){booltypea00,typeb00;//状态inttypea0,typeb0;//值ll maxaz0,minazINF,maxaf-INF,minaf0;ll maxbz0,minbzINF,maxbf-INF,minbf0;ll ans0;//查询Amaxazqmax(stazmax,l1,r1);minazqmin(stazmin,l1,r1);maxafqmax(stafmax,l1,r1);minafqmin(stafmin,l1,r1);typea0(pa[r1]-pa[l1-1]0);boolhaz(maxaz!0minaz!INF);boolhaf(maxaf!-INFminaf!0);if(!haz!haf)return0;//A全为0if(haz!haf)typea1;elseif(!hazhaf)typea2;elseif(hazhaf)typea3;elsetypea0;//查询Bmaxbzqmax(stbzmax,l2,r2);minbzqmin(stbzmin,l2,r2);maxbfqmax(stbfmax,l2,r2);minbfqmin(stbfmin,l2,r2);typeb0(pb[r2]-pb[l2-1]0);boolhbz(maxbz!0minbz!INF);boolhbf(maxbf!-INFminbf!0);if(!hbz!hbf)return0;//B全为0if(hbz!hbf)typeb1;elseif(!hbzhbf)typeb2;elseif(hbzhbf)typeb3;elsetypeb0;//分类讨论if(typea1){if(typeb1){ansmaxaz*minbz;}elseif(typeb2){ansminaz*minbf;}else{ansminaz*minbf;}}elseif(typea2){if(typeb1)ansmaxaf*maxbz;elseif(typeb2)ansminaf*maxbf;elseansmaxaf*maxbz;}else{if(typeb1){ansmaxaz*minbz;}elseif(typeb2){ansminaf*maxbf;}else{ansmax(minaz*minbf,maxaf*maxbz);}}if(typea0)ansmax(ans,0ll);if(typeb0)ansmin(ans,0ll);returnans;}intmain(){cinnmq;for(inti1;in;i)//A{cina[i];pa[i]pa[i-1](a[i]0);if(a[i]0){stazmax[0][i]stazmin[0][i]a[i];stafmax[0][i]-INF;stafmin[0][i]0;}elseif(a[i]0){stafmax[0][i]stafmin[0][i]a[i];stazmax[0][i]0;stazmin[0][i]INF;}else{stazmax[0][i]0;stazmin[0][i]INF;stafmax[0][i]-INF;stafmin[0][i]0;}}for(inti1;im;i)//B{cinb[i];pb[i]pb[i-1](b[i]0);if(b[i]0){stbzmax[0][i]stbzmin[0][i]b[i];stbfmax[0][i]-INF;stbfmin[0][i]0;}elseif(b[i]0){stbfmax[0][i]stbfmin[0][i]b[i];stbzmax[0][i]0;stbzmin[0][i]INF;}else{stbzmax[0][i]0;stbzmin[0][i]INF;stbfmax[0][i]-INF;stbfmin[0][i]0;}}initlog(max(n,m));buildst(stazmax,stazmin,n);buildst(stafmax,stafmin,n);buildst(stbzmax,stbzmin,m);buildst(stbfmax,stbfmin,m);while(q--){intl1,r1,l2,r2;cinl1r1l2r2;coutcheck(l1,r1,l2,r2)endl;}return0;}