bzoj 3211: 花神游历各国 && bzoj 3038: 上帝造题的七分钟2

3211: 花神游历各国

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 3438  Solved: 1277
[ Submit][ Status][ Discuss]

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

线段树

开更号直接暴力单点更新，因为一个int范围内的正整数最多开不到8次更号就会变成1，

这也意味着一个点最多只需要单点更新不到8次，超过就不需要再更新了，不会超时

注意节点值可能为0，所以你需要开个flag[]标记当前节点是否需要更新

上帝造题7分钟节点值没有0就不用开flag[]标记了，直接看当前节点值是否等于节点对应区间长度应该就行

但注意L可能大于R

#include<stdio.h>
#include<math.h>
#define LL long long
LL tre[444444], f[444444];
void Create(int l, int r, int x)
{
int m;
if(l==r)
{
scanf("%lld", &tre[x]);
if(tre[x]<=1)  f[x] = 1;
else  f[x] = 0;
return;
}
m = (l+r)/2;
Create(l, m, x*2);
Create(m+1, r, x*2+1);
tre[x] = tre[x*2]+tre[x*2+1];
f[x] = f[x*2]&f[x*2+1];
}
void Update(int l, int r, int x, int a, int b)
{
int m;
if(f[x])
return;
if(l==r)
{
tre[x] = sqrt(tre[x]*1.0);
if(tre[x]<=1)  f[x] = 1;
return;
}
m = (l+r)/2;
if(a<=m)
Update(l, m, x*2, a, b);
if(b>=m+1)
Update(m+1, r, x*2+1, a, b);
tre[x] = tre[x*2]+tre[x*2+1];
f[x] = f[x*2]&f[x*2+1];
}
LL Query(int l, int r, int x, int a, int b)
{
int m;
LL sum;
if(l>=a && r<=b)
return tre[x];
sum = 0;
m = (l+r)/2;
if(a<=m)
sum += Query(l, m, x*2, a, b);
if(b>=m+1)
sum += Query(m+1, r, x*2+1, a, b);
return sum;
}

int main(void)
{
int n, q, t, a, b;
while(scanf("%d", &n)!=EOF)
{
Create(1, n, 1);
scanf("%d", &q);
while(q--)
{
scanf("%d%d%d", &t, &a, &b);
if(t==1)
printf("%lld\n", Query(1, n, 1, a, b));
else
Update(1, n, 1, a, b);
}
}
return 0;
}