二维线段树的复杂度不是$O(qlog^2n)$吗，为什么会T

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+55;
#define tl1 u*4+1
#define tl2 u*4+2
#define tr1 u*4+3
#define tr2 u*4+4
#define ll long long
int n,m;
ll t[N*N*16],tag[N*N*16];
char op;
void push_up(int u){
	t[u]=0;
	for(int i=1;i<=4;i++)t[u]+=t[u*4+i];
}
void addtag(int u,int xl,int xr,int yl,int yr,int d){
	tag[u]+=d;
	t[u]+=(xr-xl+1)*(yr-yl+1)*d;
}
void push_down(int u,int xl,int xr,int yl,int yr){
	if(tag[u]){
		int midx=(xl+xr)/2,midy=(yl+yr)/2;
		addtag(tl1,xl,midx,yl,midy,tag[u]);
		if(xl<xr)addtag(tl2,midx+1,xr,yl,midy,tag[u]);
		if(yl<yr)addtag(tr1,xl,midx,midy+1,yr,tag[u]);
		if(xl<xr&&yl<yr)addtag(tr2,midx+1,xr,midy+1,yr,tag[u]);
		tag[u]=0;
	}
}
void upd(int a,int b,int c,int d,int u,int xl,int xr,int yl,int yr,int del){
	if(a<=xl&&b>=xr&&c<=yl&&d>=yr){
		addtag(u,xl,xr,yl,yr,del);
		return;
	}
	push_down(u,xl,xr,yl,yr);
	int midx=(xl+xr)/2,midy=(yl+yr)/2;
	if(a<=midx&&c<=midy)upd(a,b,c,d,tl1,xl,midx,yl,midy,del);
	if(xl<xr&&b>midx&&c<=midy)upd(a,b,c,d,tl2,midx+1,xr,yl,midy,del);
	if(yl<yr&&a<=midx&&d>midy)upd(a,b,c,d,tr1,xl,midx,midy+1,yr,del);
	if(xl<xr&&yl<yr&&b>midx&&d>midy)upd(a,b,c,d,tr2,midx+1,xr,midy+1,yr,del);
	push_up(u);
}
ll qry(int a,int b,int c,int d,int u,int xl,int xr,int yl,int yr){
	if(a<=xl&&b>=xr&&c<=yl&&d>=yr){
		return t[u];
	}
	push_down(u,xl,xr,yl,yr);
	int midx=(xl+xr)/2,midy=(yl+yr)/2,ret=0;
	if(a<=midx&&c<=midy)ret+=qry(a,b,c,d,tl1,xl,midx,yl,midy);
	if(xl<xr&&b>midx&&c<=midy)ret+=qry(a,b,c,d,tl2,midx+1,xr,yl,midy);
	if(yl<yr&&a<=midx&&d>midy)ret+=qry(a,b,c,d,tr1,xl,midx,midy+1,yr);
	if(xl<xr&&yl<yr&&b>midx&&d>midy)ret+=qry(a,b,c,d,tr2,midx+1,xr,midy+1,yr);
	return ret;
}
int main(){
	char tmp;scanf("%c%d%d",&tmp,&n,&m);
	while(1){
		if(!(cin>>op))break;
		int a,b,c,d;
		if(op=='L'){
			scanf("%d%d%d%d",&a,&c,&b,&d);
			int delta;scanf("%d",&delta);
			upd(a,b,c,d,1,1,n,1,m,delta);
		}else if(op=='k'){
			scanf("%d%d%d%d",&a,&c,&b,&d);
			printf("%lld\n",qry(a,b,c,d,1,1,n,1,m));
		}
	}
	return 0;
}