题解：P6588 『JROI-1』 向量

· · 题解

显而易见，这是一道线段树的题，并且是单点修改，区间查询。
操作一道操作三均为线段树基本操作，这里不展开讲了。
操作四和操作五不好直接推导，所以我们可以从线段树的角度下手。
对于一个区间 [l,r]，它的左右儿子分别为 [l,mid] 和 [mid+1,r]，如果我们要计算这个区间的点积，也就是 \sum\limits_{i=l}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}，那么我们可以按 \overrightarrow{a_i} 和 \overrightarrow{a_j} 所在线段树内的位置将它们分为三类：

  1. 两个向量都在左区间。那么它们的值就是 \sum\limits_{i=l}^{mid-1}\sum\limits_{j=i+1}^{mid}\overrightarrow{a_i}\cdot\overrightarrow{a_j}；
  2. 两个向量都在右区间。那么它们的值就是 \sum\limits_{i=mid+1}^{r-1}\sum\limits_{j=i+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}；
  3. 一个点在左区间，一个点在右区间。这些点的值为 \sum\limits_{i=l}^{mid}\sum\limits_{j=mid+1}^{r}\overrightarrow{a_i}\cdot\overrightarrow{a_j}。这时因为 \overrightarrow{a_i} 和 \overrightarrow{a_j} 是独立的，可以进一步将式子变形成 \left(\sum\limits_{i=l}^{mid}x_i\right)\cdot\left(\sum\limits_{j=mid+1}^{r}x_j\right)+\left(\sum\limits_{i=l}^{mid} y_i\right)\cdot\left(\sum\limits_{j=mid+1}^{r}y_j\right)。这里因为每一个求和都是独立的，所以可以直接用左右儿子的区间和算出来。

最后递归合并即可。叉积同理。
submission

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
struct node{
    int l,r,x,y,dot,cross;
}t[maxn<<2];
struct node1{
    int x,y;
}a[maxn];
int n,m;
node pushup(node L,node R){
    node res;
    res.l=L.l,res.r=R.r;
    res.x=L.x+R.x,res.y=L.y+R.y;
    res.dot=L.dot+R.dot+L.x*R.x+L.y*R.y;
    res.cross=L.cross+R.cross+L.x*R.y-L.y*R.x;
    return res;
}
void build(int p,int l,int r){
    t[p].l=l,t[p].r=r,t[p].dot=t[p].cross=0;
    if(l==r){
        t[p].x=a[l].x,t[p].y=a[l].y;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    t[p]=pushup(t[p<<1],t[p<<1|1]);
}
void add(int p,int x,node1 k){
    if(t[p].l==t[p].r){

        t[p].x+=k.x,t[p].y+=k.y;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)add(p<<1,x,k);
    else add(p<<1|1,x,k);
    t[p]=pushup(t[p<<1],t[p<<1|1]);
}
void mul(int p,int x,int k){
    if(t[p].l==t[p].r){
        t[p].x*=k,t[p].y*=k;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(x<=mid)mul(p<<1,x,k);
    else mul(p<<1|1,x,k);
    t[p]=pushup(t[p<<1],t[p<<1|1]);
}
node query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r)return t[p];
    int mid=t[p].l+t[p].r>>1;
    if(r<=mid)return query(p<<1,l,r);
    if(l>mid)return query(p<<1|1,l,r);
    return pushup(query(p<<1,l,r),query(p<<1|1,l,r));
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    build(1,1,n);
    while(m--){
        int op,i,tt,l,r;
        node1 k;
        cin>>op;
        if(op==1){
            cin>>i>>k.x>>k.y;
            add(1,i,k);
        }else if(op==2){
            cin>>i>>k.x>>k.y;
            k.x=-k.x,k.y=-k.y;
            add(1,i,k);
        }else if(op==3){
            cin>>i>>tt;
            mul(1,i,tt);
        }else if(op==4){
            cin>>l>>r;
            cout<<query(1,l,r).dot<<"\n";
        }else if(op==5){
            cin>>l>>r;
            cout<<query(1,l,r).cross<<"\n";
        }
    }
}