HDU 5828 Rika with Sequence(線分樹＋小最適化)

Problem Description As we know,Rika is poor at match.Yuta is worying about this situation,so he gives Rikca some match to practice.The e is one of them:
Yuta has an array A with n numbers.The n he makes m operations on it.
The re are three type of operations:
1 l r x:For each i in[l,r],change A[i]to A[i]+x 2 l r:For each i in[l,r],change A[i]to a a−a−−−−n 3 l:Yuta wants Rika to sum up A[i forl]all[all]
It is too difficult for Rikca.Can you help her?
Input The first line contains a number t(1<=t==100)、the number of the testcases.And there re no more than 5 testcases with n>1000.
For each testcase,the first line contains two numbers n,m(1=n,m==100000).The second line contains n numbers A[1]~A[n].The n m line follow,each line describe operation.
It is garanted that 1<=A[i],x<=100000.
Output For each operation of type 3,print a lineas contains one number–the answer of the query.
Sample Input 1 5 1 2 3 3 5 1 3 5 5 5 5 5 1 5 5 5 5 5 2 1 2 3 3 3 3 3 3 3 3 3 1 5 5 5 5 5 5
Sample Output 5 6
二つの基本的な線分樹問題の融合は、セグメント更新＋hdu 4027で、穴はこのルート番号から1の後に追加の操作があります.もし単に4027のように一つの区間だけに対して1つの剪定はタイムアウトします.剪定を追加します.

      1 ，             ，
             ，           ，   lazy       ；

ネット上のオオカミさんを参考にしてコードを改善しましたが、試合中にTATをどうやって最適化するかは分かりませんでした.いい料理ですね
acコード:

#include 

using namespace std;

#define rep(i,a,n) for(int i = (a); i < (n); i++)
#define per(i,a,n) for(int i = (n)-1; i >= (a); i--)
#define clr(arr,val) memset(arr, val, sizeof(arr))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pi acos(-1)
typedef pair<int, int> pii;
typedef long long LL;
const double eps = 1e-8;
const int mod = 1000000007;
#define lson l,mid,rt*2
#define rson mid+1,r,rt*2+1
const int maxn = 100005;

LL sum[maxn<<2], laz[maxn<<2];
LL mark[maxn<<2];
void PushUp(int rt){
    sum[rt] = sum[rt<<1] + sum[rt<<1|1];
    if(mark[rt<<1] == mark[rt<<1|1])
        mark[rt] = mark[rt<<1];
    else mark[rt] = 0;
    return ;
}
void pushdown(int rt, int len){
    if(mark[rt]){
        mark[rt<<1] = mark[rt<<1|1] = mark[rt];
        sum[rt<<1] = mark[rt]*(len-len/2);
        sum[rt<<1|1] = mark[rt]*(len/2);
        laz[rt] = 0;
    }
    if(laz[rt]){
        laz[rt<<1] += laz[rt];
        laz[rt<<1|1] += laz[rt];
        sum[rt<<1] += laz[rt]*(len-len/2);
        sum[rt<<1|1] += laz[rt]*(len/2);
        if(mark[rt<<1]) mark[rt<<1] += laz[rt];
        if(mark[rt<<1|1]) mark[rt<<1|1] += laz[rt];
        laz[rt] = 0;
    }
}
void build(int l, int r, int rt){
    laz[rt] = 0;
    mark[rt] = 0;
    if(l == r){
        scanf("%I64d", &sum[rt]);
        mark[rt] = sum[rt];
        return ;
    }
    int mid = (l+r)>>1;
    build(lson);
    build(rson);
    PushUp(rt);
}
void add(int L,int R,LL c,int l,int r,int rt){
    if(L <= l && R >= r){
        sum[rt] += c*(r-l+1);
        laz[rt] += c;
        if(mark[rt]) mark[rt] += c;
        return;
    }
    pushdown(rt, r-l+1);
    int mid = (l+r)>>1;
    if(L<=mid)
        add(L,R,c,lson);
    if(mid < R)
        add(L,R,c,rson);
    PushUp(rt);
    return ;
}
void sq(int L, int R, int l, int r, int rt){
    if(L <= l && R >= r && mark[rt]){
        mark[rt] = (LL)sqrt(mark[rt]);
        sum[rt] = mark[rt]*(r-l+1);
        return ;
    }
    pushdown(rt, r-l+1);
    int mid = (l+r)>>1;
    if(L <= mid) sq(L, R, lson);
    if(mid < R) sq(L, R, rson);
    PushUp(rt);
    return ;
}
LL 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 mid = (l+r)>>1;
    LL ans = 0;
    if(L <= mid) ans += query(L, R, lson);
    if(mid < R) ans += query(L, R, rson);
    return ans;
}
int main(int argc, char const *argv[]) {
    int n, m;
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        build(1, n, 1);
        int a, x, y;
        LL num;
        while(m--){
            scanf("%d%d%d", &a, &x, &y);
            if(a == 1){
                scanf("%I64d", &num);
                add(x, y, num, 1, n, 1);
            }
            if(a == 2)
                sq(x, y, 1, n, 1);
            if(a == 3)
                printf("%I64d
", query(x, y, 1, n, 1));
        }
    }
    return 0;
}