CF249
CF249E
CF249E题意
给你一个形如下图的矩阵
并有 \(T\) 组询问 每组询问给出 \(x_1,y_1,x_2,y_2\)。
求 \(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}A[i][j]\)。
其中 \(A[i][j]\) 表示在矩阵中的数。
\(T\leq 10^5\)
\(1\leq x_1 \leq x_2 \leq 10^9\)
\(1\leq y_1 \leq y_2 \leq 10^9\)
CF249E题解
首先先将询问拆成 \((x_2,y_2)-(x_1-1,y_2)-(x_2,y_1-1)+(x_1-1,y_1-1)\)。
然后现在考虑怎么求 \((1,1)\to (x,y)\) 的总和。
首先知道一个结论，就是 \((1,y)=((y-1)^2+1),(x,1)=x^2\)。
设 \(n=\min(x,y)\)，现在知道了 \((1,1)\to(n,n)\) 的答案是 \(\frac{n^2\times(n^2+1)}{2}\)。
这里不妨设 \(sum(n)=\sum_{i=1}^n,squ(n)=\sum_{i=1}^ni^2\)。
然后分类讨论剩下的：
- \(x>y\)，观察图形，可知每一行都是从最左侧开始递减，每次递减一。
- 先算递减一的代价，每一行的递减总和是 \(sum(y-1)\)，一共 \(x-y\) 行，所以对答案的贡献是 \(-sum(y-1)\times (x-y)\)。
- 然后算剩下的，每一列的答案都是 \(squ(x)-squ(y)\)，总和就是 \((squ(x) -squ(y))\times y\)。
- \(x<y\)，同样观察图形，可知每一列都是从最上面开始递增，每次递增一。
- 先算递增一的贡献，每一列的递增总和是 \(sum(y)\)，一共 \(y-x\) 行，所以对答案的贡献是 \(sum(y)\times (y-x)\)。
- 然后算剩下的，每一行的答案都是 \(squ(y - 1) - squ(x - 1)\)，总和就是 \((squ(y - 1) -squ(x-1))\times x\)
哦对了中间的答案最大不会超过 \(n^4\)，__int128可以驾驭，但long long好像不太行。
大水题快来切啊（bushi）
CF249E代码
#include<bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define __int128 long long
#endif
#define i128 __int128
#define ll long long
using namespace std;
inline ll read(){
ll x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
inline i128 summ(i128 x){return (x + 1) * x / 2;}
inline i128 squu(i128 x){return x * (x + 1) * (2 * x + 1) / 6;}
i128 solve(i128 x,i128 y){
if(x <= 0 || y <= 0)return 0;
i128 n = min(x, y);
i128 ans = summ(n * n);
if(x > y){
ans -= (x - y) * summ(y - 1);
ans += (squu(x) - squu(y)) * y;
}
else if(x < y){
ans += (y - x) * summ(x);
ans += (squu(y - 1) - squu(x - 1)) * x;
}
return ans;
}
signed main(){
int T = read();
while(T--){
ll xl = read(), yl = read(), xr = read(), yr = read();
i128 ans = solve(xr,yr) - solve(xl - 1,yr) - solve(xr,yl - 1) + solve(xl - 1,yl - 1);
if(ans > (i128)1e10){ans = ans % (i128)1e10;printf("...%010lld\n",(ll)ans);}
else printf("%lld\n",(ll)ans);
}
// printf("%lld\n",(ll)solve(1,3));
return 0;
}