bzoj3211花神游历各国&&bzoj3038上帝造题的七分钟2*

时间:2020-12-21 16:05:43

bzoj3211花神游历各国

题意:

n个数的序列,m个操作,操作两种:区间开根(向下取整)和区间求和。n≤100000,m≤200000,序列中的数非负且≤109

题解:

一个≤109的数开6次根就变成1了。因此开根操作可以暴力只开不是1或0的数。对每个数维护并查集表示离它最近的不是1或0的数,每次只修改这个数在并查集中的根节点,然后跳到根节点的下一个数继续此操作。而数组的快速修改求和用树状数组就可以了。反思:本机测大数据会爆栈,路径压缩得写出非递归形式,但似乎bzoj的栈很大。

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 100500
 7 #define ll long long
 8 #define lb(x) x&-x
 9 using namespace std;
10 
11 inline int read(){
12     char ch=getchar(); int f=1,x=0;
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
15     return f*x;
16 }
17 int n,m,fa[maxn]; ll c[maxn],v[maxn];
18 void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
19 ll query(int x){ll q=0; while(x>0)q+=c[x],x-=lb(x); return q;}
20 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
21 int main(){
22     n=read(); inc(i,1,n)v[i]=(ll)read(),fa[i]=i,update(i,v[i]); m=read();
23     fa[n+1]=n+1; inc(i,1,n)if(v[i]<=1)fa[i]=find(i+1);
24     inc(i,1,m){
25         int x=read(),l=read(),r=read();
26         if(x==1)printf("%lld\n",query(r)-query(l-1));
27         if(x==2){
28             int j=l;
29             while(j<=r){
30                 j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
31                 update(j,v[j]-y); if(v[j]<=1)fa[j]=find(j+1); j++;
32             }
33         }
34     }
35     return 0;
36 }

 

20160613

------------------------------------------------------------------------------------------------------------------------------------------

bzoj3038上帝造题的七分钟2

题意:

同bzoj3211,但数的大小变为10^12,且操作代码变了。

题解:

数组开大,快速读入类型改为longlong即可。(我发现我bzoj3211的代码竟然是错了,wa了好几发,现在已改正)

代码:

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 100500
 7 #define ll long long
 8 #define lb(x) x&-x
 9 using namespace std;
10 
11 inline ll read(){
12     char ch=getchar(); ll f=1,x=0;
13     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
14     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
15     return f*x;
16 }
17 int n,m,fa[maxn]; ll c[maxn],v[maxn];
18 void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}
19 ll query(int x){ll q=0; while(x>0)q+=c[x],x-=lb(x); return q;}
20 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
21 int main(){
22     n=read(); inc(i,1,n)v[i]=read(),fa[i]=i,update(i,v[i]); m=read();
23     fa[n+1]=n+1; inc(i,1,n)if(v[i]<=1)fa[i]=find(i+1);
24     inc(i,1,m){
25         int x=read(),l=read(),r=read(); if(l>r)swap(l,r);
26         if(x==1)printf("%lld\n",query(r)-query(l-1));
27         if(x==0){
28             int j=l;
29             while(j<=r){
30                 j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);
31                 update(j,v[j]-y); if(v[j]<=1)fa[j]=find(j+1); j++;
32             }
33         }
34     }
35     return 0;
36 }

 

20160922