Write an API that generates fancy sequences using the append, addAll, and multAll operations.
Implement the Fancy class:
Fancy() Initializes the object with an empty sequence.
void append(val) Appends an integer val to the end of the sequence.
void addAll(inc) Increments all existing values in the sequence by an integer inc.
void multAll(m) Multiplies all existing values in the sequence by an integer m.
int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo109 + 7. If the index is greater or equal than the length of the sequence, return -1.
MOD=int(1e9+7)classNode:def__init__(self,l,r):self.left=Noneself.right=Noneself.l=lself.r=rself.mid=(l+r)>>1self.v=0self.add=0self.mul=1classSegmentTree:def__init__(self):self.root=Node(1,int(1e5+1))defmodifyAdd(self,l,r,inc,node=None):ifl>r:returnifnodeisNone:node=self.rootifnode.l>=landnode.r<=r:node.v=(node.v+(node.r-node.l+1)*inc)%MODnode.add+=increturnself.pushdown(node)ifl<=node.mid:self.modifyAdd(l,r,inc,node.left)ifr>node.mid:self.modifyAdd(l,r,inc,node.right)self.pushup(node)defmodifyMul(self,l,r,m,node=None):ifl>r:returnifnodeisNone:node=self.rootifnode.l>=landnode.r<=r:node.v=(node.v*m)%MODnode.add=(node.add*m)%MODnode.mul=(node.mul*m)%MODreturnself.pushdown(node)ifl<=node.mid:self.modifyMul(l,r,m,node.left)ifr>node.mid:self.modifyMul(l,r,m,node.right)self.pushup(node)defquery(self,l,r,node=None):ifl>r:return0ifnodeisNone:node=self.rootifnode.l>=landnode.r<=r:returnnode.vself.pushdown(node)v=0ifl<=node.mid:v=(v+self.query(l,r,node.left))%MODifr>node.mid:v=(v+self.query(l,r,node.right))%MODreturnvdefpushup(self,node):node.v=(node.left.v+node.right.v)%MODdefpushdown(self,node):ifnode.leftisNone:node.left=Node(node.l,node.mid)ifnode.rightisNone:node.right=Node(node.mid+1,node.r)left,right=node.left,node.rightifnode.add!=0ornode.mul!=1:left.v=(left.v*node.mul+(left.r-left.l+1)*node.add)%MODright.v=(right.v*node.mul+(right.r-right.l+1)*node.add)%MODleft.add=(left.add*node.mul+node.add)%MODright.add=(right.add*node.mul+node.add)%MODleft.mul=(left.mul*node.mul)%MODright.mul=(right.mul*node.mul)%MODnode.add=0node.mul=1classFancy:def__init__(self):self.n=0self.tree=SegmentTree()defappend(self,val:int)->None:self.n+=1self.tree.modifyAdd(self.n,self.n,val)defaddAll(self,inc:int)->None:self.tree.modifyAdd(1,self.n,inc)defmultAll(self,m:int)->None:self.tree.modifyMul(1,self.n,m)defgetIndex(self,idx:int)->int:return-1ifidx>=self.nelseself.tree.query(idx+1,idx+1)# Your Fancy object will be instantiated and called as such:# obj = Fancy()# obj.append(val)# obj.addAll(inc)# obj.multAll(m)# param_4 = obj.getIndex(idx)
classNode{Nodeleft;Noderight;intl;intr;intmid;longv;longadd;longmul=1;publicNode(intl,intr){this.l=l;this.r=r;this.mid=(l+r)>>1;}}classSegmentTree{privateNoderoot=newNode(1,(int)1e5+1);privatestaticfinalintMOD=(int)1e9+7;publicSegmentTree(){}publicvoidmodifyAdd(intl,intr,intinc){modifyAdd(l,r,inc,root);}publicvoidmodifyAdd(intl,intr,intinc,Nodenode){if(l>r){return;}if(node.l>=l&&node.r<=r){node.v=(node.v+(node.r-node.l+1)*inc)%MOD;node.add=(node.add+inc)%MOD;return;}pushdown(node);if(l<=node.mid){modifyAdd(l,r,inc,node.left);}if(r>node.mid){modifyAdd(l,r,inc,node.right);}pushup(node);}publicvoidmodifyMul(intl,intr,intm){modifyMul(l,r,m,root);}publicvoidmodifyMul(intl,intr,intm,Nodenode){if(l>r){return;}if(node.l>=l&&node.r<=r){node.v=(node.v*m)%MOD;node.add=(node.add*m)%MOD;node.mul=(node.mul*m)%MOD;return;}pushdown(node);if(l<=node.mid){modifyMul(l,r,m,node.left);}if(r>node.mid){modifyMul(l,r,m,node.right);}pushup(node);}publicintquery(intl,intr){returnquery(l,r,root);}publicintquery(intl,intr,Nodenode){if(l>r){return0;}if(node.l>=l&&node.r<=r){return(int)node.v;}pushdown(node);intv=0;if(l<=node.mid){v=(v+query(l,r,node.left))%MOD;}if(r>node.mid){v=(v+query(l,r,node.right))%MOD;}returnv;}publicvoidpushup(Nodenode){node.v=(node.left.v+node.right.v)%MOD;}publicvoidpushdown(Nodenode){if(node.left==null){node.left=newNode(node.l,node.mid);}if(node.right==null){node.right=newNode(node.mid+1,node.r);}if(node.add!=0||node.mul!=1){Nodeleft=node.left,right=node.right;left.v=(left.v*node.mul+(left.r-left.l+1)*node.add)%MOD;right.v=(right.v*node.mul+(right.r-right.l+1)*node.add)%MOD;left.add=(left.add*node.mul+node.add)%MOD;right.add=(right.add*node.mul+node.add)%MOD;left.mul=(left.mul*node.mul)%MOD;right.mul=(right.mul*node.mul)%MOD;node.add=0;node.mul=1;}}}classFancy{privateintn;privateSegmentTreetree=newSegmentTree();publicFancy(){}publicvoidappend(intval){++n;tree.modifyAdd(n,n,val);}publicvoidaddAll(intinc){tree.modifyAdd(1,n,inc);}publicvoidmultAll(intm){tree.modifyMul(1,n,m);}publicintgetIndex(intidx){returnidx>=n?-1:tree.query(idx+1,idx+1);}}/** * Your Fancy object will be instantiated and called as such: * Fancy obj = new Fancy(); * obj.append(val); * obj.addAll(inc); * obj.multAll(m); * int param_4 = obj.getIndex(idx); */
constintMOD=1e9+7;classNode{public:Node*left;Node*right;intl;intr;intmid;longlongv;longlongadd;longlongmul;Node(intl,intr){this->l=l;this->r=r;this->mid=(l+r)>>1;this->left=this->right=nullptr;v=add=0;mul=1;}};classSegmentTree{private:Node*root;public:SegmentTree(){root=newNode(1,1e5+1);}voidmodifyAdd(intl,intr,intinc){modifyAdd(l,r,inc,root);}voidmodifyAdd(intl,intr,intinc,Node*node){if(l>r)return;if(node->l>=l&&node->r<=r){node->v=(node->v+(node->r-node->l+1)*inc)%MOD;node->add=(node->add+inc)%MOD;return;}pushdown(node);if(l<=node->mid)modifyAdd(l,r,inc,node->left);if(r>node->mid)modifyAdd(l,r,inc,node->right);pushup(node);}voidmodifyMul(intl,intr,intm){modifyMul(l,r,m,root);}voidmodifyMul(intl,intr,intm,Node*node){if(l>r)return;if(node->l>=l&&node->r<=r){node->v=(node->v*m)%MOD;node->add=(node->add*m)%MOD;node->mul=(node->mul*m)%MOD;return;}pushdown(node);if(l<=node->mid)modifyMul(l,r,m,node->left);if(r>node->mid)modifyMul(l,r,m,node->right);pushup(node);}intquery(intl,intr){returnquery(l,r,root);}intquery(intl,intr,Node*node){if(l>r)return0;if(node->l>=l&&node->r<=r)returnnode->v;pushdown(node);intv=0;if(l<=node->mid)v=(v+query(l,r,node->left))%MOD;if(r>node->mid)v=(v+query(l,r,node->right))%MOD;returnv;}voidpushup(Node*node){node->v=(node->left->v+node->right->v)%MOD;}voidpushdown(Node*node){if(!node->left)node->left=newNode(node->l,node->mid);if(!node->right)node->right=newNode(node->mid+1,node->r);if(node->add||node->mul!=1){longadd=node->add,mul=node->mul;Node*left=node->left;Node*right=node->right;left->v=(left->v*mul+(left->r-left->l+1)*add)%MOD;right->v=(right->v*mul+(right->r-right->l+1)*add)%MOD;left->add=(left->add*mul+add)%MOD;right->add=(right->add*mul+add)%MOD;left->mul=(left->mul*mul)%MOD;right->mul=(right->mul*mul)%MOD;node->add=0;node->mul=1;}}};classFancy{public:intn;SegmentTree*tree;Fancy(){n=0;tree=newSegmentTree();}voidappend(intval){++n;tree->modifyAdd(n,n,val);}voidaddAll(intinc){tree->modifyAdd(1,n,inc);}voidmultAll(intm){tree->modifyMul(1,n,m);}intgetIndex(intidx){returnidx>=n?-1:tree->query(idx+1,idx+1);}};/** * Your Fancy object will be instantiated and called as such: * Fancy* obj = new Fancy(); * obj->append(val); * obj->addAll(inc); * obj->multAll(m); * int param_4 = obj->getIndex(idx); */