2022.07.19 Logu p6588 『 jroi-1 』 vector

$$\text{P6588 [JROI-1] }\text{Vector}$$

$\text{[Problem]}$

You have now $n$ Vector $\overrightarrow{a_i}=(x_i,y_i)$, You need to do something $5$ Operations in total $m$ Time ：

1. Put the vector $\overrightarrow{a_i}$ Add the given directional quantity $(\Delta x,\Delta y)$
2. Put the vector $\overrightarrow{a_i}$ Subtract the given amount $(\Delta x,\Delta y)$
3. Put the vector $\overrightarrow{a_i}$ With a given integer $k$ Perform multiplication , Namely the $\overrightarrow{a_i}$ Turn into $(k\times x_i,k\times y_i)$
4. inquiry $\sum _{i=l}^{r-1}\sum _{j=i+1}^r\overrightarrow{a_i}\cdot \overrightarrow{a_j}$（ That is to find the sum of dot multiplication ）
5. inquiry $\sum _{i=1}^{r-1}\sum _{j=i+1}^r\overrightarrow{a_i}\oplus \overrightarrow{a_j}$（ That is to find the sum of cross products ）

（ As for what each operation means , Please do the basic operation of Baidu vector by yourself ）

$1\le n,m\le 1\times 10^5$. Guarantee any vector at any time $\overrightarrow{a_i}$ The absolute value of the horizontal and vertical coordinates of is not greater than $1000$.

$\text{[Analysis]}$

The first three operations are the basic operations of the segment tree , Focus on the fourth and fifth operations .

$\text{Operation 4}$

Because dot multiplication has Commutative law ¹ and Distributive law ², therefore ：

$$\sum _{i=l}^{r-1}\sum _{j=i+1}^r\overrightarrow{a_i}\cdot \overrightarrow{a_j}=\frac{{\left(\overrightarrow{s_{l,r}}\right)}^2-\sum _{i=l}^r{\left(\overrightarrow{a_i}\right)}^2}{2}$$

among ：

$$s_{l,r}=\sum _{i=l}^r\overrightarrow{a_i}$$

It's equivalent to multiplying all vectors once , Subtract yourself by yourself , Divided by $2$（ because $\overrightarrow{a}$ and $\overrightarrow{b}$ Will multiply twice ）.

$\text{Operation 5}$

unfortunately , Cross multiplication has no commutative law ³, Only the law of distribution .

We have a new way , remember ：

$${\text{Cross}}_{l,r}=\sum _{i=1}^{r-1}\sum _{j=i+1}^r\overrightarrow{a_i}\oplus \overrightarrow{a_j}$$

$${\text{Sx}}_{l,r}=\sum _{i=l}^r{x}_i$$

namely ${\text{Sx}}_{l,r}$ Vector $\overrightarrow{a_{l\cdots r}}$ The sum of abscissa of ,${\text{Sy}}_{l,r}$ similar , Is the sum of the ordinates .

take $\forall \text{mid}\text{s.t.}l\le \text{mid}\le r$, be ：

$${\text{Cross}}_{l,r}={\text{Cross}}_{l,\text{mid}}+{\text{Cross}}_{\text{mid}+1,r}+{\text{Sx}}_{l,\text{mid}}\times {\text{Sy}}_{\text{mid}+1,r}-{\text{Sy}}_{l,\text{mid}}\times {\text{Sx}}_{\text{mid}+1,r}$$

According to this nature , We can use the segment tree to maintain .

$\text{[code]}$

typedef long long ll;
const int N=1e5+100,M=N<<2;

ll x[M],y[M],xs[M],ys[M],Cross[M];

pair<ll,ll> add(pair<ll,ll> a,pair<ll,ll> b){
    
	return make_pair(a.first+b.first,a.second+b.second);
}

inline void maintain(int o){
    
	xs[o]=x[o]*x[o];
	ys[o]=y[o]*y[o];
}//maintain the leaves

pair<int,int> a[N];

inline void pushup(int o){
    
	x[o]=x[o<<1]+x[o<<1|1];
	y[o]=y[o<<1]+y[o<<1|1];
	xs[o]=xs[o<<1]+xs[o<<1|1];
	ys[o]=ys[o<<1]+ys[o<<1|1];
	Cross[o]=Cross[o<<1]+Cross[o<<1|1]+x[o<<1]*y[o<<1|1]-y[o<<1]*x[o<<1|1];
}
void build(int o,int l,int r){
    
	if (l==r){
    
		x[o]=a[l].first;
		y[o]=a[r].second;
		maintain(o);
		return;
	}
	int mid=(l+r)>>1;
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
	pushup(o);return;
}
void modify(int o,int l,int r,int p,int vx,int vy){
    
	if (l==r){
    
		x[o]+=vx;y[o]+=vy;
		maintain(o);
		return;
	}
	int mid=(l+r)>>1;
	if (p<=mid) modify(o<<1,l,mid,p,vx,vy);
	else modify(o<<1|1,mid+1,r,p,vx,vy);
	pushup(o);return;
}//add or minus （ operation  1,2）
void modify(int o,int l,int r,int p,int v){
    
	if (l==r){
    
		x[o]*=v;y[o]*=v;
		maintain(o);
		return;
	}
	int mid=(l+r)>>1;
	if (p<=mid) modify(o<<1,l,mid,p,v);
	else modify(o<<1|1,mid+1,r,p,v);
	pushup(o);return;
}//times （ operation  3）
pair<ll,ll> query(int o,int l,int r,int p,int q){
    
	if (p<=l&&r<=q) return make_pair(x[o],y[o]);
	int mid=(l+r)>>1;
	pair<ll,ll> ret=make_pair(0ll,0ll);
	if (p<=mid) ret=add(ret,query(o<<1,l,mid,p,q));
	if (mid<q) ret=add(ret,query(o<<1|1,mid+1,r,p,q));
	return ret;
}//the sum of ai （ Sum up ）
ll Query(int o,int l,int r,int p,int q){
    
	if (p<=l&&r<=q) return xs[o]+ys[o];
	int mid=(l+r)>>1;ll ans=0;
	if (p<=mid) ans+=Query(o<<1,l,mid,p,q);
	if (mid<q) ans+=Query(o<<1|1,mid+1,r,p,q);
	return ans;
}//the sum of ai dot ai （ Point multiplication ）
pair<ll,pair<ll,ll> > QUERY(int o,int l,int r,int p,int q){
    
	if (p<=l&&r<=q) return make_pair(Cross[o],make_pair(x[o],y[o]));
	int mid=(l+r)>>1;
	pair<ll,pair<ll,ll> > L,R;
	L=make_pair(0ll,make_pair(0ll,0ll));
	R=make_pair(0ll,make_pair(0ll,0ll));
	if (p<=mid) L=QUERY(o<<1,l,mid,p,q);
	if (mid<q) R=QUERY(o<<1|1,mid+1,r,p,q);
	ll ans=L.first+R.first+L.second.first*R.second.second-L.second.second*R.second.first;
	return make_pair(ans,make_pair(L.second.first+R.second.first,L.second.second+R.second.second));
}//the sum of ai cross ai （ Cross riding ）

int n,m;

int main(){
    
	n=read();m=read();
	for(int i=1;i<=n;i++){
    
		int u=read(),v=read();
		a[i]=make_pair(u,v);
	}
	
	build(1,1,n);
	
	for(int i=1,opt,l,r,vx,vy;i<=m;i++){
    
		opt=read();l=read();
		if (opt==1){
    
			vx=read();vy=read();
			modify(1,1,n,l,vx,vy);
		}
		else if (opt==2){
    
			vx=read();vy=read();
			modify(1,1,n,l,-vx,-vy);
		}
		else if (opt==3){
    
			vx=read();
			modify(1,1,n,l,vx);
		}
		else if (opt==4){
    
			r=read();
			pair<ll,ll> tmp=query(1,1,n,l,r);
			ll Minus=Query(1,1,n,l,r);
			printf("%lld\n",(tmp.first*tmp.first+tmp.second*tmp.second-Minus)/2);
		}// Don't forget to divide by  2
		else{
    
			r=read();
			pair<ll,pair<ll,ll> > ans=QUERY(1,1,n,l,r);
			printf("%lld\n",ans.first);
		}
	}
	
	return 0;
}