如果说以前写的树状数组都不是正宗的线段数的话，那么昨天晚上写的绝对是正宗的线段数了。
昨晚从约19.00开始一直写到00.00，累死了 最终还是被我调出来了。。。
其实回头看昨天写的题目，才真正理解线段树的优越性所在。优越的关键在于一个叫做lazy标记数组的神奇的东西（就是一个普通的数组啦哈）
但是用这个lazy数组做标记 ， 意义在于可以用来记录以改节点为父节点的子节点是否被更新过。
但需要修改或查询这个区间时，如果发现没有更新过的话，那么就将lazy数组下放，进而实现更新。同时下放后，有的区间也是不需要更新的，这样又可以节省出许多的时间来。
第一个题是《POJ 4047 Garden》题目的大意就是按顺序给出若干数字，对于若干条命令，有的命令是修改数组中某个数的值，有的则是要求出一个区间中，连续K个数之和的最大值。
这是一个压缩数值后的线段数。主要是修改这一部分。根据修改数值的下标，可以推算出该数的改变可能影响到的压缩后的区间的范围，然后才能继续进行updata函数的操作。代码如下：
＃i nclude <iostream>
＃i nclude <cstdio>
#define maxn 250010
using namespace std;
int a[maxn],b[maxn],sum[4*maxn],col[4*maxn];
int n,m,k,END;
void build(int rt, int l, int r)
{
col[rt]=0; sum[rt]=0;
if (l==r)
{
sum[rt]=b[l+k-1]-b[l-1];
return;
}
int mid=(l+r)/2;
build(rt*2,l,mid);
build(rt*2+1,mid+1,r);
sum[rt]=max(sum[2*rt],sum[2*rt+1]);
}
void PushDown(int rt)
{
if (col[rt]==0) return;
col[2*rt]+=col[rt];
col[2*rt+1]+=col[rt];
sum[2*rt]+=col[rt];
sum[2*rt+1]+=col[rt];
col[rt]=0;
}
void updata(int L,int R,int c,int l,int r,int rt)
{
if (L<=l && R>=r)
{
sum[rt]+=c,col[rt]+=c;return;
}
PushDown(rt);
int mid=(l+r)/2;
if (L<=mid) updata(L,R,c,l,mid,2*rt);
if (R>mid) updata(L,R,c,mid+1,r,2*rt+1);
sum[rt]=max(sum[2*rt],sum[2*rt+1]);
}
void work(int v, int c)
{
int L=max(1,v-k+1),R=min(END,v);
updata(L,R,c,1,END,1);
}
int query(int rt,int l,int r,int L,int R)
{
if (L<=l && R>=r) return sum[rt];
int mid=(l+r)/2,ans=-999999999;
PushDown(rt);
if (L<=mid) ans=query(rt*2,l,mid,L,R);
if (R>mid) ans=max(ans,query(2*rt+1,mid+1,r,L,R));
return ans;
}
int main()
{
int t,p,x,y;
scanf("%d",&t);
while (t--)
{
scanf("%d %d %d",&n,&m,&k);
END=n-k+1; b[0]=0;
for (int i=1; i<=n; i++) scanf("%d",&a[i]),b[i]=b[i-1]+a[i];
build(1,1,END);
while (m--)
{
scanf("%d%d%d",&p,&x,&y);
if (p==2)
{
printf("%d\n",query(1,1,END,x,y-k+1));
}
else if (p==0)
{
work(x,y-a[x]),a[x]=y;
}
else if (p==1)
{
work(x,a[y]-a[x]);
work(y,a[x]-a[y]);
swap(a[x],a[y]);
}
}
}
return 0;
}比较难以理解的可能是work函数，其具体作用就是推算影响到的区间，继而更新。
然后今天做的这个线段树的题目要稍稍简单一点点。这个题目是《POJ 2777 Count Color》
大意是给定一个长度为L的板，在每个单位长度上可以覆盖一种颜色。中途可以对任何一个区间上的颜色进行修改。对于每个输入的'P'，要求输出给定区间上的颜色的种类数。
但是题目还有一个小小的条件引起了我的注意，T（颜色种类数）<=30，邪恶了。（就是2^T<max int）
显然，可以用位运算来记录区间上的颜色种类，这样就显得方便灵活多了。
同时，由于题目有说明，在开始的时候，所以的单位长度的板上都被涂上了颜色1，显然这样的话build建树这个函数可以省略了，只要在标记数组上写个col[1]=1;就哦科啦，因为标记数组会一直往下面更新，这样有的地方不用的就不会被更新到，显然又是一个节省时间的好方法了。。。
本题比较简单，不多说了。具体代码如下：
＃i nclude <iostream>
＃i nclude <cstdio>
#define maxn 111111
using namespace std;
int sum[3*maxn],col[3*maxn];
int L,T,O;
int countnum(int x)
{
int ans=0;
while (x>0)
{
if (x%2==1) ans++;
x/=2;
}
return ans;
}
void PushDown(int rt)
{
if (col[rt]==0) return;
col[2*rt]=col[rt];
col[2*rt+1]=col[rt];
sum[2*rt]=col[rt];
sum[2*rt+1]=col[rt];
col[rt]=0;
}
void ***(int rt,int l,int r,int left,int right,int color)
{
if (left<=l && right>=r)
{
col[rt]=1<<(color-1);
sum[rt]=1<<(color-1);
return;
}
PushDown(rt);
int mid=(l+r)/2;
if (left<=mid) ***(2*rt,l,mid,left,right,color);
if (right>mid) ***(2*rt+1,mid+1,r,left,right,color);
sum[rt]=sum[2*rt] | sum[2*rt+1] ;
}
int query(int rt,int l,int r,int left,int right)
{
if (left<=l && right>=r) return sum[rt];
PushDown(rt);
int mid=(l+r)/2,ans=0;
if (left<=mid) ans=query(2*rt,l,mid,left,right);
if (right>mid) ans=ans|query(2*rt+1,mid+1,r,left,right);
return ans;
}
int main()
{
char s[3];
int A,B,C;
scanf("%d%d%d",&L,&T,&O);
col[1]=1;
while (O--)
{
scanf("%s",s);
if (s[0]=='P')
{
scanf("%d%d",&A,&B);
printf("%d\n",countnum(query(1,1,L,min(A,B),max(A,B))));
}
else if (s[0]=='C')
{
scanf("%d%d%d",&A,&B,&C);
***(1,1,L,min(A,B),max(A,B),C);
}
}
return 0;
}
感觉昨天晚上和今天进步很大，继续加油！ ^_^
