HBC237532[HNOI2016]网络,堆/优先队列,树链剖分,数据结构SegmentTree题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

As everyone knows , segment tree is an elegant data structure . One day , beginner Lucy started to learn segment tree and wrote the following code . #include

As everyone knows , segment tree is an elegant data structure . One day , beginner Lucy started to learn segment tree and wrote the following code . #include  #define mid (l + r) / 2 #define ls now * 2 #define rs now * 2 + 1 using namespace std; int n, q, l, r; int flag = 0; void build( int now, int l, int r, int *a ) { if ( l == r ) { cin >> a[now]; return; } build( ls, l, mid, a ); build( rs, mid + 1, r, a ); a[now] = a[ls] + a[rs]; return; } int query( int now, int l, int r, int L, int R, int *a ) { if ( a[ls] + a[rs] != a[now] ) flag = 1; if ( L <= l && r <= R ) return(a[now]); int sum = 0; if ( L <= mid ) sum += query( ls, l, mid, L, R, a ); if ( mid + 1 <= R ) sum += query( rs, mid + 1, r, L, R, a ); return(sum); } int main() { cin >> n >> q; int a[4 * n]; memset( a, 0, sizeof(a) ); build( 1, 1, n, a ); for (int i = 1 ; i <= q ; i++ ) { cin >> l >> r; cout << query( 1, 1, n, l, r, a ) << endl; } return 0 ; } Although this code made an mistake . But Lucy still passed TTT testcases and got AC . Now we know nnn and qqq for each testcase , and each aia_iai​ is positive and smaller than 100010001000 . Each query [l,r][l,r][l,r] satisfied 1≤l≤r≤n1leq lleq r leq n1≤l≤r≤n and completely randomly generated . The question is , what's the probability of Lucy to get AC ?

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC237532[HNOI2016]网络 堆/优先队列 树链剖分 数据结构SegmentTree题解