BZOJ-3211花神游历各国并查集+树状数组-白红宇

BZOJ-3211花神游历各国并查集+树状数组

阅读量：5026 次

发布时间：2019-06-12

本文共 2494 字，大约阅读时间需要 8 分钟。

一开始想写线段树区间开方，简单暴力下，但觉得变成复杂度稍高，懒惰了，编了个复杂度简单的

3211: 花神游历各国

Time Limit: 5 Sec Memory Limit: 128 MB

Submit: 1706 Solved: 651

[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

这道题一打眼看就是区间操作，就想到线段树和树状数组，一开始想暴力开根到1为止，写个线段树区间开方但感觉编程复杂度相对较高，外加时间复杂度不低，于是写了个树状数组+并查集树状数组的用处不用多说，并查集的用处比较精妙：用并查集维护一下，维护每个数右边第一个不为1的数字，暴力开根，如果开根成1后，把他的父亲连到右边数的父亲上，这样在连续修改上，就可以跳过大量连续的1了666666

代码如下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define maxn 100001long long love[maxn]={
    0};int past[maxn]={
    0};int father[maxn]={
    0};int n;int lowbit(int x){    return x&(-x);}void change(int loc,int data){    while (loc<=n)        {            love[loc]+=data;            loc+=lowbit(loc);        }}long long sum(int loc){    long long tot=0;    while (loc>0)        {            tot+=love[loc];            loc-=lowbit(loc);        }    return tot;}int find(int x){    if (x==father[x])        return x;    else        {            father[x]=find(father[x]);            return father[x];        }}int main(){    scanf("%d",&n);    for (int i=1; i<=n; i++)        {            int x;            scanf("%d",&x);            change(i,x);            past[i]=x;            if (past[i]<=1)                father[i]=i+1;            else                father[i]=i;//一开始对father的初始化         }    int m;    father[n+1]=n+1;    scanf("%d",&m);    for (int i=1; i<=m; i++)        {            int command,l,r;            scanf("%d%d%d",&command,&l,&r);            if (command==1)                {                    long long ans=sum(r)-sum(l-1);                    printf("%lld\n",ans);                }            else                {                    for (l=find(l); l<=r; l=find(l+1))                        {                            int delta=floor(sqrt(past[l]));                            change(l,delta-past[l]);//变成开根的方法，就是先减掉自己本身再加上开根，所以可以直接减去自身和开根的差                             past[l]=delta;                            if (past[l]==1)                                father[l]=find(l+1);//如果开根到1了，就把father连到右边数的father上                         }                }        }    return 0;}