题目描述
红莉栖想要弄清楚楼下天王寺大叔的显像管电视对“电话微波炉（暂定）”的影响。
选取显像管的任意一个平面，一开始平面内有个$n$电子，初始速度分别为$v_i$，定义飘升系数为
$$sum limits_{1leqslant i<jleqslant n}|v_i imes v_j|^2$$
由于电视会遭到大叔不同程度的暴击，电子的速度常常会发生变化。也就是说，有两种类型的操作：
$ullet 1 p x y$将$v_p$改为$(x,y)$
$ullet 2 l r$询问$[l,r]$这段区间内的电子的飘升系数
这么简单的问题红莉栖当然能解决，但是她需要一个人帮忙验证一下结果的正确性。
由于唯一帮得上忙的桶子去找菲利斯了，于是只能拜托你来完成这个任务了。答案对$20170927$取模即可。
输入格式
第一行两个整数$n,m$表示电子个数和询问个数。
接下来$n$行，每行两个整数$x,y$表示$v_i$。
接下来$m$行，每行形如$1 p x y$或$2 l r$，分别表示两种操作。
输出格式
对于每个操作$2$，输出一行一个整数表示飘升系数对$20170927$取模的值。
样例
样例输入：
9 5
13052925 5757314
9968857 11135327
13860145 3869873
6912189 3461377
2911603 7061332
6334922 7708411
5505379 5915686
6806727 588727
7603043 15687404
2 1 6
1 7 2602783 18398476
1 8 8636316 19923037
2 2 7
2 2 4
样例输出：
18529202
963126
19167545
数据范围与提示
对于$100\%$的数据，$1leqslant n,mleqslant 10^6,0leqslant x_i,y_i<20170927,1leqslant l_ileqslant r_ileqslant n$。
题解
我依（$qing$）稀（$chu$）记得波波老师让我出过这道题的数据，就是题面动了一点，时间限制调小了（当时我还是挺慌的，原题$4s$，现在这个时限我的代码都跑不过我的数据……），但是我还是打了，然后它就$A$了……
简单说一下，上面那个鬼畜的$ imes$其实是叉积也就是：
$v_1=(x_1,y_1),v_2=(x_2,y_2) Rightarrow vec{v_1} imes vec{v_2}=x_1 imes y_2-x_2 imes y_1$。
初步是这样的：$large egin{array}{ll} ans &=& sum limits_{i=l}^r sum limits_{j=i+1}^r (v_i imes v_j)^2 \ &=& sum limits_{i=l}^r sum limits_{j=i+1}^r (x_iy_j-x_jy_i)^2 end{array}$
那么我们化简一下上面那个式子即可得到：
$large egin{array}{ll} ans &=& sum limits_{i=l}^{r} sum limits_{j=i+1}^r (x_i^2y_j^2+x_j^2y_i^2-2x_iy_ix_jy_j) \ &=& sum limits_{i=l}^r sum limits_{j=i+1}^r x_i^2y_j^2 + sum limits_{i=l}^r sum limits_{j=i+1}^r x_j^2y_i^2 - sum limits_{i=l}^r sum limits_{j=i+1}^r 2x_iy_ix_jy_j \ &=& sum limits_{i=l}^r sum limits_{j=l}^r [i!=j] imes x_i^2y_j^2 - sum limits_{i=l}^r sum limits_{j=l}^r [i!=j] imes x_iy_ix_jy_j \ &=& sum limits_{i=l}^r x_i^2 (sum limits_{j=l}^r y_j^2 -y_i^2) - (sum limits_{i=l}^r x_iy_i (sum limits_{j=l}^r x_jy_j - x_iy_i)) \ &=& sum limits_{i=l}^r x_i^2 sum limits_{j=l}^r y_j^2 - sum limits_{i=l}^r x_i^2y_i^2 - (sum limits_{i=l}^r x_iy_i sum limits_{j=l}^r x_jy_j - sum limits_{i=l}^r x_i^2 y_i^2) \ &=& sum limits_{i=l}^r x_i^2 imes sum limits_{i=l}^ry_i^2 - (sum limits_{i=l}^r x_iy_i)^2end{array}$
有了这个式子，我们就可以用三个树状数组维护分别维护$sum limits_{i=l}^r x_i^2$，$sum limits_{i=l}^r y_i^2$，$sum limits_{i=l}^r x_iy_i$即可。
时间复杂度：$Theta((n+m)log n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
const int mod=20170927;
int n,m;
long long tr[3][4000001];
pair<long long,long long> e[1000001];
void add(int x,long long val,int id)
{
for(int i=x;i<=n;i+=i&-i)
tr[id][i]=(tr[id][i]+val)%mod;
}
long long query(int x,int id)
{
long long res=0;
for(int i=x;i;i-=i&-i)
res=(res+tr[id][i])%mod;
return res;
}
long long ask(int l,int r,int id)
{
return (query(r,id)-query(l-1,id)+mod)%mod;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&e[i].first,&e[i].second);
add(i,e[i].first*e[i].first,0);
add(i,e[i].second*e[i].second,1);
add(i,e[i].first*e[i].second,2);
}
while(m--)
{
int op;
scanf("%d",&op);
if(op==1)
{
int p;
long long x,y;
scanf("%d%lld%lld",&p,&x,&y);
add(p,(x*x%mod-e[p].first*e[p].first%mod+mod)%mod,0);
add(p,(y*y%mod-e[p].second*e[p].second%mod+mod)%mod,1);
add(p,(x*y%mod-e[p].first*e[p].second%mod+mod)%mod,2);
e[p]=make_pair(x,y);
}
else
{
int l,r;
scanf("%d%d",&l,&r);
long long res=ask(l,r,0)*ask(l,r,1)%mod,res1=ask(l,r,2);
res=(res-(res1*res1%mod)+mod)%mod;
printf("%lld
",res);
}
}
return 0;
}
rp++