[2017纪中10-25]天才绅士少女助手克里斯蒂娜线段树

本文主要是介绍[2017纪中10-25]天才绅士少女助手克里斯蒂娜线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面
这里写图片描述
线段树维护三个∑即可。
AC的里面跑的最慢的。。。好像因为每次query了三下。
代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int mod=20170927;
const int maxn=1000010;
int n,m;
ll v[maxn][2];
int read()
{int x=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x;
}
struct tree
{int l,r;ll s[3];tree *ls,*rs;tree(){l=r=s[0]=s[1]=s[2]=0;ls=rs=NULL;}   void update(){for(int i=0;i<=2;i++)s[i]=(ls->s[i]+rs->s[i])%mod;}void init(int p){for(int i=0;i<=1;i++)s[i]=v[p][i]*v[p][i]%mod;s[2]=v[p][0]*v[p][1]%mod;   }void build(int lx,int rx){l=lx;r=rx;if(l==r) {init(l); return;}int mid=(l+r)>>1;(ls=new tree)->build(lx,mid);(rs=new tree)->build(mid+1,rx);update();}void mdf(int pl){if(l==r) {init(pl);return;}int mid=(l+r)>>1;if(pl<=mid) ls->mdf(pl);else rs->mdf(pl);update();}ll query(int lx,int rx,int f){if(l==lx&&r==rx) return s[f];int mid=(l+r)>>1;if(rx<=mid) return ls->query(lx,rx,f);else if(lx>mid) return rs->query(lx,rx,f);else return (ls->query(lx,mid,f)+rs->query(mid+1,rx,f))%mod;}
}*xtr;
ll calc(int l,int r)
{ll q0=xtr->query(l,r,0),q1=xtr->query(l,r,1),q2=xtr->query(l,r,2);return (q0*q1%mod-q2*q2%mod+mod)%mod;
}
int main()
{n=read();m=read();for(int i=1;i<=n;i++){v[i][0]=read();v[i][1]=read();}(xtr=new tree)->build(1,n);while(m--){int opt=read(),p=read(),x=read(),y;if(opt==1){y=read();v[p][0]=x;v[p][1]=y;xtr->mdf(p);}if(opt==2){printf("%lld\n",calc(p,x));}}return 0;
}