题意:对数列有三种操作:
- 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 for
each i (l ≤ i ≤ r). - Set operation k, x. Picks should set the value of a[k] to x (in
other words perform an assignment a[k] = x).
/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//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<x)
return;
if(p->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<<query(nodes,l,r)<<endl;
}
else if(t==2)
{
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
update2(nodes,l,r,x);
}
else if(t==3)
{
int i,x;
scanf("%d%d",&i,&x);
update(nodes,i,x);
}
}
}
return 0;
}
CF(438D) The Child and Sequence(线段树)的更多相关文章
-
Codeforces 438D The Child and Sequence - 线段树
At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at ...
-
CodeForces 438D The Child and Sequence (线段树 暴力)
传送门 题目大意: 给你一个序列,要求在序列上维护三个操作: 1)区间求和 2)区间取模 3)单点修改 这里的操作二很讨厌,取模必须模到叶子节点上,否则跑出来肯定是错的.没有操作二就是线段树水题了. ...
-
Codeforces Round #250 (Div. 1) D. The Child and Sequence 线段树 区间取摸
D. The Child and Sequence Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest ...
-
Codeforces Round #250 (Div. 1) D. The Child and Sequence 线段树 区间求和+点修改+区间取模
D. The Child and Sequence At the children's day, the child came to Picks's house, and messed his h ...
-
cf250D. The Child and Sequence(线段树 均摊复杂度)
题意 题目链接 单点修改,区间mod,区间和 Sol 如果x > mod ,那么 x % mod < x / 2 证明: 即得易见平凡, 仿照上例显然, 留作习题答案略, 读者自证不难. ...
-
Codeforces Round #250 (Div. 1) D. The Child and Sequence (线段树)
题目链接:http://codeforces.com/problemset/problem/438/D 给你n个数,m个操作,1操作是查询l到r之间的和,2操作是将l到r之间大于等于x的数xor于x, ...
-
CF438D The Child and Sequence 线段树
给定数列,区间查询和,区间取模,单点修改. n,m小于10^5 ...当区间最值小于模数时,就直接返回就好啦~ #include<cstdio> #include<iostream& ...
-
2016暑假多校联合---Rikka with Sequence (线段树)
2016暑假多校联合---Rikka with Sequence (线段树) Problem Description As we know, Rikka is poor at math. Yuta i ...
-
2018.07.23 codeforces 438D. The Child and Sequence(线段树)
传送门 线段树维护区间取模,单点修改,区间求和. 这题老套路了,对一个数来说,每次取模至少让它减少一半,这样每次单点修改对时间复杂度的贡献就是一个log" role="presen ...
随机推荐
-
如何根据执行计划,判断Mysql语句是否走索引
如何根据执行计划,判断Mysql语句是否走索引
-
angular学习笔记,很乱哈哈。
1.鼠标悬浮出现的信息v-bind:title="message" 2.对该便签进行结果判断显示隐藏v-if=''控制台设置 app3.seen = false(消失).控制台设置 ...
-
使用Nginx在自己的电脑上实现负载均衡
我其实早就想弄这个负载均衡了,但是总觉得这玩意肯定不简单,今天星期六闲着没事终于下定决心来搞一搞他了,但是没想到这玩意这么简单,真的是出乎我的意料的简单(我现在陪的是最简单的那种).额是没有我想象中的 ...
-
php防止sql注入
[一.在服务器端配置] 安全,PHP代码编写是一方面,PHP的配置更是非常关键. 我们php手手工安装的,php的默认配置文件在 /usr/local/apache2/conf/php.ini,我们最 ...
-
hdu 1026 Ignatius and the Princess I(优先队列+bfs+记录路径)
以前写的题了,现在想整理一下,就挂出来了. 题意比较明确,给一张n*m的地图,从左上角(0, 0)走到右下角(n-1, m-1). 'X'为墙,'.'为路,数字为怪物.墙不能走,路花1s经过,怪物需要 ...
-
阿里云API网关(6)用户指南(开放 API )
网关指南: https://help.aliyun.com/document_detail/29487.html?spm=5176.doc48835.6.550.23Oqbl 网关控制台: https ...
-
在Vuex更新,组件内的视图更新问题
由于js的限制,vue无法进行监听数组; 当你利用索引直接设置一个项时,例如: vm.items[indexOfItem] = newValue 当你修改数组的长度时,例如: vm.items.len ...
-
CentOS7.4安装配置mysql8 TAR免安装版
下载mysql: https://dev.mysql.com/downloads/mysql/ 解压tar.xz文件:先 xz -d mysql-8.0.15-linux-glibc2.12-x86_ ...
-
【代码审计】XYHCMS V3.5任意文件读取漏洞分析
0x00 环境准备 XYHCMS官网:http://www.xyhcms.com/ 网站源码版本:XYHCMS V3.5(2017-12-04 更新) 程序源码下载:http://www.xyhc ...
-
node.js基本使用
1.引入http模块(node的核心模块) const http = require("http"); 2.createServer来创建服务器 http.createServer ...