qbxt DAY 6 T3 柯西不等式和拉格朗日不等式

qbxt DAY 6 T3

其实主要是对拉格朗日不等式的了解和认识。

((sum a_i^2)(sum b_i^2)=(sum a_ib_i)^2+sumlimits_{1leq i< jleq n}(a_ib_j-a_jb_i)^2)

柯西不等式：

((sum a_i^2)(sum b_i^2)geq (sum a_ib_i)^2)

把两边开根

(sqrt{(sum a_i^2)} sqrt{(sum b_i^2)}geq (sum a_ib_i))

可以看成两个(n)维向量((a_1,a_2,...,a_n))和((b_1,b_2,...,b_n))

则原式就是他们的模长之积大于等于点积

而(vec{m}cdotvec{n}=|vec{m}|cdot|vec{n}|cdot cos<vec{m},vec{n}>)，(cos<vec{m},vec{n}> leq 1)

则不等式得证

或者直接用拉格朗日不等式证明，因为(sumlimits_{1leq i< jleq n}(a_ib_j-a_jb_i)^2 geq 0)，所以不等式得证

证明拉格朗日不等式

首先展开

(sumlimits_{1leq i< jleq n}(a_ib_j-a_jb_i)^2=sumlimits_{i<j}(a_i^2b_j^2-2a_ib_ia_jb_j+a_j^2b_i^2))

先看前后两项

(sumlimits_{i,j}a_i^2b_j^2-sumlimits_{i=j}a_i^2b_j^2 )

前面的(i,j)是独立的，可以单独拿出来

(sumlimits_ia_i^2sumlimits_jb_j^2)

中间那一项(sumlimits_{i<j}2a_ib_ia_jb_j)，可以把(i)提出来，并且把(i,j)的位置换一下，也就变成了

[egin{aligned}& sumlimits_{i<j}a_ib_ia_jb_j+sumlimits_{i>j}a_ib_ia_jb_j \& =sumlimits_{i eq j}a_ib_ia_jb_j\& =sumlimits_{i,j}a_ib_ia_jb_j-sumlimits_{i=j}a_ib_ja_jb_iend{aligned} ]

原式就是

[ egin{aligned}& sumlimits_ia_i^2sumlimits_jb_j^2 -sumlimits_{i}a_i^2b_i^2-sumlimits_{i,j}a_ib_ia_jb_j+sumlimits_{i}a_i^2b_i^2 \&= (sum a_i^2)(sum b_i^2)-(sum a_ib_i)^2 end{aligned}]

则等式得证

对于这道题来说，就只需要维护这三个值的树上前缀和就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
	char s = getchar(), last = '0';
	ll ans = 0;
	while(s < '0' || s > '9') last = s, s = getchar();
	while(s >= '0' && s <= '9') ans = ans * 10 + s - '0', s = getchar();
	if(last == '-') ans = -ans;
	return ans;
}
const ll mod = 998244353;
const int  N = 500005;
ll p, n, q, t, l, r, ans, a2[N], b2[N], a[N], b[N], ab[N];
int low(int x){return x & (-x);}
void add1(int now, ll v)
{
	while(now <= n)
	{
		a2[now] = (a2[now] + v) % mod;
		now += low(now);
	}
}
void add2(int now, ll v)
{
	while(now <= n)
	{
		b2[now] = (b2[now] + v) % mod;
		now += low(now);
	}
}
void add3(int now, ll v)
{
	while(now <= n)
	{
		ab[now] = (ab[now] + v) % mod;
		now += low(now);
	}
}
ll query1(int now)
{
	ll rt = 0;
	while(now)
	{
		rt += a2[now];
		now -= low(now);
	}
	return rt % mod;
}
ll query2(int now)
{
	ll rt = 0;
	while(now)
	{
		rt += b2[now];
		now -= low(now);
	}
	return rt % mod;
}
ll query3(int now)
{
	ll rt = 0;
	while(now)
	{
		rt += ab[now];
		now -= low(now);
	}
	return rt % mod;
}
ll qr1(int l, int r)
{
	return (query1(r) - query1(l - 1) + mod) % mod;
}
ll qr2(int l, int r)
{
	return (query2(r) - query2(l - 1) + mod) % mod;
}
ll qr3(int l, int r)
{
	return (query3(r) - query3(l - 1) + mod) % mod;
}
int main()
{
	cin>>n>>q;
	for(int i = 1; i <= n; i ++)
	{
		a[i] = read();
		add1(i, a[i] * a[i] % mod);
	}
	for(int i = 1; i <= n; i ++)
	{
		b[i] = read();
		add2(i, b[i] * b[i] % mod);
		add3(i, a[i] * b[i] % mod);
	}
	for(int i = 1; i <= q; i ++)
	{
		t = read();
		if(t == 1)
		{
			l = read(), r = read();
			ans = qr3(l, r);
			ans = (-ans * ans + mod * mod) % mod;
			ans = (ans + qr1(l, r) * qr2(l, r)) % mod;
			printf("%lld
", ans);
		}
		if(t == 2)
		{
			p = read(), l = read(), r = read();
			add1(p, (l * l - a[p] * a[p] + mod * mod) % mod);
			add2(p, (r * r - b[p] * b[p] + mod * mod) % mod);
			add3(p, (l * r - a[p] * b[p] + mod * mod) % mod);
			a[p] = l, b[p] = r;
		}
	}
}