#Codeforces 1060C 树状数组

传送门：

题意如下：给A数组和B数组，并建立C数组，建立规则为Cij = Ai*Bj。求所有子矩阵中矩阵元素和<=x的元素最多的那个矩阵，并输出矩阵元素数量

首先我们要知道矩阵区间和可以表示为 sumA[ai~aj]*sumB[bi~bj] (sumA[ai~aj]表示ai到aj的和，sumB[bi~bj]表示bi到bj的区间和)

我们可以以O(n^2)的复杂度把A和B的任意区间的区间和求出来。接下来对于每一个A的区间和，都计算B区间和能达到的最大值 x/sumA。我们需要的是比这个值小的B的区间和中区间长度最大的值。这种区间问题很容易就想到了树状数组

#include
    
     #define pb push_back#define MID(a,b) ((a+b)>>1)#define LL(a) (a<<1)#define RR(a) (a<<1|1)using namespace std;typedef long long ll;typedef pair
     
      pii;typedef pair
      
        pdi;typedef pair
       
        pli;typedef pair
        
         pll;typedef pair
         
          psi;const int N = 1e5+5,M=100005;const int inf=0x3f3f3f3f;const ll INF=1000000000000000000ll;const ll mod = 998244353;const double pi=acos(-1.0);const double eps=1e-6;int a[2005], b[2005], e[4000005];int lb(int k){ return k&-k;}void add(int v, int pos){ for(int i=pos;i<=4000000; i+=lb(i)){ e[i] = max(e[i], v); }}int getmax(int pos){ int maxi = -1; for(int i = pos; i>=1; i-=lb(i)){ maxi = max(maxi, e[i]); } return maxi;}int main(){ int n, m; while(~scanf("%d%d", &n,&m)){ memset(e, 0, sizeof(e)); for(int i=1;i<=n;i++){ scanf("%d", &a[i]); a[i] += a[i-1]; } for(int i=1;i<=m;i++){ scanf("%d", &b[i]); b[i] += b[i-1]; } int x; scanf("%d", &x); for(int len=1;len<=m;len++){ for(int i=len;i<=m;i++){ add(len, b[i] - b[i-len]); } } int maxi = -1, tmp; for(int len=1;len<=n;len++){ for(int i=len;i<=n;i++){ tmp = min(4000000, x / (a[i]-a[i-len])); maxi = max(maxi, getmax(tmp) * len); } } printf("%d\n", maxi); }}复制代码