树套树区修区查求条
  • 板块题目总版
  • 楼主d909RCA
  • 当前回复5
  • 已保存回复5
  • 发布时间2025/1/4 10:34
  • 上次更新2025/1/4 15:17:27
查看原帖
树套树区修区查求条
703115
d909RCA楼主2025/1/4 10:34
#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 il inline
#define rg register
// #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)-2
#define son2 (k<<2)-1
#define son3 k<<2
#define son4 (k<<2)+1
#endif
namespace d909RCA
{
	int ssum[8009][8009],stg[8009][8009],tsum[8009][8009],ttg[8009][8009],n,m,ans;
	void smodify(int rt,int k,int l,int r,int L,int R,int d)
	{
		ssum[rt][k]+=(d*(R-L+1));
		if(l==L&&r==R)
		{
			stg[rt][k]+=(d*(R-L+1));
			return ;
		}
		int mid=(l+r)>>1;
		if(R<=mid) smodify(rt,k<<1,l,mid,L,R,d);
		else if(L>mid) smodify(rt,k<<1|1,mid+1,r,L,R,d);
		else 
		{
			smodify(rt,k<<1,l,mid,L,mid,d);
			smodify(rt,k<<1|1,mid+1,r,mid+1,R,d);
		}
	}
	int squery(int rt,int k,int l,int r,int L,int R)
	{
        // cout<<l<<" "<<r<<" "<<ssum[rt][k]<<'\n';
		if(l==L&&r==R) return ssum[rt][k];
		int ans=stg[rt][k],mid=(l+r)>>1;
		if(R<=mid) ans+=squery(rt,k<<1,l,mid,L,R);
		else if(L>mid) ans+=squery(rt,k<<1|1,mid+1,r,L,R);
		else
		{ 
			ans+=squery(rt,k<<1,l,mid,L,mid);
			ans+=squery(rt,k<<1|1,mid+1,r,mid+1,R);
		}
		return ans;
	}
	void tmodify(int rt,int k,int l,int r,int L,int R,int d)
	{
		tsum[rt][k]+=(d*(R-L+1));
		if(l==L&&r==R)
		{
			ttg[rt][k]+=(d*(R-L+1));
			return ;
		}
		int mid=(l+r)>>1;
		if(R<=mid) tmodify(rt,k<<1,l,mid,L,R,d);
		else if(L>mid) tmodify(rt,k<<1|1,mid+1,r,L,R,d);
		else 
		{
			tmodify(rt,k<<1,l,mid,L,mid,d);
			tmodify(rt,k<<1|1,mid+1,r,mid+1,R,d);
		}
	}
	int tquery(int rt,int k,int l,int r,int L,int R)
	{
		if(l==L&&r==R) return tsum[rt][k];
		int ans=ttg[rt][k],mid=(l+r)>>1;
		if(R<=mid) ans+=tquery(rt,k<<1,l,mid,L,R);
		else if(L>mid) ans+=tquery(rt,k<<1|1,mid+1,r,L,R);
		else
		{ 
			ans+=tquery(rt,k<<1,l,mid,L,mid);
			ans+=tquery(rt,k<<1|1,mid+1,r,mid+1,R);
		}
		return ans;
	}
	void modifx(int k,int l,int r,int L,int R,int T,int B,int d)
	{
		smodify(k,1,1,m,T,B,d);
		if(l==L&&r==R)
		{
			tmodify(k,1,1,m,T,B,d);
			return ;
		}
		int mid=(l+r)>>1;
		if(R<=mid) modifx(k<<1,l,mid,L,R,T,B,d);
		else if(L>mid) modifx(k<<1|1,mid+1,r,L,R,T,B,d);
		else
		{
			modifx(k<<1,l,mid,L,mid,T,B,d);
			modifx(k<<1|1,mid+1,r,mid+1,R,T,B,d);
		}
	}
	int querx(int k,int l,int r,int L,int R,int T,int B)
	{
		if(l==L&&r==R) return squery(k,1,1,m,T,B);
		int ans=tquery(k,1,1,m,T,B),mid=(l+r)>>1;
		if(R<=mid) ans+=querx(k<<1,l,mid,L,R,T,B);
		else if(L>mid) ans+=querx(k<<1|1,mid+1,r,L,R,T,B);
		else
		{
			ans+=querx(k<<1,l,mid,L,mid,T,B);
			ans+=querx(k<<1|1,mid+1,r,mid+1,R,T,B);
		}
		return ans;
	}
    // void debuy(int rt,int k,int l,int r,int t,int b)
    // {
    //     cout<<'('<<t<<','<<l<<')'<<" to "<<'('<<b<<','<<r<<')'<<" "<<ssum[rt][k]<<" "<<stg[rt][k]<<" "<<tsum[rt][k]<<" "<<ttg[rt][k]<<'\n';
    //     if(l==r) return ;
    //     int mid=(l+r)>>1;
    //     debuy(rt,k<<1,l,mid,t,b);
    //     debuy(rt,k<<1|1,mid+1,r,t,b);
    // }
    // void debux(int k,int l,int r)
    // {
    //     debuy(k,1,1,m,l,r);
    //     if(l==r) return ;
    //     int mid=(l+r)>>1;
    //     debux(k<<1,l,mid);
    //     debux(k<<1|1,mid+1,r);
    // }
	il void inp()
	{
        cin>>n>>m;
	}
	il void solve()
	{
		int op;
        while(cin>>op)
		{
			int x1,y1,x2,y2,d;
			cin>>x1>>y1>>x2>>y2;
			if(op==1)
			{
				cin>>d;
				modifx(1,1,n,x1,x2,y1,y2,d);
			}
			else cout<<querx(1,1,n,x1,x2,y1,y2)<<'\n';
            // debux(1,1,n);
//			cout<<maxx<<"\n";
		}
	}
	il void print()
	{
        /*
        4 4
        1 1 1 3 3 2
        1 2 2 4 4 1
        2 2 2 3 3
        */
	}
}
using namespace d909RCA;
signed main()
{
	int t=1;
	#ifdef file
		freopen(".in","r",stdin);
		freopen(".out","w",stdout);
	#endif
	#ifdef multi_test
		cin>>t;
		ios::sync_with_stdio(true);
	#endif
	while(t--)
	{
		d909RCA::inp();
		d909RCA::solve();
		d909RCA::print();
	}
	return 0;
}

2025/1/4 10:34
加载中...