题意简述
在上图所示的矩阵中求一个子矩形的元素和。
思路
先可以考虑差分。然后问题转化为求以 \((x,y)\) 为右下角的矩形的元素和。先考虑 \(x\leq y\) 的情况。\(x>y\) 的情况同理可推。先可以算出以 \((x,x)\) 为右下角的，答案为 \(\sum\limits_{i=1}^{x^2}i\)。
然后考虑剩下的部分。每一列最上方是 \(x^2+1,(x+1)^2+1,\cdots,(y-1)^2+1\)，每一列有 \(x\) 个递增的数。所以总的就是 \(x[x^2+(x+1)^2+\cdots+(y-1)^2]+[(y-1)-x+1]\times\dfrac{x(x+1)}{2}\)，可以通过平方和公式 \(\left(\sum \limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6}\right)\) 计算。若 \(x>y\) 则同理。这里不给出式子。可以看看图。
一些细节：输出的时候如果后十位有前导 \(0\) 也要输出。要求判断位数是否大于十位，简单计算可得最大的答案不超过 __int128 的储存范围，所以计算完后判断再输出即可。
Code
代码很短，加上 Fast IO 目前是你谷最优解。当然 CF 太强了卡不到第一。/kk
#define ll __int128
ll sum(ll x){
return x*(x+1)*(2*x+1)/6;
}
ll calc(ll x,ll y){
if(x<=y){
return x*(x+1)/2*(y-x)+(sum(y-1)-sum(x-1))*x+x*x*(x*x+1)/2;
}
return (sum(x)-sum(y))*y-y*(y-1)/2*(x-y)+y*y*(y*y+1)/2;
}
int main(){
int t=gi();
ll x,y,a,b,ans;
while(t--){
x=gl();
y=gl();
a=gl();
b=gl();
ans=calc(a,b)-calc(x-1,b)-calc(a,y-1)+calc(x-1,y-1);
print(ans);
}
}