题目链接
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