【bzoj3211】花神游历各国

2015.04.14 16:43 Tue | 0次阅读 | 旧日oi | 固定链接 | 源码

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

题解

第一眼看到题肯定会想到区间修改线段树,但是需要维护的东西很多,空间也很大,注意到一个小于10^9次方的数最多开5次根号就变成1,并且不会再被修改,所以每个数至多被有效的修改5次,这提示我们可以从暴力的角度来考虑。我们只需维护1个链表,指向当前节点左右第一个不为1的数,然后顺次修改即可。维护链表可以用并查集。很神奇的一道题~

我的程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
const int maxn=400001;
ll s[maxn];
int n,m,fa[maxn],a[maxn];
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
    return x*f;
}
void add(int x,int y)
{
    for(;x<=n;x+=x&(-x))s[x]+=y;
}
ll sum(int x)
{
    ll t=0;
    for(;x>0;x-=x&(-x))t+=s[x];
    return t;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++){a[i]=read();add(i,a[i]);fa[i]=i;}
    fa[n+1]=n+1;
    m=read();
    while(m--)
    {
        int ch=read(),l=read(),r=read();
        if(ch==1)printf("%lld\n",sum(r)-sum(l-1));
        else
        {
            for(int i=find(l);i<=r;i=find(i+1))
             {
              int t=int(sqrt(a[i]));
              add(i,t-a[i]);
              a[i]=t;
              if(a[i]<=1)fa[i]=find(i+1);
             } 
        }
    }
    return 0;
}```