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

时间:2022-08-29 18:09:27

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

  1. Print operation l, r. Picks should write down the value of CF(438D) The Child and Sequence(线段树).
  2. Modulo operation l, r, x. Picks should perform assignment a[i] = a[imod x for
    each i (l ≤ i ≤ r).
  3. Set operation k, x. Picks should set the value of a[k] to x (in
    other words perform an assignment a[k] = x).

解法:线段树更新。维护区间最大值ma和区间sum。假设訪问的x小于ma就能够忽略。否则向下更新;

代码:  
/******************************************************
* 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(线段树)的更多相关文章

  1. 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 ...

  2. CodeForces 438D The Child and Sequence &lpar;线段树 暴力&rpar;

    传送门 题目大意: 给你一个序列,要求在序列上维护三个操作: 1)区间求和 2)区间取模 3)单点修改 这里的操作二很讨厌,取模必须模到叶子节点上,否则跑出来肯定是错的.没有操作二就是线段树水题了. ...

  3. Codeforces Round &num;250 &lpar;Div&period; 1&rpar; D&period; The Child and Sequence 线段树 区间取摸

    D. The Child and Sequence Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/contest ...

  4. Codeforces Round &num;250 &lpar;Div&period; 1&rpar; D&period; The Child and Sequence 线段树 区间求和&plus;点修改&plus;区间取模

    D. The Child and Sequence   At the children's day, the child came to Picks's house, and messed his h ...

  5. cf250D&period; The Child and Sequence&lpar;线段树 均摊复杂度&rpar;

    题意 题目链接 单点修改,区间mod,区间和 Sol 如果x > mod ,那么 x % mod < x / 2 证明: 即得易见平凡, 仿照上例显然, 留作习题答案略, 读者自证不难. ...

  6. Codeforces Round &num;250 &lpar;Div&period; 1&rpar; D&period; The Child and Sequence &lpar;线段树&rpar;

    题目链接:http://codeforces.com/problemset/problem/438/D 给你n个数,m个操作,1操作是查询l到r之间的和,2操作是将l到r之间大于等于x的数xor于x, ...

  7. CF438D The Child and Sequence 线段树

    给定数列,区间查询和,区间取模,单点修改. n,m小于10^5 ...当区间最值小于模数时,就直接返回就好啦~ #include<cstdio> #include<iostream& ...

  8. 2016暑假多校联合---Rikka with Sequence &lpar;线段树&rpar;

    2016暑假多校联合---Rikka with Sequence (线段树) Problem Description As we know, Rikka is poor at math. Yuta i ...

  9. 2018&period;07&period;23 codeforces 438D&period; The Child and Sequence(线段树)

    传送门 线段树维护区间取模,单点修改,区间求和. 这题老套路了,对一个数来说,每次取模至少让它减少一半,这样每次单点修改对时间复杂度的贡献就是一个log" role="presen ...

随机推荐

  1. 如何根据执行计划,判断Mysql语句是否走索引

    如何根据执行计划,判断Mysql语句是否走索引

  2. angular学习笔记,很乱哈哈。

    1.鼠标悬浮出现的信息v-bind:title="message" 2.对该便签进行结果判断显示隐藏v-if=''控制台设置 app3.seen = false(消失).控制台设置 ...

  3. 使用Nginx在自己的电脑上实现负载均衡

    我其实早就想弄这个负载均衡了,但是总觉得这玩意肯定不简单,今天星期六闲着没事终于下定决心来搞一搞他了,但是没想到这玩意这么简单,真的是出乎我的意料的简单(我现在陪的是最简单的那种).额是没有我想象中的 ...

  4. php防止sql注入

    [一.在服务器端配置] 安全,PHP代码编写是一方面,PHP的配置更是非常关键. 我们php手手工安装的,php的默认配置文件在 /usr/local/apache2/conf/php.ini,我们最 ...

  5. hdu 1026 Ignatius and the Princess I&lpar;优先队列&plus;bfs&plus;记录路径&rpar;

    以前写的题了,现在想整理一下,就挂出来了. 题意比较明确,给一张n*m的地图,从左上角(0, 0)走到右下角(n-1, m-1). 'X'为墙,'.'为路,数字为怪物.墙不能走,路花1s经过,怪物需要 ...

  6. 阿里云API网关(6)用户指南(开放 API )

    网关指南: https://help.aliyun.com/document_detail/29487.html?spm=5176.doc48835.6.550.23Oqbl 网关控制台: https ...

  7. 在Vuex更新,组件内的视图更新问题

    由于js的限制,vue无法进行监听数组; 当你利用索引直接设置一个项时,例如: vm.items[indexOfItem] = newValue 当你修改数组的长度时,例如: vm.items.len ...

  8. CentOS7&period;4安装配置mysql8 TAR免安装版

    下载mysql: https://dev.mysql.com/downloads/mysql/ 解压tar.xz文件:先 xz -d mysql-8.0.15-linux-glibc2.12-x86_ ...

  9. 【代码审计】XYHCMS V3&period;5任意文件读取漏洞分析

      0x00 环境准备 XYHCMS官网:http://www.xyhcms.com/ 网站源码版本:XYHCMS V3.5(2017-12-04 更新) 程序源码下载:http://www.xyhc ...

  10. node&period;js基本使用

    1.引入http模块(node的核心模块) const http = require("http"); 2.createServer来创建服务器 http.createServer ...