【UOJ#228】 基础数据结构练习题
2024-08-24 00:19:41
题目描述
sylvia 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。
在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友九条可怜酱给她出了一道题。
给出一个长度为 nn 的数列 AA，接下来有 mm 次操作，操作有三种：
- 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 Ai+xAi+x。
- 对于所有的 i∈[l,r]i∈[l,r]，将 AiAi 变成 ⌊Ai‾‾√⌋⌊Ai⌋。
- 对于所有的 i∈[l,r]i∈[l,r]，询问 AiAi 的和。
作为一个不怎么熟练的初学者，sylvia 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。于是她决定向你寻求帮助：你能帮她解决这个问题吗。
输入格式
第一行两个数：n,m。
接下来一行 n 个数 Ai。
接下来 m 行中，第 i 行第一个数 ti 表示操作类型：
若 ti=1，则接下来三个整数 li,ri,xi，表示操作一。
若 ti=2，则接下来三个整数 li,ri，表示操作二。
若 ti=3，则接下来三个整数 li,ri，表示操作三。
输出格式
对于每个询问操作，输出一行表示答案。
样例一
input
5 5
1 2 3 4 5
1 3 5 2
2 1 4
3 2 4
2 3 5
3 1 5
output
5
6
样例二
见样例数据下载。
限制与约定
| 测试点编号 | n 的规模 | m 的规模 | 其他约定 |
|---|---|---|---|
| 1 | n≤3000 | m≤3000 | |
| 2 | |||
| 3 | |||
| 4 | n≤100000 | m≤100000 | 数据随机生成 |
| 5 | |||
| 6 | ti≠1 | ||
| 7 | |||
| 8 | |||
| 9 | |||
| 10 |
对于所有数据，保证有 1≤li≤ri≤n,1≤Ai,xi≤105
时间限制：1s
空间限制：256MB
题解
orz 北大爷yyy。
用线段树维护区间的最大、最小值和答案。每次区间取根号的时候我们发现区间的极差都会减少，最后会减少到0。可以证明这个次数是loglogn级别的（开根相当于指数一直除以2），所以可以暴力递归进去改。但是区间加会导致区间的极差发生变化也有可能不变。所以我们在做开根号的时候只有在区间的极差会变的情况下我们暴力递归进去改，否则就直接区间减。可以证明这样的复杂度是NlogNloglogN的。
代码
#include <cstdio>
#include <cmath> #define R register
#define maxn 1048586
typedef long long ll;
int a[maxn];
ll sum[maxn], mn[maxn], mx[maxn], tag[maxn], mnnum[maxn], mxnum[maxn];
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
inline void update(R int o)
{
sum[o] = sum[o << ] + sum[o << | ];
mn[o] = dmin(mn[o << ], mn[o << | ]);
mx[o] = dmax(mx[o << ], mx[o << | ]);
}
inline void pushdown(R int o, R int l, R int r, R int mid)
{
if (tag[o] != )
{
sum[o << ] += 1ll * tag[o] * (mid - l + );
sum[o << | ] += 1ll * tag[o] * (r - mid);
mn[o << ] += tag[o]; mx[o << ] += tag[o];
mn[o << | ] += tag[o]; mx[o << | ] += tag[o];
tag[o << ] += tag[o];
tag[o << | ] += tag[o];
tag[o] = ;
}
}
void build(R int o, R int l, R int r)
{
if (l == r)
{
mn[o] = mx[o] = sum[o] = a[l];
mnnum[o] = mxnum[o] = ;
return ;
}
R int mid = l + r >> ;
build(o << , l, mid);
build(o << | , mid + , r);
update(o);
}
int ql, qr, qv;
void modify1(R int o, R int l, R int r)
{
if (ql <= l && r <= qr)
{
tag[o] += qv;
sum[o] += 1ll * qv * (r - l + );
mx[o] += qv;
mn[o] += qv;
return ;
}
R int mid = l + r >> ;
pushdown(o, l, r, mid);
if (ql <= mid) modify1(o << , l, mid);
if (mid < qr) modify1(o << | , mid + , r);
update(o);
}
inline bool check(R ll x)
{
return (ll) sqrt(x) * (ll) sqrt(x) == x;
}
void modify2(R int o, R int l, R int r)
{
if (ql <= l && r <= qr)
{
if (mx[o] == mn[o] || (mx[o] - mn[o] == && check(mx[o])))
{
R ll p = mx[o] - (ll) sqrt(mx[o]);
tag[o] -= p;
sum[o] -= p * (r - l + );
mx[o] -= p;
mn[o] -= p;
}
else
{
R int mid = l + r >> ;
pushdown(o, l, r, mid);
modify2(o << , l, mid);
modify2(o << | , mid + , r);
update(o);
}
return ;
}
R int mid = l + r >> ;
pushdown(o, l, r, mid);
if (ql <= mid) modify2(o << , l, mid);
if (mid < qr) modify2(o << | , mid + , r);
update(o);
}
inline ll query(R int o, R int l, R int r)
{
if (ql <= l && r <= qr) return sum[o];
R int mid = l + r >> ; R ll ret = ;
pushdown(o, l, r, mid);
if (ql <= mid) ret += query(o << , l, mid);
if (mid < qr) ret += query(o << | , mid + , r);
return ret;
}
int main()
{
R int n, m; scanf("%d%d", &n, &m);
for (R int i = ; i <= n; ++i) scanf("%d", a + i);
build(, , n);
for (R int i = ; i <= m; ++i)
{
R int opt, l, r; scanf("%d%d%d", &opt, &l, &r);
if (opt == )
{
R int x; scanf("%d", &x);
ql = l; qr = r; qv = x;
modify1(, , n);
}
else if (opt == )
{
ql = l; qr = r;
modify2(, , n);
}
else
{
ql = l; qr = r;
printf("%lld\n", query(, , n));
}
}
return ;
}
最新文章
- Linux-Rsync服务器/客户端搭建实战
- 斯坦福大学CS224d基础1：线性代数回顾
- 对象之间的引用传递 之 .NET中的深拷贝和浅拷贝
- Linux Hugetlbfs内核源码简析-----(二)Hugetlbfs挂载
- INPC & RaizePropertyChanged in mvvmlight
- depth_write
- 使用Python脚本强化LLDB调试器
- byte[] bytes和string转换
- POJ2531——Network Saboteur(随机化算法水一发)
- SVG 矢量图形格式
- struts2 集成webservice 的方法
- mysql的乱码问题
- java与数据结构(4)---java实现双向循环链表
- html系列教程--link mark meta
- Texture的渲染及截屏功能
- select默认选中项颜色为灰色，选择后变为黑色（js实现）
- Tensorflow object detection API ——环境搭建与测试
- MySQL 5.7安装指南
- SPARK安装三：SPARK集群部署
- 【HDOJ1045】【DFS】