HDU 4893 Wow! Such Sequence!(2014年多校联合 第三场 G)(线段树)

时间:2023-03-08 16:56:19

磨了一天的线段树,不能说完全搞清楚,只能说有一个大概的了解,靠着模板才把这道题A了,只能说太弱~~!

题意:

初始时有一字符串,全为0.

三种操作:

1 k d - add  把d加到第k个数上去
2 l r - query sum 计算l到r所有数的和
3 l r - change to nearest Fibonacci 把l到r的数修改为距离它最近的斐波那契数

节点附件三个值:

s1:由lazy控制的区间的正确的和。

s2:区间内与所有数相近的fib数之和,随着单点更新而更新。

col:lazy,标记区间是否全部取fib数,是取1,否则取0。

询问区间的和时,找到相应区间直接返回s1,若有col为1的区间要先向下推送,表示要取该区间的fib数的和。

代码以及详解:

 #include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxm=;
long long f[]= {,};
struct node
{
long long e,f;
int flag;
}a[maxm<<];
void pushup(int rt)
{
a[rt].e=a[*rt].e+a[*rt+].e;
a[rt].f=a[*rt].f+a[*rt+].f;
}
void pushdown(int rt)
{
if(a[rt].flag)
{
a[*rt].flag=;
a[*rt+].flag=;
a[*rt].e=a[*rt].f;
a[*rt+].e=a[*rt+].f;
a[rt].flag=;
}
} //建树
void build(int l,int r,int rt)
{
a[rt].flag=;//先都初始化为0
a[rt].e=;//区间和初始化为0
if(l==r)//如果只有一个元素
{
a[rt].f=;//该节点的斐波那契数记为1,因为此时距离a[rt].e最近的斐波那契数为1
return;
}
int m=(l+r)/;//递归构造左右子树
build(l,m,rt<<);
build(m+,r,rt<<|);
pushup(rt);//回溯更新父节点
} void add(int pos,int m,int l,int r,int rt)
{//要修改的元素的位置是pos,加数为m
if(pos<l||pos>r)//如果pos不在区间范围内,则返回
return ;
if(l==r)//找到那个节点了
{
if(a[rt].flag)//如果这个节点是被处理过的,就是说它以及它的子孩子都已经是离它最近的斐波那契数了
{
a[rt].e=m+a[rt].f;//该节点的区间和为该节点的斐波那契数+m
a[rt].flag=;//由于节点的值已经修改过了,所以当前的a[rt].f不一定是正确的值了
}
else
a[rt].e+=m;//没有被处理过,直接相加就好了
int p=lower_bound(f,f+,a[rt].e)-f;//二分查找:p是小于a[rt].e的第一个数
if(!p)//如果不存在比a[rt].f大的数,那么离它最近的斐波那契数就是1了
a[rt].f=;
else if(abs(a[rt].e-f[p])<abs(a[rt].e-f[p-]))//比较第p个数和p-1个数哪个离a[rt].e近,把a[rt].f赋为较近的那个
a[rt].f=f[p];
else
a[rt].f=f[p-];
return;
}
pushdown(rt);//延迟标记法,判断孩子节点是否需要更新,需要更新就更新
int mid=(l+r)/;
if(pos<=mid)
add(pos,m,l,mid,*rt);
else
add(pos,m,mid+,r,*rt+);
pushup(rt);//回溯更新根节点
} //将l到r的数赋为离他最近的斐波那契数
void change(int L,int R,int l,int r,int rt)
{
if(R<l||L>r)
return;
if (L <= l && r <= R)
{
a[rt].e=a[rt].f;//将e的值修改为f的值
a[rt].flag=;//标记修改过了
return ;
}
pushdown(rt);//向下更新子节点
int m = (l + r) >> ;
if (L <= m) change(L , R, l,m,rt<<);
if (m < R) change(L , R ,m+,r,rt<<|);
pushup(rt);//回溯更新父节点
} //计算l到r个数的和
long long query(int L,int R,int l,int r,int rt)
{
if(R<l||L>r)
return ;
else if (L <= l && r <= R)
{
return a[rt].e;
}
pushdown(rt);//向下更新子节点
int m = (l + r) >> ;
long long ret = ;
if (L <= m) ret += query(L , R , l,m,rt*);
if (m < R) ret += query(L , R , m+,r,rt*+);
return ret;
}
int main()
{
int n,m,i,op;
int l,r;
int k,d;
for(i=; i<=; i++)//打出斐波那契表
f[i]=f[i-]+f[i-];
while(scanf("%d%d",&n,&m)!=EOF)
{
build(,n,);//建树
while(m--)//m种操作
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&k,&d);
add(k,d,,n,);//给第k个数加上d;
}
else
{
scanf("%d%d",&l,&r);
if(op==)
printf("%I64d\n",query(l,r,,n,));//计算l到r个数的和
else
change(l,r,,n,);//将l到r的数赋为离他最近的斐波那契数
}
}
}
return ;
}

现附上线段树的一些基本概念以及两个常用模板:

  

线段树详解

1.概述

线段树类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,每个操作的复杂度为O(lgN)。

线段树的性质:若父区间是[a,b].(c=(a+b)/2),左儿子区间为[a,c],右儿子区间为[c+1,b],线段树需要的空间是数组大小的四倍。

2.基本操作

(1)线段树的构造(void build(int node,int begin,int end);)

运用递归的思想,如果当前结点记录的区间只有一个值,则直接赋值,                      否则递归左右子树。

代码如下:

#include <iostream>

using namespace std;

const int maxind = 256;

int segTree[maxind * 4 + 10];  //用来存储线段树,大小要大于原数组的四倍

int array[maxind];

/* 构造函数,得到线段树 */

void build(int node, int begin, int end)//node记录的是线段树的节点号

{

if (begin == end)

segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */

else

{

/*递归构造左右子树 */

build(2*node, begin, (begin+end)/2);//构造左孩子

build(2*node+1, (begin+end)/2+1, end);//构造右孩子

/*回溯时得到当前node节点的线段信息 */

if(segTree[2 * node] <= segTree[2 * node + 1])//把较小的数赋给左孩子

segTree[node] = segTree[2 * node];

else

segTree[node] = segTree[2 * node + 1];

}

}

int main()

{

array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;

build(1, 0, 5);

for(int i = 1; i<=20; ++i)

cout<< "seg"<< i << "=" <<segTree[i] <<endl;

return 0;

}

(2)区间查询(int query(int node,int begin,int end,int left,int right);)

主要思想是把所要查询的区间[a,b],划分为线段树上的结点,然后将这些结点代表的区间合并起来得到所需要的信息。

代码如下:

//其中node为当前查询结点,begin,end为当前存储的区间,left,right为此次query所要查询的区间。

int query(int node, int begin, int end, int left, int right)

{

int p1, p2;

/*  查询区间和要求的区间没有交集  */

if (left > end || right < begin)

return -1;

/* 如果当前区间在查询区间内 ,返回该节点的值*/

if (begin >= left && end <= right)

return segTree[node];

/*  比较左右子树两个节点值的最小值  */

p1 = query(2 * node, begin, (begin + end) / 2, left, right);

p2 = query(2 * node + 1, (begin + end) / 2 + 1, end, left, right);

if (p1 == -1)

return p2;

if (p2 == -1)

return p1;

if (p1 <= p2)

return  p1;

return  p2;

}

这样的过程一定选出了尽量少的区间,他们连后一定涵盖整个[left,right],没有重复也没有遗漏,线段树并不适合所有区间查询情况,它使用的条件是“相邻区间的信息可以被合并成两个区间合并的信息”,即问题是可以被分解解决的。

(3)区间或结点的更新 及线段树的动态维护(线段树的核心价值所在)

A.单节点更新

void Updata(int node, int begin, int end, int ind, int add)/*单节点更新*/

{

if( begin == end )

{

segTree[node] += add;

return ;

}

int m = ( left + right ) >> 1;

if(ind <= m)

Updata(node * 2,left, m, ind, add);

else

Updata(node * 2 + 1, m + 1, right, ind, add);

/*回溯更新父节点*/

segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]);

}

B.区间更新(线段树中最有用的)

需要用到延迟标记,每个节点新增加一个标记,用来记录这个节点是否被进行了某种修改操作(这种修改操作会影响其子节点),对于任意区间的修改,我们先按照查询的方式将其划分成线段树中的结点,然后修改这些节点中的信息,并给这些节点标上代表这种操作的标记,在修改和查询的时候,如果我们到了一个节点p,并且决定考虑其子节点,那我们就要看p有没有标记,如果有,就按照标记修改其子节点的信息,并且给子节点都标上相同的标记,同时取+消掉p的标记。

代码如下

void Change(node *p, int a, int b) /* 当前考察结点为p,修改区间为(a,b]*/

{

if (a <= p->Left && p->Right <= b)

/* 如果当前结点的区间包含在修改区间内*/

{

...... /* 修改当前结点的信息,并标上标记*/

return;

}

Push_Down(p); /* 把当前结点的标记向下传递*/

int mid = (p->Left + p->Right) / 2; /* 计算左右子结点的分隔点 */

if (a < mid) Change(p->Lch, a, b); /* 和左孩子有交集,考察左子结点*/

if (b > mid) Change(p->Rch, a, b); /* 和右孩子有交集,考察右子结点*/

Update(p); /* 维护当前结点的信息(因为其子结点的信息可能有更改)*/

}

线段树的主要运用:

1.区间最值查询问题:模板一;

2.连续区间修改或者单节点更新的动态查询问题:模板二;

3.多维空间的动态查询:模板三;

典型模板:

模板一:查询区间最值下标:

#include <iostream>

#include <string.h>

using namespace std;

#define maxind 256 //线段树节点个数

void build(int node,int b,int e,int m[],int a[])

{

if(b==e)

m[node]=b;//只有一个元素

else

{

build(2*node,b,(b+e)/2,m,a);

build(2*node+1,(b+e)/2+1,e,m,a);

if(a[m[2*node]]<=a[m[2*node+1]])

m[node]=m[2*node];

else

m[node]=m[2*node+1];

}

}

int query(int node,int b,int e,int m[],int a[],int i,int j)

{

int p1,p2;

if(i>e||j<b)

return -1;

if(b>=i&&e<=j)

return m[node];

p1=query(2*node,b,(b+e)/2,m,a,i,j);

p2=query(2*node+1,(b+e)/2+1,e,m,a,i,j);

if(p1==-1)

return m[node]=p2;

if(p2==-1)

return m[node]=p1;

if(a[p1]<=a[p2])

return m[node]=p1;

else

return m[node]=p2;

}

int main()

{

int l,r;//查询区间

scanf("%d%d",&l,&r);

int m[maxind];//下标从1起才有意义,否则不是二叉树

//保存下标编号结点对应区间最小值的下标

memset(m,-1,sizeof(m));

int a[]={3,4,5,7,2,1,0,3,4,5};

build(1,0,sizeof(a)/sizeof(a[0])-1,m,a);

cout<<query(1,0,sizeof(a)/sizeof(a[0])-1,m,a,l,r)<<endl;

return 0;

}

模板二:

#include<stdio.h>

#include<algorithm>

using namespace std;

const int maxm=111111;

long long add[maxm<<2];

long long sum[maxm<<2];

void pushup(int rt)

{

sum[rt]=sum[rt<<1]+sum[rt<<1|1];

}

void pushdown(int rt,int m)

{

if(add[rt])

{

add[rt<<1] += add[rt];

add[rt<<1|1] += add[rt];

sum[rt<<1] += add[rt] * (m - (m >> 1));

sum[rt<<1|1] += add[rt] * (m >> 1);

add[rt] = 0;

}

}

void build(int l,int r,int rt)

{

add[rt]=0;

if(l==r)

{

scanf("%lld",&sum[rt]);

return;

}

int m=(l+r)/2;

build(l,m,rt<<1);

build(m+1,r,rt<<1|1);

pushup(rt);

}

void update(int L,int R,int c,int l,int r,int rt) {

if (L <= l && r <= R) {

add[rt] += c;

sum[rt] += (long long)c * (r - l + 1);

return ;

}

pushdown(rt , r - l + 1);

int m = (l + r) >> 1;

if (L <= m) update(L , R , c , l,m,rt<<1);

if (m < R) update(L , R , c , m+1,r,rt<<1|1);

pushup(rt);

}

long long query(int L,int R,int l,int r,int rt) {

if (L <= l && r <= R) {

return sum[rt];

}

pushdown(rt , r - l + 1);

int m = (l + r) >> 1;

long long ret = 0;

if (L <= m) ret += query(L , R , l,m,rt<<1);

if (m < R) ret += query(L , R , m+1,r,rt<<1|1);

return ret;

}

int main()

{

int n,q;

scanf("%d%d",&n,&q);

build(1,n,1);

while(q--)

{

char op[2];

int a,b,c;

scanf("%s",op);

if(op[0]=='Q'){

scanf("%d%d",&a,&b);

printf("%lld\n",query(a,b,1,n,1));

}

else

{

scanf("%d%d%d",&a,&b,&c);

update(a,b,c,1,n,1);

}

}

return 0;

}