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

题意：

n个数的序列，m个操作，操作两种：区间开根（向下取整）和区间求和。n≤100000，m≤200000，序列中的数非负且≤10⁹。

题解：

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

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 100500

 #define ll long long

 #define lb(x) x&-x

 using namespace std;

 inline int read(){

     char ch=getchar(); int f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int n,m,fa[maxn]; ll c[maxn],v[maxn];

 void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}

 ll query(int x){ll q=; while(x>)q+=c[x],x-=lb(x); return q;}

 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

 int main(){

     n=read(); inc(i,,n)v[i]=(ll)read(),fa[i]=i,update(i,v[i]); m=read();

     fa[n+]=n+; inc(i,,n)if(v[i]<=)fa[i]=find(i+);

     inc(i,,m){

         int x=read(),l=read(),r=read();

         if(x==)printf("%lld\n",query(r)-query(l-));

         if(x==){

             int j=l;

             while(j<=r){

                 j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);

                 update(j,v[j]-y); if(v[j]<=)fa[j]=find(j+); j++;

             }

         }

     }

     return ;

 }

20160613

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

bzoj3038上帝造题的七分钟2

题意：

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

题解：

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

代码：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #define inc(i,j,k) for(int i=j;i<=k;i++)

 #define maxn 100500

 #define ll long long

 #define lb(x) x&-x

 using namespace std;

 inline ll read(){

     char ch=getchar(); ll f=,x=;

     while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

     while(ch>=''&&ch<='')x=x*+ch-'',ch=getchar();

     return f*x;

 }

 int n,m,fa[maxn]; ll c[maxn],v[maxn];

 void update(int x,ll val){while(x<=n)c[x]+=val,x+=lb(x);}

 ll query(int x){ll q=; while(x>)q+=c[x],x-=lb(x); return q;}

 int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

 int main(){

     n=read(); inc(i,,n)v[i]=read(),fa[i]=i,update(i,v[i]); m=read();

     fa[n+]=n+; inc(i,,n)if(v[i]<=)fa[i]=find(i+);

     inc(i,,m){

         int x=read(),l=read(),r=read(); if(l>r)swap(l,r);

         if(x==)printf("%lld\n",query(r)-query(l-));

         if(x==){

             int j=l;

             while(j<=r){

                 j=find(j); if(j>r)break; ll y=v[j]; v[j]=(ll)sqrt(y);

                 update(j,v[j]-y); if(v[j]<=)fa[j]=find(j+); j++;

             }

         }

     }

     return ;

 }

20160922

巴特西

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

最新文章

热门文章