首页 > 其他分享 >D. The Child and Sequence

D. The Child and Sequence

时间:2022-10-19 23:44:44浏览次数:81  
标签:取模 Sequence int long Child define

题目链接

D. The Child and Sequence

给定数列,区间查询和,区间取模,单点修改。
\( n, m \leq 10^5 \)

解题思路

势能线段树

线段树维护一个最大值 \(mx\),对 \(x\) 取模时,当 \(mx>=x\) 时才递归取模,且对某个数 \(v\) 取模来说,其值至少会减少一半,即 \(log(v)\) 次后不会递归到该节点,类似于区间开方

  • 时间复杂度:\(O(m\times nlog^2n)\)

代码

// Problem: D. The Child and Sequence
// Contest: Codeforces - Codeforces Round #250 (Div. 1)
// URL: https://codeforces.com/problemset/problem/438/D
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=1e5+5;
int n,m,a[N];
struct Tr
{
	int l,r,mx;
	LL sum;
}tr[N<<2];
void pushup(int p)
{
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
}
void build(int p,int l,int r)
{
	tr[p]={l,r};
	if(l==r)
	{
		tr[p].sum=tr[p].mx=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
}
LL ask(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
	int mid=tr[p].l+tr[p].r>>1;
	LL res=0;
	if(l<=mid)res+=ask(p<<1,l,r);
	if(r>mid)res+=ask(p<<1|1,l,r);
	return res;
}
void modify_mod(int p,int l,int r,int x)
{
	if(tr[p].l==tr[p].r)
	{
		tr[p].mx%=x;
		tr[p].sum=tr[p].mx;
		return ;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid&&tr[p<<1].mx>=x)modify_mod(p<<1,l,r,x);
	if(r>mid&&tr[p<<1|1].mx>=x)modify_mod(p<<1|1,l,r,x);
	pushup(p);
}
void modify_change(int p,int k,int x)
{
	if(tr[p].l==tr[p].r)
	{
		tr[p].mx=tr[p].sum=x;
		return ;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(k<=mid)modify_change(p<<1,k,x);
	else
		modify_change(p<<1|1,k,x);
	pushup(p);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build(1,1,n);
    while(m--)
    {
    	int op,l,r,k,x;
    	scanf("%d",&op);
    	if(op==1)
    	{
    		scanf("%d%d",&l,&r);
    		printf("%lld\n",ask(1,l,r));
    	}
    	else if(op==2)
    	{
    		scanf("%d%d%d",&l,&r,&x);
    		modify_mod(1,l,r,x);
    	}
    	else
    	{
    		scanf("%d%d",&k,&x);
    		modify_change(1,k,x);
    	}
    }
    return 0;
}

标签:取模,Sequence,int,long,Child,define
From: https://www.cnblogs.com/zyyun/p/16808249.html

相关文章

  • UE5 中用 Python 接口创建 Level Sequence 与设置 TriggerEvent
    UE5中用Python接口创建LevelSequence与设置TriggerEvent本文内容可能只能在UE5下有用,未在UE4环境下实验过。背景遇到了一个美术需求,需要批量读取一段动画,制......
  • CF1741E Sending a Sequence Over the Network
    Description先水了发翻译你现在有一个序列\(a\),定义一个用该序列生成新序列\(b\)的规则如下:把\(a\)这个序列分成连续的几段;对于每一段,我们把这一段的长度插入......
  • Sending a Sequence Over the Network
    传送门题意:一段a序列,划分他,每一个区间都有一个长度,这个长度可以放在他划分的区间的左侧或者右侧,然后重新构成一个b序列,现在给出b序列,问能否由a序列得来思路:首先,去暴......
  • sqlalchemy.exc.noforeignkeyserror: could not determine join condition between pa
    错误提示:sqlalchemy.exc.noforeignkeyserror:couldnotdeterminejoinconditionbetweenparent/childtablesonrelationshipwife.wife-therearenoforeignkey......
  • elementUI 如何动态的给 el-tree 添加子节点数据 children
    elementUI如何动态的给el-tree添加子节点数据children一、需求有这样一个数据结构的tree。​​element​​的tree懒加载是从根上就开始懒加载,但我需要实现的是已经......
  • 测试BAPI ,执行test sequence
    ​同行问了个问题,说执行BAPI后显示成功,但是前台去查看值并没有变化。其实BAPI都是RFC,updatetask模式更新,需要显示的commit,不会隐士提交。所以在SE37下,执行testsequence,把......
  • MaoWei-2021-GeneratingSmoothPoseSequencesForDiverseHumanMotionPredition
    #GeneratingSmoothPoseSequencesforDiverseHumanMotionPrediction#paper1.paper-info1.1MetadataAuthor::[[WeiMao]],[[MiaomiaoLiu]],[[MathieuSa......
  • [Oracle] LeetCode 300 Longest Increasing Subsequence
    Givenanintegerarraynums,returnthelengthofthelongeststrictlyincreasingsubsequence.Asubsequenceisasequencethatcanbederivedfromanarrayby......
  • CF437D The Child and Zoo
    CF437DTheChildandZoo-洛谷|计算机科学教育新生态(luogu.com.cn)很像货车运输?但是点权?转化一下。每条边\((u,v)\)设定边权为\(\min(a[u],a[v])\),那么一条简......
  • Yet Another RGB Sequence
    传送门读题后立马想到容斥:嗯先算由\(R-K,G-K,B,0\)构成的方案数,再把\(K\)个RG插入。这样就完美地简化成模型了!但明显把\(K\)个RG删掉后剩下的序列可能会合并......