题目链接

P4145 上帝造题的七分钟 2 / 花神游历各国

上帝造题的七分钟 2 / 花神游历各国

题目背景

XLk 觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。

题目描述

"第一分钟，X 说，要有数列，于是便给定了一个正整数数列。

第二分钟，L 说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。

第三分钟，k 说，要能查询，于是便有了求一段数的和的操作。

第四分钟，彩虹喵说，要是 noip 难度，于是便有了数据范围。

第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。

第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过 \(64\) 位有符号整数类型的表示范围的限制。

第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。"

——《上帝造题的七分钟·第二部》

所以这个神圣的任务就交给你了。

输入格式

第一行一个整数 \(n\)，代表数列中数的个数。

第二行 \(n\) 个正整数，表示初始状态下数列中的数。

第三行一个整数 \(m\)，表示有 \(m\) 次操作。

接下来 \(m\) 行每行三个整数 k l r。

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

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

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

输出格式

对于询问操作，每行输出一个回答。

样例 #1

样例输入 #1

10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

样例输出 #1

19
7
6

提示

对于 \(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}\)。

解题思路

分块

由于最大的数最多修改 \(6\) 次后就变为 \(1\)，之后修改后都为 \(1\)，故可以分块暴力维护信息

• 时间复杂度：\(O(6\times m\sqrt{n})\)

珂朵莉树

• 时间复杂度：\(O()\)

势能线段树（小清新线段树）

懒标记适合：标记能够快速处理对区间询问的结果的影响，能够快速实现标记的合并。而区间开根号显然不适合打懒标记，但是对一个数开平方是有限的，可以用线段树暴力修改，即记录区间最大值 \(mx\)，当 \(mx>1\) 时才往下递归修改

• 时间复杂度：\(O(6\times min(n,m)logn+mlogn)\)

代码

• 分块

// Problem: P4145 上帝造题的七分钟 2 / 花神游历各国
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4145
// Memory Limit: 125 MB
// Time Limit: 1000 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,len,vis[N];
LL a[N],sum[N];
int get(int x)
{
	return x/len;
}
LL ask(int l,int r)
{
	LL res=0;
	if(get(l)==get(r))for(int i=l;i<=r;i++)res+=a[i];
	else
	{
		int i=l,j=r;
		while(get(i)==get(l))res+=a[i],i++;
		while(get(j)==get(r))res+=a[j],j--;
		for(int k=get(i);k<=get(j);k++)res+=sum[k];
	}
	return res;
}
void change(int l,int r)
{
	if(get(l)==get(r))for(int i=l;i<=r;i++)sum[get(i)]+=(int)sqrt(a[i])-a[i],a[i]=sqrt(a[i]);
	else
	{
		int i=l,j=r;
		while(get(i)==get(l))sum[get(i)]+=(int)sqrt(a[i])-a[i],a[i]=sqrt(a[i]),i++;
		while(get(j)==get(r))sum[get(j)]+=(int)sqrt(a[j])-a[j],a[j]=sqrt(a[j]),j--;
		for(int k=get(i);k<=get(j);k++)
		{
			vis[k]++;
			if(vis[k]<=6)
			{
				int ll=k*len,rr=min(len+ll-1,n-1);
				for(int i=ll;i<=rr;i++)
					sum[get(i)]+=(int)sqrt(a[i])-a[i],a[i]=sqrt(a[i]);
			}
		}
	}
}
int main()
{
    scanf("%d",&n);
    len=sqrt(n);
    for(int i=0;i<n;i++)scanf("%lld",&a[i]),sum[get(i)]+=a[i];
    scanf("%d",&m);
    while(m--)
    {
    	int op,l,r;
    	scanf("%d%d%d",&op,&l,&r);
    	l--,r--;
    	if(l>r)swap(l,r);
    	if(op)printf("%lld\n",ask(l,r));
    	else
    		change(l,r);
    }
    return 0;
}

• 势能线段树（小清新线段树）

// Problem: P4145 上帝造题的七分钟 2 / 花神游历各国
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4145
// Memory Limit: 125 MB
// Time Limit: 1000 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;
LL a[N];
struct Tr
{
	int l,r;
	LL mx,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].mx=tr[p].sum=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	pushup(p);
}
void change(int p,int l,int r)
{
	if(tr[p].l==tr[p].r)
	{
		tr[p].mx=tr[p].sum=sqrt(tr[p].mx);
		return ;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid&&tr[p<<1].mx>1)change(p<<1,l,r);
	if(r>mid&&tr[p<<1|1].mx>1)change(p<<1|1,l,r);
	pushup(p);
}
LL ask(int p,int l,int r)
{
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].sum;
	LL res=0;
	int mid=tr[p].l+tr[p].r>>1;
	if(l<=mid)res+=ask(p<<1,l,r);
	if(r>mid)res+=ask(p<<1|1,l,r);
	return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
    	int op,l,r;
    	scanf("%d%d%d",&op,&l,&r);
    	if(l>r)swap(l,r);
    	if(op)printf("%lld\n",ask(1,l,r));
    	else
    		change(1,l,r);
    }
    return 0;
}