BZOJ 3211 弗洛拉前往国家 树阵+并检查集合

标题效果：给定一个序列，它提供了以下操作：

1.将[l.r]每个号码间隔a[i]变sqrt(a[i])

2.查询[l,r]间隔和

剧烈的变化不支持由间隔，因此，我们选择单 - 点更换间隔查询的树阵，但是，这是O(n^2)的，怎么办？

我们发现一个数x最多开loglogx次根号就会变为1 也就是一个int范围内的数仅仅要开6次根号就会变为1 于是改动的总时间复杂度为O(nloglogn)

可是单次改动怎么办？我们维护一个并查集。一旦一个数为1或0，我们就把这个位置的father设为它右面的那个位置就可以 这样能够均摊O(n)时间找到一个数后面第一个>1的数

此外此题增加读入优化能够快一倍 令人非常费解0.0

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 100100

using namespace std;

typedef long long ll;

int n,m,a[M],fa[M];

ll c[M];

inline int getc() {

    static const int L = 1 << 15;

    static char buf[L], *S = buf, *T = buf;

    if (S == T) {

        T = (S = buf) + fread(buf, 1, L, stdin);

        if (S == T)

            return EOF;

    }

    return *S++;

}

inline int getint() {

    int c;

    while(!isdigit(c = getc()) && c != '-');

    bool sign = c == '-';

    int tmp = sign ?

0 : c - '0';

    while(isdigit(c = getc()))

        tmp = (tmp << 1) + (tmp << 3) + c - '0';

    return sign ? -tmp : tmp;

}

int Find(int x)

{

	if(!fa[x]||fa[x]==x)

		return fa[x]=x;

	return fa[x]=Find(fa[x]);

}

void Update(int x,int y)

{

	for(;x<=n;x+=x&-x)

		c[x]+=y;

}

ll Get_Ans(int x)

{

	ll re=0;

	for(;x;x-=x&-x)

		re+=c[x];

	return re;

}

void Modify(int x,int y)

{

	int i=x;

	for( i=x ; i<=y ; i=Find(i+1) )

	{

		int temp=(int)sqrt(a[i]);

		Update(i,temp-a[i]);

		a[i]=temp;

		if(a[i]<=1)

			fa[i]=Find(i+1);

	}

}

int main()

{

	int i,p,x,y;

	cin>>n;

	for(i=1;i<=n;i++)

	{

		a[i]=getint();

		if(a[i]==1||!a[i])

			fa[i]=i+1;

		Update(i,a[i]);

	}

	m=getint();

	for(i=1;i<=m;i++)

	{

		p=getint();

		x=getint();

		y=getint();

		if(p==1)

			printf("%lld\n", Get_Ans(y)-Get_Ans(x-1) );

		else

			Modify(x,y);

	}

}