【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

Solution

求 ∑i,jai∗bj−aj∗bi $\sum _{i,j}ai*bj-aj*bi$
相当于求 (∑iai2)(∑iaj2)−(∑iaiaj) $(\sum _{i}ai^2)(\sum _{i}aj^2)-(\sum _{i}aiaj)$
然后……就没了

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define lowbit(a) ((a)&(-(a)))
#define ll long long
#define N 1001000
#define mo 20170927
using namespace std;
ll a[N][2],t[3][N];
int n,m;
ll sqr(ll x){x%=mo;return x*x%mo;}
void ins(int q,int x,ll z)
{(z+=mo)%=mo;for(;x<=n;x+=lowbit(x)) (t[q][x]+=z)%=mo;
}
ll get(int q,int x)
{ll ans=0;for(;x;x-=lowbit(x)) (ans+=t[q][x])%=mo;return ans;
}
int main()
{freopen("kurisu.in","r",stdin);freopen("kurisu.out","w",stdout);scanf("%d%d",&n,&m);fo(i,1,n){scanf("%d%d",&a[i][0],&a[i][1]);ins(0,i,sqr(a[i][0]));ins(1,i,sqr(a[i][1]));ins(2,i,a[i][0]*a[i][1]);}for(;m;m--){int k;ll x,y;scanf("%d%lld%lld",&k,&x,&y);if(k==1){ll p;scanf("%lld",&p);swap(p,x);swap(x,y);ins(0,p,sqr(x)-sqr(a[p][0]));ins(1,p,sqr(y)-sqr(a[p][1]));ins(2,p,x*y-a[p][0]*a[p][1]);a[p][0]=x;a[p][1]=y;}else{ll ans=(get(0,y)-get(0,x-1)+mo)%mo;ans=(ans*((get(1,y)-get(1,x-1)+mo)%mo))%mo;ans=(ans-sqr(get(2,y)-get(2,x-1)+mo)%mo+mo)%mo;printf("%lld\n",ans);}}
}