首页 > 代码库 > bzoj3211: 花神游历各国

bzoj3211: 花神游历各国

2024-08-13 17:23:59   237人阅读

/*向下取整smg！
Popoqqq：题目大意：给定一个序列，提供下列操作：
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的数
*/

#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<cmath>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longint read(){	int x=0,f=1;char c=getchar();	while(!isdigit(c)){		if(c==‘-‘) f=-1;c=getchar();	}	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x*f;}const int nmax=1e5+5;ll sm[nmax];int fa[nmax],a[nmax];int find(int x){	return fa[x]==x?x:fa[x]=find(fa[x]);}ll query(int x){	ll ans=0;	for(int i=x;i;i-=(i&-i)) ans+=sm[i];	return ans;}void update(int x,int n,ll add){	for(int i=x;i<=n;i+=(i&-i)) sm[i]+=add;}int main(){	int n=read(),u,v,d;	rep(i,1,n) a[i]=read(),update(i,n,a[i]),fa[i]=i;fa[n+1]=n+1;	int m=read();	rep(i,1,m){		u=read(),v=read(),d=read();		if(u==1) printf("%lld\n",query(d)-query(v-1));		else{			int j=v;ll t;			while(j<=d){				j=find(j);if(j>d) break;t=a[j];a[j]=(ll)sqrt(t);update(j,n,a[j]-t);				if(a[j]<=1) fa[j]=find(j+1);++j;			}		}	}	return 0;}

　　

3211: 花神游历各国

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 2489  Solved: 925
[Submit][Status][Discuss]

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

Sample Output

101

11

11

HINT

 

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9


 

 

Source

SPOJ2713 gss4 数据已加强

[Submit][Status][Discuss]

 

bzoj3211: 花神游历各国


联系
我们