天才绅士少女助手克里斯蒂娜 题解【向量内积】【树状数组】

点击量：177

    有点卡常？学会了\(O(n)\)建树状数组。

目录

Description

红莉栖想要弄清楚楼下天王寺大叔的显像管电视对 “电话微波炉 (暂定)” 的影响.

选取显像管的任意一个平面, 一开始平面内有个\(n\)电子, 初始速度分别为\(\mathbf{v}_i\), 定义飘升系数为$$\sum_{1\le i<j\le n}|\mathbf{v}_i\times \mathbf{v}_j|$$

由于电视会遭到大叔不同程度的暴击, 电子的速度常常会发生变化. 也就是说, 有两种类型的操作:

• 1 p x y 将\(\mathbf{v}_p\)改为\((x,y)\)

• 2 l r 询问\([l,r]\)这段区间内的电子的飘升系数

这么简单的问题红莉栖当然能解决, 但是她需要一个人帮忙验证一下结果的正确性.

由于唯一帮得上忙的桶子去找菲利斯了, 于是只能拜托你来完成这个任务了. 答案对\(2017092\)取模即可.

 

Input Format

第一行两个整数\(n,m\)表示电子个数和询问个数.

接下来\(n\)行, 每行两个整数\(x,y\)表示\(\mathbf{v}_i\).

接下来\(m\)行, 每行形如 1 p x y 或 2 l r, 分别表示两种操作.

Output Format

对于每个操作 2, 输出一行一个整数表示飘升系数对\(20170927\)取模的值.

 

Sample

Input

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

Output

18529202
963126
19167545

Constraints

测试点编号	\(n\)	\(m\)
\(1\)	\(\le 100\)	\(\le 100\)
\(2\)	\(\le 500\)	\(\le 500\)
\(3\)	\(\le 1000\)	\(\le 1000\)
\(4\)	\(\le 5000\)	\(\le 5000\)
\(5\)	\(\le 10000\)	\(\le 10000\)
\(6\)	\(\le 50000\)	\(\le 50000\)
\(7\)	\(\le 100000\)	\(\le 100000\)
\(8\)	\(\le 500000\)	\(\le 500000\)
\(9\)	\(\le 1000000\)	\(\le 1000000\)
\(10\)

对于\(100\%\)的数据,\(1\le n, m\le 10^6,0\le x_i,y_i<20170927,1\le l_i\le r_i\le n\).

题解：

    这个题每次询问求的是\((\sum_{l\le i<j\le r}x_iy_j-x_jy_i)^2\)，我们把这个式子拆开得到\(x_i^2y_j^2-2x_ix_jy_iy_j+x_j^2y_i^2\)。

    因为我们要对这区间所有的向量都求一遍这个式子，所以考虑有什么元素是多次出现的。因为在这个式子中，每一项的次数都是\(4\)，所以我们可以找一些二次项乘起来，那么第一项和后面一项就要存每个向量的\(x_i^2,y_i^2\)并维护前缀和。中间一项也比较好办，可以存每个向量的\(x_iy_i\)，维护前缀和。

    在我们查询的时候，发现式子中是没有形如\(x_i^2y_i^2\)这样的项的，但是我们把这些项乘起来，让第一、三项为正，第二、四项为负，就可以把原本产生的\(x_i^2y_i^2\)抵消掉了，同时因为正项系数为\(2\)，负项系数也为\(2\)，相当于没有产生贡献，这样上面\(\sum\)的条件就可以使\(i,j\)取等了。

    这个题由于开了\(10^6\)的大小，\(O(n\log n)\)的复杂度需要非常小的常数，这里因为单点修改，所以树状数组非常方便。但是建树过程太慢，达到\(O(n\log n)\)，还是会被卡常。我们有一个简便的方法，可以使树状数组的初始化做到\(O(n)\)。因为我们知道，树状数组\(c_i\)的表示范围是\((i-\mathrm{lowbit}(i),i]\)，那么我们预处理出前缀和，然后直接赋值即可。这个操作简直不要太神啊

    卡常技巧：尽量少取膜

Code：

#include<cstdio>
#include<cstring>
#define lowbit(x) (x&(-x))
long long p=20170927;
long long c[3][1001000];
int n;
void change(int t,int r,long long x)//哪一项 改在哪 改多少
{
    x=(x%p+p)%p;
    while(r<=n)
    {
        c[t][r]=(c[t][r]+x)%p;
        r+=lowbit(r);
    }
}
long long ask(int t,int r)
{
    long long ans=0;
    while(r)
    {
        ans=ans+c[t][r];
        r-=lowbit(r);
    }
    return ans%p;
}
long long X[1001000],Y[1001000];
long long sum[3][1001000];
int main()
{
    int m,op,u,v;
    long long x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&X[i],&Y[i]);
        sum[0][i]=(sum[0][i-1]+X[i]*Y[i])%p;
        int l=i-lowbit(i);
        c[0][i]=(sum[0][i]-sum[0][l])%p;
        sum[1][i]=(sum[1][i-1]+X[i]*X[i])%p;
        c[1][i]=(sum[1][i]-sum[1][l])%p;
        sum[2][i]=(sum[2][i-1]+Y[i]*Y[i])%p;
        c[2][i]=(sum[2][i]-sum[2][l])%p;
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%lld%lld",&u,&x,&y);
            change(0,u,x*y-X[u]*Y[u]);
            change(1,u,x*x-X[u]*X[u]);
            change(2,u,y*y-Y[u]*Y[u]);
            X[u]=x;
            Y[u]=y;
        }
        else
        {
            scanf("%d%d",&u,&v);
            long long ans=(ask(1,v)-ask(1,u-1))*(ask(2,v)-ask(2,u-1))%p;
            long long tmp=(ask(0,v)-ask(0,u-1))%p;
            ans-=tmp*tmp;
            printf("%lld\n",(ans%p+p)%p);
        }
    }
    return 0;
}