「雅礼day4」天才绅士少女助手克里斯蒂娜 - 树状数组

题目大意

---

题目分析

将向量叉积打开得到：

$$\sum_{1\le j\lt k\le n}(x_jy_k-x_ky_j)^2$$ $$\sum_{1\le j\lt k\le n}(a_jb_k-a_kb_j)^2=\sum_{k_1=1}^na_{k_1}^2\sum_{k_2=1}^nb_{k_2}^2-(\sum_{k=1}^na_kb_k)^2$$

然后用树状数组维护一下即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const int maxn=1000005;
const LL mod=20170927;
LL n,m,x[maxn],y[maxn];
struct BIT {
	LL c[3][maxn];
	#define lowbit(x) x&(-x)
	void add(int bj,int pos,LL val) {
		for(int i=pos; i<=n; i+=lowbit(i))c[bj][i]=(c[bj][i]+val)%mod;
	}
	LL sum(int bj,int pos) {
		LL ans=0;
		for(int i=pos; i>=1; i-=lowbit(i))ans=(ans+c[bj][i])%mod;
		return ans;
	}
} bit;
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=1; i<=n; i++) {
		x[i]=Get_Int();
		y[i]=Get_Int();
		bit.add(0,i,x[i]*x[i]%mod);
		bit.add(1,i,y[i]*y[i]%mod);
		bit.add(2,i,x[i]*y[i]%mod);
	}
	for(int i=1; i<=m; i++) {
		int opt=Get_Int();
		if(opt==1) {
			LL pos=Get_Int(),_x=Get_Int(),_y=Get_Int();
			bit.add(0,pos,(-x[pos]*x[pos]%mod+mod)%mod);
			bit.add(1,pos,(-y[pos]*y[pos]%mod+mod)%mod);
			bit.add(2,pos,(-x[pos]*y[pos]%mod+mod)%mod);
			x[pos]=_x,y[pos]=_y;
			bit.add(0,pos,x[pos]*x[pos]%mod);
			bit.add(1,pos,y[pos]*y[pos]%mod);
			bit.add(2,pos,x[pos]*y[pos]%mod);
		} else {
			LL x=Get_Int(),y=Get_Int();
			LL tmp=bit.sum(2,y)-bit.sum(2,x-1);
			printf("%lld\n",(((bit.sum(0,y)-bit.sum(0,x-1))*(bit.sum(1,y)-bit.sum(1,x-1))-tmp*tmp)%mod+mod)%mod);
		}
	}
	return 0;
}