学步园

http://poj.org/problem?id=4047

求给定区间连续k个值和的最大值，有单点更改和交换操作。

这题主要是建树，以每个节点开始的连续k个值的和作为一个节点，这样共有n-k+1个节点，更新时计算出更新的点所在节点的范围，更新值为 新值-旧值。

交换即为两次更新，线段树记录节点最大值。

code:

#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <iomanip>
#include <bitset>
#include <list>
#include <ctime>
using namespace std ;
#define SET(arr, what)  memset(arr, what, sizeof(arr))
#define FF(i, a)        for(i=0; i<a; i++)
#define SD(a)           scanf("%d", &a)
#define SSD(a, b)       scanf("%d%d", &a, &b)
#define SSF(a, b)       scanf("%lf%lf", &a, &b)
#define SS(a)           scanf("%s", a)
#define SLD(a)          scanf("%lld", &a)
#define PF(a)           printf("%d\n", a)
#define PPF(a, b)       printf("%d %d\n", a, b)
#define PLF(a)          printf("%lf\n", a)
#define SZ(arr)         (int)a.size()
#define SWAP(a,b)       a=a xor b;b= a xor b;a=a xor b;
#define read            freopen("in.txt", "r", stdin)
#define write            freopen("out.txt", "w", stdout)
#define MAX             1<<30
#define ESP             1e-5
#define lson            l, m, rt<<1
#define rson            m+1, r, rt<<1|1
template<class T> inline T sqr(T a){return a*a;}
template<class T> inline void AMin(T &a,T b){if(a==-1||a>b)a=b;}
template<class T> inline void AMax(T &a,T b){if(a<b)a=b;}
template<class T> inline T Min(T a,T b){return a>b?b:a;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
const int maxn = 222222 ;
int data[maxn], q[maxn], sum[maxn<<2], cover[maxn<<2] ;
void pushup(int rt){
    sum[rt] = Max(sum[rt<<1], sum[rt<<1|1]) ;
}
void pushdown(int rt){
    if(cover[rt]!=0){
        cover[rt<<1] += cover[rt] ;
        cover[rt<<1|1] += cover[rt] ;
        sum[rt<<1] += cover[rt] ;
        sum[rt<<1|1] += cover[rt] ;
        cover[rt] = 0 ;
    }
}
void build(int l, int r, int rt){
    cover[rt] = 0 ;
    if(l==r){
        sum[rt] = q[l] ;
        return ;
    }
    int m = (l + r) >> 1 ;
    build(lson) ;
    build(rson) ;
    pushup(rt) ;
}
void update(int L, int R, int val, int l, int r, int rt){
    if(L<=l&&r<=R){
        cover[rt] += val ;
        sum[rt] += val ;
        return ;
    }
    pushdown(rt) ;
    int m = (l + r) >> 1 ;
    if(L<=m)    update(L, R, val, lson) ;
    if(R>m)     update(L, R, val, rson) ;
    pushup(rt) ;
}
int query(int L, int R, int l, int r, int rt){
    if(L<=l&&r<=R){
        return sum[rt] ;
    }
    pushdown(rt) ;
    int m = (l + r) >> 1 ;
    int ret = -MAX ;
    if(L<=m)    ret = Max(ret, query(L, R, lson)) ;
    if(m<R)     ret = Max(ret, query(L, R, rson)) ;
    return ret ;
}
int main(){
    int t, n, k, m, temp, i, j, cnt ;
    SD(t) ;
    while(t--){
        cnt = 1, temp = 0 ;
        SD(n) ;SSD(m, k) ;
        for(i=1; i<=n; i++){
            SD(data[i]) ;
            temp += data[i] ;
            if(i>k){
                temp -= data[i-k] ;
                q[++cnt] = temp ;
            }else   q[cnt] = temp ;
        }
        build(1, cnt, 1) ;
        while(m--){
            int a, b ;
            SD(temp) ;SSD(a, b) ;
            if(temp==2){
                PF(query(a, b+1-k, 1, cnt, 1)) ;
            }
            if(temp==1){
                if(a==b)    continue ;
                if(a>b){
                    int c = a ;a = b ;b = c ;
                }
                int v = data[b] - data[a] ;
                int x = Max(1, a-k+1) ;
                int y = Min(a, cnt) ;
                update(x, y, v, 1, cnt, 1) ;
                v = data[a] - data[b] ;
                x = Max(1, b-k+1) ;
                y = Min(b, cnt) ;
                update(x, y, v, 1, cnt, 1) ;
                v = data[a], data[a] = data[b], data[b] = v ;
            }
            if(temp==0){
                int v = b - data[a] ;
                data[a] = b ;
                int x = Max(1, a-k+1) ;
                int y = Min(a, cnt) ;
                update(x, y, v, 1, cnt, 1) ;
            }
        }
    }
    return 0 ;
}