D - 敌兵布阵

二叉搜索树的问题,求区间最大数。这个题嘛,只能说坑,坑到死,写程序和调试程序的时间大概是1:2,一遍写好,之后就一直在Debug,我就说我逻辑没错吧,为了检查我把别人的c语言代码全部移植过来,也是TLE,难道是我主程序有问题?怎么可能!!!找了好久,最后用“敌兵布阵 TLE”作为关键词搜索,发现,原来是c++里面的cin、cout太耗费时间,我...


Description

Lily 特别喜欢养花,但是由于她的花特别多,所以照料这些花就变得不太容易。她把她的花依次排成一行,每盆花都有一个美观值。如果Lily把某盆花照料的好的话,这盆花的美观值就会上升,如果照料的不好的话,这盆花的美观值就会下降。有时,Lily想知道某段连续的花的美观值之和是多少,但是,Lily的算术不是很好,你能快速地告诉她结果吗?

Input

	第一行一个整数T,表示有T组测试数据。每组测试数据的第一行为一个正整数N(N<=50000),表示Lily有N盆花。接下来有N个正整数,第i个正整数ai表示第i盆花的初始美观值(1<=ai<=50)。接下来每行有一条命令,命令有4种形式:(1)Add i j, i和j为正整数,表示第i盆花被照料的好,美观值增加j(j<=30)(2)Sub i j, i和j为正整数,表示第i盆花被照料的不好,美观值减少j(j<=30)(3)Query i j, i和j为正整数,i<=j,表示询问第i盆花到第j盆花的美观值之和(4)End,表示结束,这条命令在每组数据最后出现每组数据的命令不超过40000条

Output

	对于第i组数据,首先输出"Case i:"和回车。对于每个"Query i j"命令,输出第i盆花到第j盆花的美观值之和。

Sample Input

1
9
7 9 8 4 4 5 4 2 7
Query 7 9
Add 4 9
Query 3 6
Sub 9 6
Sub 3 3
Query 1 9
End

Sample Output

Case 1:
13
30
50


下面是我的代码:


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct Node
{
    int left;
    int right;
    int value;
    //Node(int nleft, int nright, int nvalue):left(nleft),right(nright),value(nvalue){}
};
const int maxn=50000+1;
const int maxm=65536*2;
int flower[maxn];
Node treeNode[maxm];
int T, N;
int Queryans;
void BuildTree(int index, int left, int right)
{
    treeNode[index].value=0;        //每个节点初始化为0
    treeNode[index].left=left;      //左区间
    treeNode[index].right=right;    //右区间
    if(left==right)                 //如果是叶子节点则赋值并且把节点的下标放到flower数组
    {
        flower[left]=index;
        return;
    }
    BuildTree(index<<1, left, (left+right)>>1);     //新建下一个左节点
    BuildTree((index<<1)+1, ((left+right)>>1)+1, right);    //新建下一个右节点
}
void Update(int inode, int add)
{
    if(inode==1)return;     //如果更新到了根节点则返回
    int fnode=inode>>1;     //inode除以2得到父节点
    treeNode[fnode].value+=add;          //更新父节点的值
    Update(fnode, add);                      //递归更新上一级
}
void ToQuery(int i, int qleft, int qright)
{
    if(treeNode[i].left==qleft&&treeNode[i].right==qright)  //如果找到符合区间
    {
        Queryans+=treeNode[i].value;        //结果要增加
        return;
    }
    i = i<<1;                           //左子节点
    if(qleft<=treeNode[i].right)        //左区间有值
    {
        if(qright<=treeNode[i].right)ToQuery(i, qleft, qright); //完全在左区间
        else ToQuery(i, qleft, treeNode[i].right);              //部分在左区间
    }
    i+=1;                               //右子节点
    if(qright>=treeNode[i].left)        //右边区间有值
    {
        if(qleft>=treeNode[i].left)ToQuery(i, qleft, qright);     //完全在右区间
        else ToQuery(i, treeNode[i].left, qright);
    }
}
void Query(int qcoma, int qcomb)
{
    Queryans=0;
    ToQuery(1, qcoma, qcomb);
    //cout<<Queryans<<endl;
    printf("%d\n", Queryans);
}
void Add(int acoma, int acomb)
{
    treeNode[flower[acoma]].value+=acomb;
    Update(flower[acoma], acomb);
}
void Sub(int scoma, int scomb)
{
    treeNode[flower[scoma]].value-=scomb;
    Update(flower[scoma], -scomb);
}
bool Command(char *ccommand)
{
    int coma, comb;
    if(ccommand[0]=='E')return 0;
    else if(ccommand[0]=='Q')
    {
        scanf("%d %d", &coma, &comb);
        Query(coma, comb);
    }
    else if(ccommand[0]=='A')
    {
        scanf("%d %d", &coma, &comb);
        Add(coma, comb);
    }
    else if(ccommand[0]=='S')
    {
        scanf("%d %d", &coma, &comb);
        Sub(coma, comb);
    }
    return 1;
}
void Init()
{
    scanf("%d", &N);
    BuildTree(1, 1, N);
    int orgflower;
    for(int i=1;i<=N;i++)
    {
        scanf("%d", &orgflower);
        Add(i, orgflower);
    }
    //for(int i=1;i<=N;i++)cout<<treeNode[flower[i]].value<<" ";
    //cout<<endl;
}
int main()
{
    char command[20];
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        Init();
        printf("Case %d:\n", i);
        while(1)
        {
            scanf("%s",command);
            if(!Command(command))break;
        }
    }
    return 0;
}