【线段树 成段更新】HDU 4027
KIDx的解题报告题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4027
http://dl.iteye.com/upload/attachment/0062/3712/03745ead-a7ca-372d-8c00-9dfaef5b6818.png
加了输入外挂之后，排第二，还不错！
下面的代码没加外挂，运行时间是：375ms，还可以
#include <iostream>#include <cmath>using namespace std;#define inf 0x3fffffff#define M 100005#define Max 26#define LL __int64struct Node{int l, r;LL v;}N;LL v;void create (int u, int a, int b){N.l = a, N.r = b;if (a == b){N.v = v;return ;}int mid = (a + b) >> 1, lc = u+u, rc = u+u+1;create (lc, a, mid);create (rc, mid+1, b);N.v = N.v + N.v;}void update (int u, int a, int b){if (N.v == N.r - N.l + 1)//说明从l到r都是1，不用往下更新了return ;if (N.l == N.r){N.v = LL(sqrt ((double)N.v));//自底向上更新return ;}int lc = u+u, rc = u+u+1;if (a <= N.r)update (lc, a, b);if (b >= N.l)update (rc, a, b);N.v = N.v + N.v;}LL find (int u, int a, int b){if (N.v == N.r - N.l + 1)//同理lazy一下return min (N.r, b) - max (N.l, a) + 1;if (a <= N.l && b >= N.r)return N.v;LL m1 = 0, m2 = 0;int lc = u+u, rc = u+u+1;if (a <= N.r)m1 = find (lc, a, b);if (b >= N.l)m2 = find (rc, a, b);return m1+m2;}int main(){char ch;int n, i, m, cc = 1, a, b;while (~scanf ("%d", &n)){for (i = 1; i <= n; i++)scanf ("%I64d", v+i);create (1, 1, n);scanf ("%d", &m);printf ("Case #%d:\n", cc++);while (m--){scanf ("%s%d%d", ch, &a, &b);if (a > b) a ^= b, b ^= a, a ^= b;//又是坑人的陷阱if (ch == '1') printf ("%I64d\n", find (1, a, b));else update (1, a, b);}printf ("\n");} return 0;}
页:
[1]