二维线段树求条
  • 板块学术版
  • 楼主d909RCA
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/12/5 22:46
  • 上次更新2024/12/6 16:39:48
查看原帖
二维线段树求条
703115
d909RCA楼主2024/12/5 22:46
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int,int>
#define pq priority_queue
#define il inline
#define rg register
namespace d909RCA_math
{
	int fac[200009];
	void Cinit(int p) 
	{
		fac[0] = 1;
		for(int i=1;i<200000;i++)
		{
			fac[i]=fac[i-1]*i%p;
		}
	}
	int qpow(int a,int b,int p) 
	{
		int ans=1;
		while(b) 
		{
			if(b&1) ans=ans*a%p;
			a=a*a%p;
			b>>=1;
		}
		return ans;
	}
	int C(int n,int m,int p) 
	{
		if(m>n||m<0) return 0;
		return fac[n]*qpow(fac[m],p-2,p)%p*qpow(fac[n-m],p-2,p)%p;
	}
	int Lucas(int n,int m,int p) 
	{
		if(!m) return 1;
		return (C(n%p,m%p,p)*Lucas(n/p,m/p,p))%p;
	}
	int GCD(int n,int m,int p) 
	{
		return __gcd(n,m)%p;
	}
	int LCM(int n,int m,int p) 
	{
		return n*m%p*qpow(GCD(n,m,p),p-2,p)%p;
	}
}
using namespace d909RCA_math;
// #define file 1
// #define multi_test 1
#define segment_tree 1
#ifdef segment_tree
#define mid ((l+r)>>1)
#define mid2 ((t+b)>>1)
#define lson k<<1
#define rson k<<1|1
#define son1 (k<<2)
#define son2 (k<<2)+1
#define son3 (k<<2)+2
#define son4 (k<<2)+3
#endif
namespace d909RCA
{
	int n,m;
	map<int,int> sum,tg;
	void pushup(int k)
	{
		sum[k]=sum[son1]+sum[son2]+sum[son3]+sum[son4];
	}
	void pushdown(int k)
	{
		if(tg[k])
		{
			tg[son1]+=tg[k];
			sum[son1]+=tg[k];
			tg[son2]+=tg[k];
			sum[son2]+=tg[k];
			tg[son3]+=tg[k];
			sum[son3]+=tg[k];
			tg[son4]+=tg[k];
			sum[son4]+=tg[k];
			tg[k]=0;
		}
	}
	int query(int k,int l,int r,int t,int b,int L,int R,int T,int B)
	{
        // cout<<k<<" "<<l<<" "<<r<<" "<<t<<" "<<b<<" "<<sum[k]<<'\n';
        if(L<=l&&r<=R&&T<=t&&b<=B) 
        {
            // cout<<"ans:"<<k<<" "<<l<<" "<<r<<" "<<t<<" "<<b<<" "<<sum[k]<<'\n';
            return sum[k];
        }
        pushdown(k);
        int ans=0;
        if(L<=mid)
        {
            if(T<=mid2) ans+=query(son1,l,mid,t,mid2,L,R,T,B);
            if(B>mid2) ans+=query(son2,l,mid,mid2+1,b,L,R,T,B);
        }
        if(R>mid)
        {
            if(T<=mid2) ans+=query(son3,mid+1,r,t,mid2,L,R,T,B);
            if(B>mid2) ans+=query(son4,mid+1,r,mid2+1,b,L,R,T,B);
        }
        return ans;
	}
	void modify(int k,int l,int r,int t,int b,int L,int R,int T,int B,int d)
	{
        // cout<<k<<" "<<l<<" "<<r<<" "<<t<<" "<<b<<" "<<sum[k]<<'\n';
        if(L<=l&&r<=R&&T<=t&&b<=B) 
        {
            // cout<<"add:"<<k<<" "<<l<<" "<<r<<" "<<t<<" "<<b<<" "<<((r-l+1)*(b-t+1)*d)<<'\n';
            sum[k]+=((r-l+1)*(b-t+1)*d);
            tg[k]+=d;
            return ;
        }
        pushdown(k);
        if(L<=mid)
        {
            if(T<=mid2) modify(son1,l,mid,t,mid2,L,R,T,B,d);
            if(B>mid2) modify(son2,l,mid,mid2+1,b,L,R,T,B,d);
        }
        if(R>mid)
        {
            if(T<=mid2) modify(son3,mid+1,r,t,mid2,L,R,T,B,d);
            if(B>mid2) modify(son4,mid+1,r,mid2+1,b,L,R,T,B,d);
        }
        pushup(k);
	}
	void inp()
	{
        cin>>n>>m;
	}
	void solve()
	{
        int op;
        while(cin>>op)
		{
			int w,x,y,z,d;
			cin>>w>>x>>y>>z;
			// cout<<w<<" "<<x<<" "<<y<<" "<<z<<'\n';
			if(op==1)
			{
				cin>>d;
				modify(1,1,n,1,m,w,y,x,z,d);
			}
			else cout<<query(1,1,n,1,m,w,y,x,z)<<'\n';
			// cout<<'\n';
		}
	}
	void print()
	{
		
	}
}
using namespace d909RCA;
signed main()
{
	int t=1;
	IOS
	#ifdef file
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif
	#ifdef multi_test
		cin>>t;
		ios::sync_with_stdio(true);
	#endif
		d909RCA::inp();
		d909RCA::solve();
		d909RCA::print();
	return 0;
}
2024/12/5 22:46
加载中...