洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组，并查集]

　　题目传送门

题目背景

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

题目描述

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

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

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

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

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

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

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

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

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

输入输出格式

输入格式：

第一行一个整数 nn ，代表数列中数的个数。

第二行 nn 个正整数，表示初始状态下数列中的数。

第三行一个整数 mm ，表示有 mm 次操作。

接下来 mm 行每行三个整数k,l,r，

• k=0表示给 [l,r][l,r] 中的每个数开平方(下取整)
• k=1表示询问 [l,r][l,r] 中各个数的和。

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

输出格式：

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

输入输出样例

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

19
7
6

说明

对于30%的数据， 1\le n,m\le 10001≤n,m≤1000 ，数列中的数不超过 3276732767 。

对于100%的数据， 1 \le n,m \le 1000001≤n,m≤100000 ， 1 \le l,r \le n1≤l,r≤n ，数列中的数大于 00 ，且不超过 10^{12}1012 。

注意l有可能大于r，遇到这种情况请交换l,r。

　　分析：首先，要求进行区间修改和区间查询，很明显的线段树啊。这题用线段树确实也可以做，但是开方是不支持区间操作的，所以只能单点修改，但是会发现单点修改最多只能进行6次，因为log(log(1e12))约为6，向下取整就得到，每一个数只能操作六次，那么就打标记，直接暴力单点修改就可以A了。

　　但是这题还可以用树状数组套并查集做，而且更优。因为树状数组是用于保存前缀和的，那么每一次修改只要修改前缀和即可，每次的操作复杂度为O(logn)，查询也一样。那么修改操作和线段树也差不多。每次单点修改，最多只有6次，但是这样复杂度还是O(n^2)，那么并查集的作用就显现出来了。每次修改过以后，如果该点的值已经<=1了，那么就将该点的fa[i]修改为i+1，修改的for循环就可以这样写：

　　for(int i=find(l);i<=r;i=find(i+1))

　　就可以直接跳过不需要修改的点，优化复杂度了，平摊下来复杂度大约也就是树状数组的复杂度O(nlogn)。

　　Code：

 1 #include<bits/stdc++.h>
 2 #define Fi(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=1e5+7;
 6 ll a[N],c[N];int n,m,fa[N];
 7 inline ll read()
 8 {
 9   char ch=getchar();ll num=0;bool flag=false;
10   while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)flag=true;ch=getchar();}
11   while(ch>=‘0‘&&ch<=‘9‘){num=num*10+ch-‘0‘;ch=getchar();}
12   return flag?-num:num;
13 }
14 inline int find(int x){return (fa[x]==x||!fa[x])?fa[x]=x:fa[x]=find(fa[x]);}
15 inline void update(int x,ll y){for(;x<=n;x+=x&-x)c[x]+=y;}
16 inline ll get(int x){ll ret=0;for(;x;x-=x&-x)ret+=c[x];return ret;}
17 inline void change(int l,int r)
18 {
19   for(int i=find(l);i<=r;i=find(i+1)){
20     ll temp=(ll)sqrt(a[i]);update(i,temp-a[i]);
21     a[i]=temp;if(a[i]<=1)fa[i]=find(i+1);}
22 }
23 int main()
24 {
25   n=read();Fi(i,1,n){a[i]=read();update(i,a[i]);fa[i]=i;if(a[i]<=1)fa[i]=i+1;}
26   m=read();ll x,y,z;Fi(i,1,m){x=read();y=read();z=read();if(y>z)swap(y,z);
27     if(x==0)change(y,z);else printf("%lld\n",get(z)-get(y-1));}return 0;
28 }

洛谷P4145 上帝造题的七分钟2/花神游历各国 [树状数组，并查集]

原文：https://www.cnblogs.com/cytus/p/9071551.html