【UOJ228】基础数据结构练习题(线段树)
2023-09-11 14:14:41 时间
【UOJ228】基础数据结构练习题(线段树)
题面
题解
我们来看看怎么开根?
如果区间所有值都相等怎么办?
显然可以直接开根
如果\(max-sqrt(max)=min-sqrt(min)\)怎么办?
此时意味着虽然开根出来的值不同,但是减去的值相同
举个例子,比如\(8,9\)
开根后是\(2,3\)
虽然值不同,但是差相同
所以,我们把开根换成区间减法
当出现上述两种情况时下放减法标记即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define MAX 120000
#define lson (now<<1)
#define rson (now<<1|1)
inline int read()
{
RG int x=0,t=1;RG char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return x*t;
}
int n,m,A[MAX];
struct Node{ll v,mx,mn,tag;}t[MAX<<2];
void Build(int now,int l,int r)
{
if(l==r){t[now].v=t[now].mx=t[now].mn=A[l];return;}
int mid=(l+r)>>1;
Build(lson,l,mid);Build(rson,mid+1,r);
t[now].v=t[lson].v+t[rson].v;
t[now].mx=max(t[lson].mx,t[rson].mx);
t[now].mn=min(t[lson].mn,t[rson].mn);
}
void puttag(int now,int l,int r,ll w)
{
t[now].v+=w*(r-l+1);
t[now].mx+=w;t[now].mn+=w;
t[now].tag+=w;
}
void pushdown(int now,int l,int r)
{
if(t[now].tag==0)return;
int mid=(l+r)>>1;
puttag(lson,l,mid,t[now].tag);
puttag(rson,mid+1,r,t[now].tag);
t[now].tag=0;
}
void Modify_Plus(int now,int l,int r,int L,int R,int w)
{
if(L<=l&&r<=R){puttag(now,l,r,w);return;}
pushdown(now,l,r);
int mid=(l+r)>>1;
if(L<=mid)Modify_Plus(lson,l,mid,L,R,w);
if(R>mid)Modify_Plus(rson,mid+1,r,L,R,w);
t[now].v=t[lson].v+t[rson].v;
t[now].mx=max(t[lson].mx,t[rson].mx);
t[now].mn=min(t[lson].mn,t[rson].mn);
}
void Modify_Sqrt(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
ll a=sqrt(t[now].mx),b=sqrt(t[now].mn);
if(t[now].mx==t[now].mn){puttag(now,l,r,a-t[now].mx);return;}
if(t[now].mx-a==t[now].mn-b){puttag(now,l,r,a-t[now].mx);return;}
}
pushdown(now,l,r);
int mid=(l+r)>>1;
if(L<=mid)Modify_Sqrt(lson,l,mid,L,R);
if(R>mid)Modify_Sqrt(rson,mid+1,r,L,R);
t[now].v=t[lson].v+t[rson].v;
t[now].mx=max(t[lson].mx,t[rson].mx);
t[now].mn=min(t[lson].mn,t[rson].mn);
}
ll Query(int now,int l,int r,int L,int R)
{
if(L<=l&&r<=R)return t[now].v;
pushdown(now,l,r);
int mid=(l+r)>>1;ll ret=0;
if(L<=mid)ret+=Query(lson,l,mid,L,R);
if(R>mid)ret+=Query(rson,mid+1,r,L,R);
t[now].v=t[lson].v+t[rson].v;
t[now].mx=max(t[lson].mx,t[rson].mx);
t[now].mn=min(t[lson].mn,t[rson].mn);
return ret;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i)A[i]=read();
Build(1,1,n);
while(m--)
{
int opt=read(),l=read(),r=read();
if(opt==1)Modify_Plus(1,1,n,l,r,read());
else if(opt==2)Modify_Sqrt(1,1,n,l,r);
else printf("%lld\n",Query(1,1,n,l,r));
}
return 0;
}
相关文章
- 数据结构基础 后序遍历和中序遍历还原二叉树
- 【HttpClient4.5中文教程】【第一章 :基础】1.1运行请求(二)
- JS基础 空间坐标
- 【零基础学习iOS开发】【01-前言】02-准备
- MATLAB 数据分析方法(第2版)1.2 MATLAB基础概述
- 【Java基础】HashMap底层数据结构及其原理
- 浅析Redis基础数据结构
- Python函数基础
- SwiftUI 基础之@ObservedObject 有什么用(含demo代码2020)
- Python基础之:Python的数据结构
- Shell基础:什么是shell脚本、2种脚本解释器、#!约定解释器类型、运行shell脚本的2种方式、shell变量命令规范/赋值/如何使用/只读变量/删除变量/变量类型、shell字符串及其常用方法、shell数组及其常用方法、shell注释
- 【数据结构/链表】基础内容+leetcode刷题路线(持续更新)
- 数据结构基础入门知识
- MySQL基础学习笔记
- 计算机基础之计算机硬件软件数据结构
- 通达OA 小飞鱼工作流在线培训教程(一)HTML基础介绍
- Objective-C的基础数据结构
- Redis学习系列二之.Net开发环境搭建及基础数据结构String字符串
- GAMES101作业2-代码框架逐行理解(c++基础巩固)
- 【uoj#228】基础数据结构练习题 线段树+均摊分析