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
【分析】
开始看一眼觉得线段树可做。
后来看题解用树状数组瞬秒......orzzz，注意到任何一个int都可以在很小的次数下变为1，所以直接暴力单点修改，将变成1的数parent设为它右边的数。
注意，输入中可能会有很多的0....直接写优化不好会T。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <map> const int MAXN = + ;
const int MAX = + ;
using namespace std;
typedef long long ll;
int n;
ll C[MAXN];
int data[MAXN], parent[MAXN]; int SQRT(int x){return (int)floor(sqrt((double)x * 1.0));}
int lowbit(int x){return x & -x;}
void add(int x, int val){
while (x <= n){
C[x] += val;
x += lowbit(x);
}
return;
}
ll sum(int x){
ll cnt = ;
while (x > ){
cnt += C[x];
x -= lowbit(x);
}
return cnt;
}
int find(int x) {return parent[x] == x? x : parent[x] = find(parent[x]);}
void init(){
memset(C, , sizeof(C));
scanf("%d", &n);
for (int i = ; i <= n; i++){
scanf("%d", &data[i]);
add(i, data[i]);
parent[i] = i;
if (data[i] == || data[i] == ) parent[i] = i + ;
}
parent[n + ] = n + ;
}
void work(){
int q;
scanf("%d", &q);
for (int i = ; i <= q; i++){
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (t == ) printf("%lld\n", sum(y) - sum(x - ));
else{
for (int i = x; i <= y; i = find(i + )){
int tmp = data[i];
data[i] = SQRT(data[i]);
add(i, data[i] - tmp);
if (data[i] <= ) parent[i] = find(i + );
}
}
}
} int main(){
int T;
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
work();
return ;
}