CF(438D) The Child and Sequence(线段树) - c++编程基础

TOP

CF(438D) The Child and Sequence(线段树)

2015-07-24 06:51:51 来源: 作者: 【大中小】浏览:59次

题意：对数列有三种操作：

Print operation l,?r. Picks should write down the value of $\$ .
Modulo operation l,?r,?x. Picks should perform assignment a[i]?=?a[i] mod x fZ??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcgogZWFjaCA8ZW0+aTwvZW0+ICg8ZW0+bDwvZW0+P6HcPzxlbT5pPC9lbT4/odw/PGVtPnI8L2VtPikuPGxpPgpTZXQgb3BlcmF0aW9uIDxlbT5rPC9lbT4sPzxlbT54PC9lbT4uIFBpY2tzIHNob3VsZCBzZXQgdGhlIHZhbHVlIG9mIDxlbT5hPC9lbT5bPGVtPms8L2VtPl0gdG8gPGVtPng8L2VtPiAoaW4KIG90aGVyIHdvcmRzIHBlcmZvcm0gYW4gYXNzaWdubWVudCA8ZW0+YTwvZW0+WzxlbT5rPC9lbT5dPz0/PGVtPng8L2VtPikuCjxicj4KCr3it6ijus/fts7K97j80MKho86su6TH+Lzk1+608yYjMjA1NDA7bWG6zcf4vORzdW2ho8jnufu3w87KtcR40KHT2m1hvs2/ydLUuvbC1KOst/HU8s/yz8K4/NDCo7sKPGJyPgoKtPrC66O6PHByZSBjbGFzcz0="brush:java;">/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include #include //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=100100*2; const int INF=1000000007; struct node { int l,r; node * left,*right; int ma; LL sum; } nodes[Max]; int Mid(node* p) { return (p->l+p->r)/2; } int tot=0; void buildtree(node* p,int left,int right) { p->l=left; p->r=right; p->ma=0; p->sum=0; if(left==right) return ; int mid=(left+right)/2; tot++; p->left=nodes+tot; buildtree(p->left,left,mid); tot++; p->right=nodes+tot; buildtree(p->right,mid+1,right); } void update(node* p,int i,int value) { if(p->l==i&&p->r==i) { p->sum=value; p->ma=value; return ; } int mid=Mid(p); if(i<=mid) update(p->left,i,value); else update(p->right,i,value); p->sum=p->left->sum+p->right->sum; p->ma=max(p->left->ma,p->right->ma); } void update2(node* p,int l,int r,int x) { if(p->ma l==l&&p->r==r&&l==r) { p->sum%=x; p->ma=p->sum; return ; } int mid=Mid(p); if(r<=mid) update2(p->left,l,r,x); else if(l>mid) update2(p->right,l,r,x); else { update2(p->left,l,mid,x); update2(p->right,mid+1,r,x); } p->sum=p->left->sum+p->right->sum; p->ma=max(p->left->ma,p->right->ma); } LL query(node* p,int l,int r) { if(l==p->l&&r==p->r) { return p->sum; } int mid=Mid(p); if(r<=mid) return query(p->left,l,r); if(l>mid) return query(p->right,l,r); return query(p->left,l,mid)+query(p->right,mid+1,r);; } int n,m; int main() { while(scanf("%d%d",&n,&m)==2) { tot=0; buildtree(nodes,0,n+1); for(int i=1; i<=n; i++) { int a; scanf("%d",&a); update(nodes,i,a); } while(m--) { int t; scanf("%d",&t); if(t==1) { int l,r; scanf("%d%d",&l,&r); cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：CF(437C)The Child and Toy(贪心)	下一篇：从零单排PAT1015,1016,1017,1018

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: