KIDx的解题报告
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4027
加了输入外挂之后,排第二,还不错!
下面的代码没加外挂,运行时间是:375ms,还可以
#include <iostream>
#include <cmath>
using namespace std;
#define inf 0x3fffffff
#define M 100005
#define Max 26
#define LL __int64
struct Node{
int l, r;
LL v;
}N[M<<2];
LL v[M];
void create (int u, int a, int b)
{
N[u].l = a, N[u].r = b;
if (a == b)
{
N[u].v = v[a];
return ;
}
int mid = (a + b) >> 1, lc = u+u, rc = u+u+1;
create (lc, a, mid);
create (rc, mid+1, b);
N[u].v = N[lc].v + N[rc].v;
}
void update (int u, int a, int b)
{
if (N[u].v == N[u].r - N[u].l + 1) //说明从l到r都是1,不用往下更新了
return ;
if (N[u].l == N[u].r)
{
N[u].v = LL(sqrt ((double)N[u].v)); //自底向上更新
return ;
}
int lc = u+u, rc = u+u+1;
if (a <= N[lc].r)
update (lc, a, b);
if (b >= N[rc].l)
update (rc, a, b);
N[u].v = N[lc].v + N[rc].v;
}
LL find (int u, int a, int b)
{
if (N[u].v == N[u].r - N[u].l + 1) //同理lazy一下
return min (N[u].r, b) - max (N[u].l, a) + 1;
if (a <= N[u].l && b >= N[u].r)
return N[u].v;
LL m1 = 0, m2 = 0;
int lc = u+u, rc = u+u+1;
if (a <= N[lc].r)
m1 = find (lc, a, b);
if (b >= N[rc].l)
m2 = find (rc, a, b);
return m1+m2;
}
int main()
{
char ch[2];
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[0] == '1') printf ("%I64d\n", find (1, a, b));
else update (1, a, b);
}
printf ("\n");
}
return 0;
}
- 大小: 12.3 KB
分享到:
相关推荐
hdu 1166线段树代码
hdu 1166线段树
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
线段树入门资料,有利于初学者学习,让他们详细了解线段树。
NULL 博文链接:https://128kj.iteye.com/blog/1738772
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
题面 【题目描述】 有nnn个营地,已知每个营地的人数,有四条命令: (1)Add(1) Add(1)Add iii jjj,iii和jjj为正整数,表示第iii个营地增加jjj个人(jjj不超过303030) (2)Sub(2)Sub(2)Sub iii jjj ,iii和jjj为正...