[BZOJ 3211]花神游历各国

danihao123 posted @ 2016年3月27日 22:02 in 题解 with tags BZOJ 线段树 , 733 阅读
转载请注明出处：http://danihao123.is-programmer.com/

这题和3038几乎一样啊……

但是注意有的喜欢度可能为0，这种情况不处理的话时间效率duangduangduang……

代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
/**************************************************************
    Problem: 3211
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1432 ms
    Memory:5108 kb
****************************************************************/
  
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001,maxnode=maxn*4;
unsigned long long sumv[maxnode];
bool lazy[maxnode];
unsigned long long A[maxn];
void build_tree(int o,int L,int R){
    if(L==R){
        sumv[o]=A[L];
        if(sumv[o]==1 || sumv[o]==0)
            lazy[o]=true;
    }else{
        int M=L+(R-L)/2,lc=o*2,rc=o*2+1;
        build_tree(lc,L,M);
        build_tree(rc,M+1,R);
        sumv[o]=sumv[lc]+sumv[rc];
        lazy[o]=lazy[lc]&&lazy[rc];
    }
}
int ql,qr;
void update(int o,int L,int R){
    if(L==R){
        sumv[o]=(unsigned long long)floor(sqrt(sumv[o]));
        if(sumv[o]==1 || sumv[o]==0)
            lazy[o]=true;
    }else{
        int M=L+(R-L)/2,lc=o*2,rc=o*2+1;
        if(ql<=M && !lazy[lc])
            update(lc,L,M);
        if(qr>M && !lazy[rc])
            update(rc,M+1,R);
        lazy[o]=lazy[lc]&&lazy[rc];
        sumv[o]=sumv[lc]+sumv[rc];
    }
}
unsigned long long query(int o,int L,int R){
    if(ql<=L && R<=qr){
        return sumv[o];
    }else{
        int M=L+(R-L)/2;
        unsigned long long ans=0;
        if(ql<=M)
            ans+=query(o*2,L,M);
        if(qr>M)
            ans+=query(o*2+1,M+1,R);
        return ans;
    }
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[20];
inline void writeint(unsigned long long x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    register int n,m,op;
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        A[i]=readint();
    build_tree(1,1,n);
    m=readint();
    while(m--){
        op=readint();
        ql=readint();
        qr=readint();
        if(ql>qr)
            swap(ql,qr);
        if(1&op){
            writeint(query(1,1,n));
            putchar('\n');
        }else{
            update(1,1,n);
        }
    }
    return 0;
}
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter