【NOIP2017提高A组集训10.25】天才绅士少女助手克里斯蒂娜（树状数组）

树状数组）"/>

【NOIP2017提高A组集训10.25】天才绅士少女助手克里斯蒂娜（树状数组）

Description

Input

第一行两个整数n;m 表示电子个数和询问个数.
接下来n 行, 每行两个整数x; y 表示vi.
接下来m 行, 每行形如1 p x y 或2 l r, 分别表示两种操作.

Output

对于每个操作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

Sample Output

18529202
963126
19167545

Data Constraint

题解

首先，那个 vi∗vj $v_i*v_j$其实就是 xiyj−xjyi $x_iy_j-x_jy_i$
然后就用完全平方公式展开那个式子，再化简一下：
∑x2i∗∑y2i+∑xiyi $\sum x_i^2*\sum y_i^2+\sum x_iy_i$
然后树状数组维护这三个前缀和就好了。
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<vector>
#define ll long long
using namespace std;
inline int read(){int x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
const ll p=20170927;
int n,m;
ll x[1000001],y[1000001];
ll x2[1000001],y2[1000001],xy[1000001];
inline void update(int a,ll b,ll c){ll xx=x[a],yy=y[a];int tmp =a;while(a<=n){x2[a]=(x2[a]-(xx*xx)%p+p)%p;y2[a]=(y2[a]-(yy*yy)%p+p)%p;xy[a]=(xy[a]-(xx*yy)%p+p)%p;a+=a&-a;}xx=b;yy=c;a = tmp;while(a<=n){x2[a]=(x2[a]+(xx*xx)%p)%p;y2[a]=(y2[a]+(yy*yy)%p)%p;xy[a]=(xy[a]+(xx*yy)%p)%p;a+=a&-a;}
}
inline ll query(int l,int r){ll sumx2=0,sumy2=0,sumxy=0;while(r){sumx2=(sumx2+x2[r])%p;sumy2=(sumy2+y2[r])%p;sumxy=(sumxy+xy[r])%p;r-=r&-r;}l--;while(l){sumx2=(sumx2-x2[l]+p)%p;sumy2=(sumy2-y2[l]+p)%p;sumxy=(sumxy-xy[l]+p)%p;l-=l&-l;}ll ans=(sumx2*sumy2)%p;ans=(ans-(sumxy*sumxy)%p+p)%p;return ans;
}
int main(){freopen("kurisu.in","r",stdin);freopen("kurisu.out","w",stdout);n=read();m=read();for(int i=1;i<=n;i++){x[i]=read();y[i]=read();int a=i;ll xx=x[i],yy=y[i];while(a<=n){x2[a]=(x2[a]+(xx*xx)%p)%p;y2[a]=(y2[a]+(yy*yy)%p)%p;xy[a]=(xy[a]+(xx*yy)%p)%p;a+=a&-a;}}while(m--){ll opt=read(),a=read(),b=read();if(opt==1){ll c=read();update(a,b,c);x[a]=b;y[a]=c;}else{printf("%lld\n",query(a,b));}}return 0;
}