Party Lamps 题解

很容易知道：
如果一个按钮被按下两次，就相当于一次都不按，按下按钮2+3就相当于按钮1。
按钮的先后顺序不会影响最终结果。
因此，可以缩小C的大小。
if(C > 4)
{
if(C % 2) C = 3;
else C = 4;
}
这样DFS就可以通过所有数据了。

进一步优化：

观察发现，灯泡的情况每6个循环一次（2x3=6），因此，只要计算前6个灯泡的情况就可以了。
这样，就可以用位运算提高速度了。

数据结构之线段树

有的时候，会遇到一些涉及区间操作与查询（比如查询某个区间内的极值）的问题。在数据量不大的情况下，可以使用数组直接模拟。可是。。。。。

看一个题目：

【问题描述】
某次列车途经C个城市，城市编号依次为1到C，列车上共有S个座位，铁路局规定售出的车票只能是坐票， 即车上所有的旅客都有座。售票系统是由计算机执行的，每一个售票申请包含三个参数，分别用O、D、N表示，O为起始站，D为目的地站，N为车票张数。售票 系统对该售票申请作出受理或不受理的决定，只有在从O到D的区段内列车上都有N个或N个以上的空座位时该售票申请才被受理。请你写一个程序，实现这个自动售票系统。

【输入格式】
第一行包含三个用空格隔开的整数C、S和R，其中1≤C≤60000， l≤S≤60000，1≤R≤60000。C为城市个数，S为列车上的座位数，R为所有售票申请总数。接下来的R行每行为一个售票申请，用三个由空格隔开 的整数O，D和N表示，O为起始站，D 为目的地站，N为车票站数，其中1≤D≤C，1≤O≤C，所有的售票申请按申请的时间从早到晚给出。

【输出格式】
输出共有R行，每行输出一个“YES”或“NO”，表示当前的售票申请被受理或不被受理。

简化后的题目：
对于区间[A,B)，检查区间内最大值+T是否大于S，如果不大于，对区间内所有数增加T。

对于如此庞大数据，数组模拟显然会TLE，因此，需要一个更好的数据结构——线段树。

线段树概念参见 http://en.wikipedia.org/wiki/Segment_tree
http://www.byvoid.com/blog/sgt-railway/

现在讨论两个问题：

1、如果更改了一个区间的值，那么这个区间的父节点的值就有可能过时，因此，需要在递归过程的最后使用叶子节点值重新计算父节点的值。

2、如果我们更改了一个区间的值，而且这个代表这个区间的节点不是叶节点，此时，这个节点的孩子节点的数据就过时了，如果下次查询的正好是其中某个孩子的数据，显然是会出错的。

为此，引入函数movedown(TNode *p)和域add，用于维护线段树（也叫做“标记下传”）。

void movedown(TNode *p)
{
    p->value += p->add;         //若add大于0，则表示这个节点的儿子节点的数据是过时的
    if(p->l != p-> r)       //p不是叶子
    {
        p->lc->add += p->add;        //更新其孩子，并标记其孩子的孩子需要更新
        p->rc->add += p->add;
    }
    p->add = 0;
}

下面是本题的部分源代码，请注意movedown在其中的使用

_Bool check(TNode * p,int l,int r,int v)
{
    _Bool res;
    int mid = (p->l + p->r) >> 1;
    if(p->add > 0)  movedown(p);     //发现儿子节点数据过时，执行维护操作
    if(p->l >= l && p->r <= r)  return (p->value + v <= s);
    res = 1;
    if(l <= mid)    res = res && check(p->lc,l,r,v);
    if(r >= mid + 1)    res = res && check(p->rc,l,r,v);
    return res;
}

void modify(TNode *p,int l,int r,int delta)
{
    int mid = (p->l + p->r) >> 1;
    if(p->l >= l && p->r <= r)      // 当[p->l,p->r] 是 [l,r]的子集
    {
        p->add += delta;
        movedown(p);
    }
    else
    {
        movedown(p->rc);           //这里也需要movedown，想想为什么

        movedown(p->lc);
        if(l <= mid)    modify(p->lc,l,r,delta);
        if(r >= mid + 1)    modify(p->rc,l,r,delta);
        p->value = get_max(p->lc->value,p->rc->value);
        //使用儿子节点的数据更新父节点
    }
}