猛新求助树状数组
查看原帖
猛新求助树状数组
639700
mtaoye楼主2022/11/19 20:45
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int 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*10+ch-48;ch=getchar();}
	return x*f;
}
const int N=2050;
int n,m;
inline int lob(int x){return (x)&(-x);}
int t1[N][N],t2[N][N],t3[N][N],t4[N][N];
void add(int x,int y,int v)
{
    for(int i=x;i<=n;i+=lob(i))
    {
        for(int j=y;j<=m;j+=lob(j))
        {
            t1[i][j]+=v;
            t2[i][j]+=v*x;
            t3[i][j]+=v*y;
            t4[i][j]+=v*x*y;
        }
    }
}
void radd(int a,int b,int c,int d,int v)
{
    add(a,b,v);
    add(a,d+1,-v);
    add(c+1,b,-v);
    add(c+1,d+1,v);
}
int query(int x,int y)
{
    int res=0;
    for(int i=x;i;i-=lob(i))
    {
        for(int j=y;j;j-=lob(j))
        {
            res+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t2[i][j]+t4[i][j];
        }
    }
    return res;
}
int rquery(int a,int b,int c,int d)
{
    return query(c,d)-query(c,b-1)-query(a-1,d)+query(a-1,b-1);
}
signed main()
{   
    char opt;
    cin>>opt;
    n=read(),m=read();
    int a,b,c,d,delta;
    while(cin>>opt)
    {
        if(opt=='L')
        {
            scanf("%d%d%d%d%d",&a,&b,&c,&d,&delta);
            radd(a,b,c,d,delta);
        }
        else
        {
            scanf("%d%d%d%d",&a,&b,&c,&d);
            cout<<rquery(a,b,c,d)<<endl;
        }
    }
}

而结果是这样 求神犇解答

2022/11/19 20:45
加载中...