Description
Input
Output
每次x=1时,每行一个整数,表示这次旅行的开心度
Sample Input
4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
1 100 5 5
5
1 1 2
2 1 2
1 1 2
2 2 3
1 1 4
Sample Output
101
11
11
11
11
HINT
对于100%的数据, n ≤ 100000,m≤200000 ,data[i]非负且小于10^9
Source
SPOJ2713 gss4 数据已加强
树状数组+并查集~
因为每个数开logn次根号就能变成1,所以我们用并查集来维护前后关系,使得每次更新的部分都是不为1或0的。当a[i]<=1时,fa[i]=i+1,每次更新的时候顺序查找,查询的时候直接在树状数组中查询即可。
开long long!
(双倍经验:Tyvj上帝造题的七分钟2~)
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long longll n,m,a[100001],c[100001],fa[100002],x,y,id;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,ll v)
{for(;u<=n;u+=u&(-u)) c[u]+=v;
}ll cal(int u)
{ll now=0;for(;u;u-=u&(-u)) now+=c[u];return now;
}int findd(int u)
{return fa[u]==u ? u:fa[u]=findd(fa[u]);
}int main()
{n=read();for(int i=1;i<=n;i++) a[i]=read(),add(i,a[i]),fa[i]=i;fa[n+1]=n+1;m=read();while(m--){id=read();x=read();y=read();if(id==1) printf("%lld\n",cal(y)-cal(x-1));else for(int i=findd(x);i<=y;i=findd(i+1)){id=sqrt(a[i]);add(i,id-a[i]);a[i]=id;if(a[i]<=1) fa[i]=i+1;}}return 0;
}