网站建设设计细节,宏发建设有限公司网站,网站网站模版,同步wordpress正题
题目链接:https://jzoj.net/senior/#main/show/4216 题目大意
一个序列要求支持操作
插入一个数区间加上一个数区间求平方和 解题思路
用线段树可以做到区间求平方和。 就是(ab)2a22abb2(ab)^2a^22abb^2(ab)2a22abb2也就是维护区间和平方和和区间个数即可。
但是因为…正题
题目链接:https://jzoj.net/senior/#main/show/4216 题目大意
一个序列要求支持操作
插入一个数区间加上一个数区间求平方和 解题思路
用线段树可以做到区间求平方和。 就是(ab)2a22abb2(ab)^2a^22abb^2(ab)2a22abb2也就是维护区间和平方和和区间个数即可。
但是因为要插入一个数所以我们用SplaySplaySplay维护即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N210000,XJQ7459;
struct Splay_node{struct Tree_node{ll siz,sum,sqr,val,lazy; }a[N];ll t[N][2],fa[N];ll Dicrect(ll x){return (t[fa[x]][1]x);}void Change(ll x,ll z){a[x].sqr2*a[x].sum*zz*z*a[x].siz;a[x].valz;a[x].lazyz;a[x].sumz*a[x].siz;return;}void PushDown(ll x){if(a[x].lazy){Change(t[x][0],a[x].lazy);Change(t[x][1],a[x].lazy);a[x].lazy0;}return;}void PushUp(ll x){a[x].sqra[t[x][0]].sqra[t[x][1]].sqra[x].val*a[x].val;a[x].suma[t[x][0]].suma[t[x][1]].suma[x].val;a[x].siza[t[x][0]].siza[t[x][1]].siz1;}void DownData(ll x){if(!x) return;DownData(fa[x]);PushDown(x);}void Connect(ll x,ll y,ll son){t[y][son]x;fa[x]y;}void Rotate(ll x){ll yfa[x],rootfa[fa[x]];ll ysDicrect(x),rsDicrect(y);ll zt[x][ys^1];Connect(z,y,ys);Connect(y,x,ys^1);Connect(x,root,rs);PushUp(y);PushUp(x);return;}void Splay(ll x,ll f){DownData(x);while(fa[x]!f){ll upfa[x];if(fa[up]f) Rotate(x);else if(Dicrect(x)Dicrect(up))Rotate(up),Rotate(x);else Rotate(x),Rotate(x);}}ll Find(ll x,ll z) {PushDown(x);if(a[t[x][0]].sizz) return Find(t[x][0],z);if(a[t[x][0]].siz1z) return x;return Find(t[x][1],z-a[t[x][0]].siz-1);}
}T;
ll n,root,tot,m;
int main()
{scanf(%lld,n);T.a[1].siz1;for(ll i1;in;i){scanf(%lld,T.a[i1].val);T.fa[i]i1;T.t[i1][0]i;T.PushUp(i1);}T.fa[n1]n2;T.t[n2][0]n1;T.PushUp(n2);roottotn2;scanf(%lld,m);while(m--){char op[8];ll l,r,z;scanf(%s,op);if(op[0]A){scanf(%lld%lld%lld,l,r,z);ll xT.Find(root,l),yT.Find(root,r2);T.Splay(x,0);T.Splay(y,x);rootT.t[y][0];T.Change(T.t[y][0],z);T.Splay(T.t[y][0],0);}if(op[0]Q){scanf(%lld%lld,l,r);ll xT.Find(root,l),yT.Find(root,r2);T.Splay(x,0);T.Splay(y,x);rootx;printf(%lld\n,T.a[T.t[y][0]].sqr%XJQ);}if(op[0]I){scanf(%lld%lld,l,z);ll xT.Find(root,l),yT.Find(root,l1);T.Splay(x,0);T.Splay(y,x);T.fa[tot]y;T.a[tot].siz1;T.a[tot].sqrz*z;T.a[tot].sumT.a[tot].valz;T.t[y][0]tot;T.Splay(tot,0);roottot;}}
}
