首页 > 代码库 > 【bzoj3211】花神游历各国 并查集+树状数组
【bzoj3211】花神游历各国 并查集+树状数组
原文地址：http://www.cnblogs.com/GXZlegend/p/6809714.html
题目描述
输入
输出
每次x=1时，每行一个整数，表示这次旅行的开心度
样例输入
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
样例输出
101
11
11
题解
并查集+树状数组，附带一点数学知识
因为√1=1，且一个数x开接近log2(log2x)次平方后就会变成1，这个数是非常小的。
所以我们完全可以暴力修改，只需要知道每次的修改区间中有多少真正需要修改的数即可。
这可以用并查集来维护，b[i]表示i之后（包括i）第一个点权不为1的数的位置，当然还需要一个find函数。
这样暴力修改，但是不能暴力求和，还需要用一个树状数组来维护区间和。
注意开long long，并且把b[n+1]赋为n+1以防止越界。
#include <cstdio>
#include <cmath>
#include <algorithm>
#define N 100010
using namespace std;
typedef long long ll;
int n , b[N];
ll w[N] , f[N];
int find(int x)
{
return b[x] == x ? x : b[x] = find(b[x]);
}
void update(int x , ll a)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] += a;
}
ll query(int x)
{
int i;
ll ans = 0;
for(i = x ; i ; i -= i & -i) ans += f[i];
return ans;
}
int main()
{
int m , i , opt , l , r;
ll tmp;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
scanf("%lld" , &w[i]) , b[i] = (w[i] <= 1 ? i + 1 : i) , update(i , w[i]);
b[n + 1] = n + 1;
scanf("%d" , &m);
while(m -- )
{
scanf("%d%d%d" , &opt , &l , &r);
if(opt == 1) printf("%lld\n" , query(r) - query(l - 1));
else
{
for(i = find(l) ; i <= r ; i = find(i + 1))
{
tmp = (ll)sqrt(w[i]) , update(i , tmp - w[i]) , w[i] = tmp;
if(w[i] <= 1) b[i] = find(i + 1);
}
}
}
return 0;
}
【bzoj3211】花神游历各国 并查集+树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。