题目

输入格式

输出格式

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

输入样例

4

1 100 5 5

5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

输出样例

101

11

11

数据

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

题解

类似于重复开根以及取模之类的操作都有个共性，就是重复取的次数非常少

以本题开根为例，当取到一定次数时，就会变为1

我们用树状数组维护区间和

用并查集维护当前位置往下【包括当前位置】，最近还可以开根的位置

每次暴力开根维护树状数组即可【最多开5*N次】

#include<iostream>

#include<cstdio>

#include<cmath>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define lbt(x) (x & -x)

using namespace std;

const int maxn = 100005,maxm = 100005,INF = 1000000000;

inline int RD(){

    int out = 0,flag = 1; char c = getchar();

    while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

    while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

    return out * flag;

}

int N,M,pre[maxn],num[maxn];

LL A[maxn];

void add(int u,LL v){while (u <= N) A[u] += v,u += lbt(u);}

LL query(int u){LL ans = 0; while(u) ans += A[u],u -= lbt(u); return ans;}

LL sum(int l,int r){return query(r) - query(l - 1);}

int find(int u){return u == pre[u] ? u : pre[u] = find(pre[u]);}

int main(){

    N = RD();

    REP(i,N){

        num[i] = RD(); add(i,num[i]);

        pre[i] = (num[i] != 0 && num[i] != 1) ? i : i + 1;

    }pre[N + 1] = N + 1;

    M = RD();

    int cmd,l,r,u,v;

    while (M--){

        cmd = RD(); l = RD(); r = RD();

        if (cmd & 1) printf("%lld\n",sum(l,r));

        else {

            u = find(l);

            while (u <= r){

                v = (LL)sqrt(num[u]); add(u,v - num[u]);

                num[u] = v;

                if (num[u] == 1 || num[u] == 0) pre[u] = u + 1;

                u++;

            }

        }

    }

    return 0;

}