对于 $100 \%$ 的数据,$1≤n,m≤1e6 \ \ \ 0<=x_i,y_i<20170927 \ \ \ 1≤l_i,r_i≤n $
$Solution:$
一开始没看懂题. 后来大致理解了一下, 所谓的 v 是一个二维向量, 有 x 和 y 两个参数. 那个 $\times$ 是叉乘, 即 $(x_i y_j-x_j y_i)$.
所以题意就是给你一个 x 序列和 y 序列, 对于每次询问的区间 $[l,r]$, 求 $\sum \limits _{l\leq i<j \leq r}(x_iy_j-x_jy_i)^2$. 带修.
点对的形式比较麻烦, 尝试化成单点的柿子:
先拆平方:
$\sum \limits _{l\leq i<j \leq r}x_i^2y_j^2-2x_ix_jy_iy_j+x_j^2y_i^2$
遍历每个点对就相当与计入每个点的贡献. 所以:
$\sum \limits_{i=l}^r x_i^2 \sum \limits _{i=l}^r y_i^2- (\sum \limits_{i=l}^r x_iy_i)^2$
然后开三个树状数组分别维护 ${x_i}^2,{y_i}^2,x_i y_i$ 即可.
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- using namespace std;
- #define pa pair<ll,ll>
- typedef long long ll;
- const ll mod=20170927;
- ll read()
- {
- int x=0,f=1;char ch=getchar();
- while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
- while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
- return x*f;
- }
- const int N=1e6+5;
- int n,m;
- ll c[3][N];
- pa v[N];
- int lb(int x){return x&-x;}
- void add(int x,ll val,int id)
- {
- for( ;x<=n;x+=lb(x))
- c[id][x]+=val,(c[id][x]+=mod)%=mod;
- }
- ll query(int x,int id)
- {
- ll res=0;
- for( ;x;x-=lb(x))
- (res+=c[id][x])%=mod;
- return (res+mod)%mod;
- }
- ll ask(int l,int r,int id)
- {
- return (query(r,id)-query(l-1,id)+mod)%mod;
- }
- int main()
- {
- n=read();m=read();
- for(int i=1;i<=n;i++)
- {
- v[i].first=read(),v[i].second=read();
- add(i,v[i].first*v[i].first,0);
- add(i,v[i].second*v[i].second,1);
- add(i,v[i].first*v[i].second,2);
- }
- while(m--)
- {
- int op=read();
- if(op==1)
- {
- int pos=read();
- ll x=read(),y=read();
- add(pos,x*x-v[pos].first*v[pos].first,0);
- add(pos,y*y-v[pos].second*v[pos].second,1);
- add(pos,x*y-v[pos].first*v[pos].second,2);
- v[pos].first=x;v[pos].second=y;
- }
- if(op==2)
- {
- int l=read(),r=read();
- ll res=ask(l,r,0)*ask(l,r,1)%mod,res1=ask(l,r,2);
- res=(res-(res1*res1%mod)+mod)%mod;
- printf("%lld\n",res);
- }
- }
- return 0;
- }
[信息学奥赛一本通 oj1741] 电子速度 题解
来源: http://www.bubuko.com/infodetail-3219443.html