终于线段树还是有所领悟，发现对一个算法真的是，一开始云里雾里，后来这些天狂搞图论，数据结构，把KMP,Manacher，最短路，最小生成树 都狂弄了一下之后，发现再来弄线段树就容易多了，至少建树，更新什么的，我脑海里已经可以自己构图了。。所以，一个心得是，算法可以让脑子变的灵活聪明，前几天看的云里雾里的东西，过几天就会有领悟了。
好了，进入正题。
挑了一道还算可以的线段树题目，上午A了一道，完全是纯线段树水题，这题涉及懒惰标记，感觉高端了好多。。就算用了懒惰标记，仍然跑了将近3000MS,话说最近做图论题目发现，G++总是比C++要多几百MS（数据量本身比较大的时候）。。。而且尤其碰到几个坑题，用G++就WA，用C++就A。。
这个题，尼玛也坑爆了，看了discuss，发现居然要把很多变量设置成long long，但是涉及数据的比较，可能出问题，后来一气之下，全部改成了long long，还有个坑的地方是其增量可以为负数，。。这个也怪我，其实题目里写C的范围的时候已经写明了。
线段树的写法其实理解了都很简单，边写心里就已经建好了图（也应该是由于我现在太菜了，只在弄弄简单线段树）。
懒惰标记是一个比较难想的地方，而且容易出问题，还需细细消化。
#include <iostream> #include <cstdio> #include <cstring> #define maxn 100005 #define Lson (x<<1),l,mid //线段树访问左右孩子，直接在这里定义，方便下面调用，这个东西实在重用太多了 #define Rson (x<<1|1),mid+1,r using namespace std; long long d[maxn*5]; long long add[maxn*5]; void getup(long long x)//更新父节点操作，依据具体题目的要求来决定 { d[x]=d[x<<1]+d[x<<1|1]; } void getdown(long long x,long long ln,long long rn) //向下更新子节点，这也是懒惰标记得以实现的重要函数。 { d[x<<1]+=add[x]*ln; //节点之下还有多少子节点，就必须加多少。 d[x<<1|1]+=add[x]*rn; if (ln>1) add[x<<1]+=add[x]; if (rn>1) add[x<<1|1]+=add[x]; add[x]=0; //x的子节点已经更新完毕，务必将其设置为0. } void build(long long x,long long l,long long r)//很经典的建树操作 { if (l==r) { scanf("%lld",&d[x]); return; } long long mid=(l+r)/2; build(Lson); build(Rson); getup(x); } //通过建树操作，发现线段树的建树就是从最低层的节点开始，层层上推，使得每个节点段都能将该节点以下的所有点信息全部囊括。 void update(long long L,long long R,long long A,long long x,long long l,long long r)//节点更新操作。 { if (L<=l&&R>=r)//因为本题是进行段更新，因此这里写法类似于询问操作 { d[x]+=(r-l+1)*A; if (r-l>0) add[x]+=(long long)A; //懒惰标记，表示该节点的子节点需要更新，但不是在本次，下次有访问需求才会更新。。大大节省时间 return; } long long mid=(l+r)/2; if (add[x]!=0)//由于增量可能为负数，所以只能！=0 getdown(x,mid-l+1,r-mid); //当访问到了懒惰标记的节点，才会进行更新 if (L<=mid) update(L,R,A,Lson); if (R>mid) update(L,R,A,Rson); getup(x);//更新父节点 } long long query(long long L,long long R,long long x,long long l,long long r) { if (L<=l&&R>=r) { return d[x]; } long long ret=0; long long mid=(l+r)/2; if (add[x]!=0) { getdown(x,mid-l+1,r-mid); } if (L<=mid) ret+=query(L,R,Lson);//询问操作，递归到子节点去，通过子节点的返回值来最终组合为这一段的值。 if (R>mid) ret+=query(L,R,Rson); return ret; } int main() { long long n,q; while (scanf("%lld %lld",&n,&q)!=EOF) { memset(add,0,sizeof add); build(1,1,n); int i,j; for (i=1; i<=q; i++) { char ch; long long a,b,c; scanf(" %c",&ch); if (ch=='Q') { scanf("%lld %lld",&a,&b); printf("%lld ",query(a,b,1,1,n)); } if (ch=='C') { scanf("%lld %lld %lld",&a,&b,&c); update(a,b,c,1,1,n); } } } return 0; }