[BZOJ3211]花神游历各国&&[BZOJ3038] 上帝造题的七分钟2 树状数组+并查集

3211: 花神游历各国

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 4057 Solved: 1480
[Submit][Status][Discuss]

Description

Input

Output

每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input

1 100 5 5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Sample Output

101

HINT

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

Source

SPOJ2713 gss4 数据已加强

由于是开方，所以每个数的开放次数不超过logn次，用树状数组维护前缀和，对于修改操作变为单点修改。

用并查集维护当前节点之前的最近的一个非1节点。

复杂度o（nlog²n）

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int read() {

     int x=;char ch=getchar();

     while(!isdigit(ch)) ch=getchar();

     while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

     return x;

 }

 int n,m;

 long long sum[];

 long long a[];

 int fa[];

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

 int lowbit(int x){return x&(-x);}

 void add(int x,long long val) {

     for(int i=x;i<=n;i+=lowbit(i)) sum[i]+=val;

 }

 void change(int x,long long val) {

     for(int i=x;i<=n;i+=lowbit(i)) sum[i]=sum[i]-val+(long long)sqrt(val);

 }

 long long query(int x) {

     long long ans=;

     for(int i=x;i>;i-=lowbit(i)) ans+=sum[i];

     return ans;

 }

 int main() {

     n=read();

     for(int i=;i<=n;i++) {a[i]=read();add(i,a[i]);}

     for(int i=;i<=n;i++) fa[i]=i;

     m=read();

     while(m--) {

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

         if(x==) {

             int now=find(r);

             while(now>=l) {

                 change(now,a[now]);

                 a[now]=sqrt(a[now]);

                 if(a[now]<=) fa[now]=find(fa[now-]);

                 now=find(fa[now-]);

             }

         }

         else {

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

         }

     }

     return ;

 }

巴特西