洛谷 P4145 上帝造题的七分钟 2 / SP2713 GSS4

Description

给出一个长度为 /(b/) 的数列 /(a/)，要进行 /(m/) 次操作，每次操作输入 /(k/)， /(l/)， /(r/)，要求支持以下两种操作：

• /(k=0/) 表示给 /([l,r]/) 中的每个数开平方（下取整）。

• /(k=1/) 表示询问 /([l,r]/) 中各个数的和。

数据中有可能 /(l>r/)，所以遇到这种情况请交换 /(l/) 和 /(r/)。

Constraints

对于 /(30/%/) 的数据，/(1/le n,m/le 10^3/)，数列中的数不超过 /(32767/)。

对于 /(100/%/) 的数据，/(1/le n,m/le 10^5/)，/(1/le l,r/le n/)，数列中的数大于 /(0/)，且不超过 /(10^{12}/)。

Solution

区间求和操作思路比较简单，直接使用树状数组维护即可。

再思考区间修改，通过举几个例子可以发现，任意数开方 /(6/) 次之后必定变成 /(1/)，而变成 /(1/) 之后无论怎样开方数值不会改变，可以从这里入手。

考虑把变成 /(1/) 的位置在区间修改时节省复杂度，可以想到用并查集维护。

令 /(fa[i]/) 表示 /(a[i]/) 及以后第一个当前不为 /(1/) 的数的位置，用来合并掉已变成 /(1/) 的区间，每次合并都是向右合并，但由于 /(a[n]/) 也可能开方成 /(1/)，所以也要记录 /(n + 1/) 位置，使得 /(n/) 位置能够合并。

考虑开方操作，设 /(sq = sqrt(a[i])/)，则这个数减少了 /((a[i] – sq)/)，在树状数组中修改减少值。

区间修改可以直接往后不断跳着修改，设置一个指针从 /(l/) 到 /(r/)，设当前位置下标为 /(now/)，接下来分两种情况：

• 若 /(a[now]/) 开方后变成了 /(1/)，则把他的父亲指向 /(now + 1/)， 更新 /(a[now]/)，同时指针直接跳到这个位置的祖先节点，即 /(now = find(fa[now])/)；

• 若 /(a[now]/) 开方后不为 /(1/)，则无法合并，指针直接向后移一个位置（即为 /(now + 1/)），他的父亲还是指向自己。

Code：

注意一下最后答案会爆 /(int/)，然后可能 /(l/) 和 /(r/) 的顺序是反的。

// by youyou2007 in 2022.
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#define int long long
#define REP(i, x, y) for(int i = x; i < y; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define PER(i, x, y) for(int i = x; i > y; i--)
#define per(i, x, y) for(int i = x; i >= y; i--)
#define lc (k << 1)
#define rc (k << 1 | 1)
using namespace std;
const int N = 1E5 + 5;
int n;
int a[N], fa[N], tree[N], m;
int lowbit(int x)
{
	return x & (-x); 
} 
void add(int x, int y)
{
	while(x <= n)
	{
		tree[x] += y;
		x += lowbit(x);
	}
}
int query(int x)
{
	int res = 0;
	while(x > 0)
	{
		res += tree[x];
		x -= lowbit(x);
	}
	return res;
}
int find(int x)
{
	if(fa[x] == x) return x;
	else
	{
		return fa[x] = find(fa[x]);
	}
}
signed main()
{
	scanf("%lld", &n);
	rep(i, 1, n)
	{
		scanf("%lld", &a[i]);
		add(i, a[i]);
	}
	rep(i, 1, n)
	{
		fa[i] = i;
	}
	fa[n + 1] = n + 1;//n + 1 也需要处理，用来给 n 合并
	scanf("%lld", &m);
	while(m--)
	{
		int opt, l, r;
		scanf("%lld%lld%lld", &opt, &l, &r);
		if(l > r)//l 与 r 可能是反的
		{
			swap(l, r);
		}
		if(opt == 0)
		{
			int now = l; 
			while(now <= r)//指针从l 到 r
			{
				int temp = sqrt(a[now]);
				add(now, -(a[now] - temp));//这里是 -(a[now] - temp)，是减少的值，不能想当然以为是 -temp
				a[now] = temp;//a数组需要更新
				if(a[now] == 1)//若开方后为1
				{
					fa[now] = now + 1;
					now = find(fa[now]);//指向祖先节点
				}
				else //否则指针直接向后移
				{
					now++;
				}
			}
		}
		else
		{
			printf("%lld/n", query(r) - query(l - 1));
		}
	}
        return 0;
}