对于$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$

大力化简：

$\large \begin{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 \neq j]*x_i^2y_j^2 - \sum \limits_{i=l}^r \sum \limits_{j=l}^r [i \neq j]*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* \sum \limits_{i=l}^ry_i^2 - (\sum \limits_{i=l}^r x_iy_i)^2\end{array}$

然后开三个树状数组分别维护${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]电子速度题解

$Solution:$

最新文章

热门文章

巴特西

[信息学奥赛一本通oj1741]电子速度 题解

$Solution:$

最新文章

热门文章

[信息学奥赛一本通oj1741]电子速度题解