[洛谷 4145,loj 6281,spoj GSS4]花神游历各国

题目链接

https://www.luogu.org/problem/P4145

https://loj.ac/problem/6281

https://www.spoj.com/problems/GSS4/

题解

Part 1 线段树做法

对序列建立一棵线段树，维护区间和以及最大值。因为开根号操作的特殊性，修改的时候我们只能针对每个元素暴力修改。

但这样对每个元素的修改不会太慢吗？

事实上并不会。因为 $\sqrt{1}=1$，所以对于区间最大值为 $1$ 的区间我们可以直接跳过，不必修改。

在题目的数据范围内（64 位整数），我们只需最多 $6$ 次开根号操作就可以让一个数变为 $1$，所以用线段树解决这道题的效率还是非常高的。

#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
struct seg
{
 long long sum,max;
}s[400005];
long long a[100005];
void pushup(int root)
{
 s[root].sum=s[root<<1].sum+s[root<<1|1].sum;
 s[root].max=max(s[root<<1].max,s[root<<1|1].max);
}
void build(int root,int l,int r)
{
 if(l==r)
 {
  s[root].sum=s[root].max=a[l];
  return;
 }
 int mid=(l+r)>>1;
 build(root<<1,l,mid);
 build(root<<1|1,mid+1,r);
 pushup(root);
}
long long query(int root,int cl,int cr,int l,int r)
{
 if(r<cl||cr<l)return 0;
 if(l<=cl&&cr<=r)return s[root].sum;
 int mid=(cl+cr)>>1;
 return query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r);
}
void update(int root,int cl,int cr,int l,int r)
{
 if(s[root].max==1)return;
 if(r<cl||cr<l)return;
 if(cl==cr)
 {
  s[root].sum=s[root].max=sqrt(s[root].sum);
  return;
 }
 int mid=(cl+cr)>>1;
 update(root<<1,cl,mid,l,r);
 update(root<<1|1,mid+1,cr,l,r);
 pushup(root);
}
int main()
{
 int n,m;
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 build(1,1,n);
 cin>>m;
 while(m--)
 {
  int op,l,r;
  cin>>op>>l>>r;
  if(l>r)swap(l,r);
  if(op)cout<<query(1,1,n,l,r)<<endl;
  else update(1,1,n,l,r);
 }
 return 0;
}

Part 2 分块解法

在 loj 上，本题是作为 hzwer 的分块入门题集中的一道题目。那么怎么用分块解决本题呢？

仿照线段树的解法来，对于同一块的元素，如果整块都是 $1$，则不必修改，否则暴力修改同一块内的所有元素。

同样的道理，因为最多 $6$ 次修改就能让全部元素变为 $1$，所以实际执行的暴力修改次数并不是那么多。

（代码暂时咕了QwQ）