统计的力量

Posted on 2013-09-13 13:29 Mato_No1 阅读(1653) 评论(4)  编辑 收藏 引用 所属分类: 线段树
Orz zkw!!!

最近看完了《统计的力量》……觉得这实在是太神了……原来线段树可以这么写……

zkw线段树的思想:先将线段长度N变为2的整数次方,使线段树成为满二叉树,然后就可以通过各种位运算直接链接到某个结点,不必递归了,因此大大减小了常数……

本沙茶利用zkw线段树在BZOJ1756和1798上都刷到了rank3……
代码:
<1>BZOJ1756:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = (1 << 19+ 10, INF = ~0U >> 2;
struct node {
    
int sum, lv, rv, v;
} T[MAXN 
<< 1];
int n, N, A[MAXN], Z[MAXN], res;
inline 
int get_int()
{
    
int x; char ch; bool FF;
    
while ((ch = getchar()) < 48 && ch != '-') ;
    
if (ch == '-') {FF = 1; x = 0;} else {FF = 0; x = ch - 48;}
    
while ((ch = getchar()) >= 48) x = x * 10 + ch - 48;
    
if (FF) x = -x; return x;
}
void prepare()
{
    N 
= n << 1;
    re2(i, n, N) T[i].sum 
= T[i].lv = T[i].rv = T[i].v = A[i - n];
    
for (int i=0; (1<<i)<=n; i++) Z[1 << i] = i;
    
int lch, rch, _;
    rre2(i, n, 
1) {
        lch 
= i << 1; rch = lch ^ 1;
        T[i].sum 
= T[lch].sum + T[rch].sum;
        T[i].lv 
= (_ = T[lch].sum + T[rch].lv) >= T[lch].lv ? _ : T[lch].lv;
        T[i].rv 
= (_ = T[rch].sum + T[lch].rv) >= T[rch].rv ? _ : T[rch].rv;
        T[i].v 
= T[lch].v >= T[rch].v ? T[lch].v : T[rch].v;
        
if ((_ = T[lch].rv + T[rch].lv) >= T[i].v) T[i].v = _;
    }
}
void opr0(int pos, int x)
{
    
int i = pos + n; T[i].sum = T[i].lv = T[i].rv = T[i].v = x; int _, __ = x - A[pos], lch, rch; A[pos] = x;
    
for (i>>=1; i; i>>=1) {
        lch 
= i << 1; rch = lch ^ 1;
        T[i].sum 
+= __;
        T[i].lv 
= (_ = T[lch].sum + T[rch].lv) >= T[lch].lv ? _ : T[lch].lv;
        T[i].rv 
= (_ = T[rch].sum + T[lch].rv) >= T[rch].rv ? _ : T[rch].rv;
        T[i].v 
= T[lch].v >= T[rch].v ? T[lch].v : T[rch].v;
        
if ((_ = T[lch].rv + T[rch].lv) >= T[i].v) T[i].v = _;
    }
}
void opr1(int l, int r)
{
    
int sum0 = 0, l0, i, _; l |= n; r |= n; r++; res = -INF;
    
for (; l0=l, (l+=l&-l)<=r; ) {
        i 
= l0 / (l0 & -l0);
        
if (T[i].v > res) res = T[i].v;
        
if ((_ = sum0 + T[i].lv) > res) res = _;
        sum0 
+= T[i].sum; if (T[i].rv > sum0) sum0 = T[i].rv;
    }
    
int s = (l0 & -l0) >> 1, z = Z[s];
    
for (; l0<r; s>>=1, z--if ((l = l0 + s) <= r) {
        i 
= l0 >> z;
        
if (T[i].v > res) res = T[i].v;
        
if ((_ = sum0 + T[i].lv) > res) res = _;
        sum0 
+= T[i].sum; if (T[i].rv > sum0) sum0 = T[i].rv;
        l0 
= l;
    }
}
int main()
{
    
int n0, m, x, y, z;
    n0 
= get_int(); m = get_int(); re(i, n0) A[i] = get_int(); for (n=1; n<n0; n<<=1) ;
    prepare();
    re(i, m) {
        x 
= get_int(); y = get_int(); z = get_int();
        
if (x == 1) {if (y > z) {x = y; y = z; z = x;} opr1(--y, --z); printf("%d\n", res);} else opr0(--y, z);
    }
    
return 0;
}


<2>BZOJ1798:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define ll long long
const int MAXN = (1 << 17+ 10;
struct node {
    ll mr0, mr1, sum;
    
int len;
} T[MAXN 
<< 1];
int n, s, N, A[MAXN];
ll MOD, res;
inline 
int get_int()
{
    
char ch; int x;
    
while ((ch = getchar()) < 48) ;
    x 
= ch - 48while ((ch = getchar()) > 47) x = x * 10 + ch - 48;
    
return x;
}
void prepare()
{
    N 
= n << 1int lch, rch;
    re2(i, n, N) {T[i].mr0 
= 1; T[i].sum = A[i - n] % MOD; T[i].len = 0;}
    rre2(i, n, 
1) {
        lch 
= i << 1; rch = lch ^ 1; T[i].len = T[lch].len + 1;
        T[i].mr0 
= 1; T[i].sum = T[lch].sum + T[rch].sum; if (T[i].sum >= MOD) T[i].sum -= MOD;
    }
}
inline 
void dm(int i)
{
    
int lch = i << 1, rch = lch ^ 1; ll c0;
    
if ((c0 = T[i].mr0) ^ 1) {
        T[i].mr0 
= 1;
        T[lch].mr0 
= T[lch].mr0 * c0 % MOD; T[lch].mr1 = T[lch].mr1 * c0 % MOD; T[lch].sum = T[lch].sum * c0 % MOD;
        T[rch].mr0 
= T[rch].mr0 * c0 % MOD; T[rch].mr1 = T[rch].mr1 * c0 % MOD; T[rch].sum = T[rch].sum * c0 % MOD;
    }
    
if (c0 = T[i].mr1) {
        T[i].mr1 
= 0;
        T[lch].mr1 
+= c0; if (T[lch].mr1 >= MOD) T[lch].mr1 -= MOD; T[lch].sum = (T[lch].sum + (c0 << T[lch].len)) % MOD;
        T[rch].mr1 
+= c0; if (T[rch].mr1 >= MOD) T[rch].mr1 -= MOD; T[rch].sum = (T[rch].sum + (c0 << T[rch].len)) % MOD;
    }
}
void opr0(int l, int r, ll c)
{
    
int k, l0 = l | n, r0 = r | n, i, j, lch, rch; ll c0;
    
for (k=s-1; k&&(i=l0>>k)==r0>>k; k--) dm(i);
    
for (int k0=k; ((i=l0>>k0)<<k0)^l0; k0--) dm(i);
    
for (int k0=k; (((i=r0>>k0)<<k0)|((1<<k0)-1))^r0; k0--) dm(i);
    r0
++int l1;
    
for (; l1=l0, (l0+=l0&-l0)<=r0; ) {
        i 
= l1 / (l1 & -l1);
        T[i].mr0 
= T[i].mr0 * c % MOD; T[i].mr1 = T[i].mr1 * c % MOD; T[i].sum = T[i].sum * c % MOD;
    }
    
int _ = (l1 & -l1) >> 1, z = __builtin_ctz(_);
    
for (; l1<r0; _>>=1, z--if (l1 + _ <= r0) {
        i 
= l1 >> z;
        T[i].mr0 
= T[i].mr0 * c % MOD; T[i].mr1 = T[i].mr1 * c % MOD; T[i].sum = T[i].sum * c % MOD;
        l1 
+= _;
    }
    l0 
= l | n; r0 = r | n;
    
for (k=0; (i=l0>>k)^(j=r0>>k); k++) {
        
if ((i << k) ^ l0) {T[i].sum = T[i << 1].sum + T[(i << 1^ 1].sum; if (T[i].sum >= MOD) T[i].sum -= MOD;}
        
if (((j << k) | ((1 << k) - 1)) ^ r0) {T[j].sum = T[j << 1].sum + T[(j << 1^ 1].sum; if (T[j].sum >= MOD) T[j].sum -= MOD;}
    }
    
for (; k<s; k++) {
        i 
= l0 >> k;
        
if ((i << k) ^ l0 || ((j << k) | ((1 << k) - 1)) ^ r0) {T[i].sum = T[i << 1].sum + T[(i << 1^ 1].sum; if (T[i].sum >= MOD) T[i].sum -= MOD;}
    }
}
void opr1(int l, int r, ll c)
{
    
int k, l0 = l | n, r0 = r | n, i, j, lch, rch; ll c0;
    
for (k=s-1; k&&(i=l0>>k)==r0>>k; k--) dm(i);
    
for (int k0=k; ((i=l0>>k0)<<k0)^l0; k0--) dm(i);
    
for (int k0=k; (((i=r0>>k0)<<k0)|((1<<k0)-1))^r0; k0--) dm(i);
    r0
++int l1;
    
for (; l1=l0, (l0+=l0&-l0)<=r0; ) {
        i 
= l1 / (l1 & -l1);
        T[i].mr1 
+= c; if (T[i].mr1 >= MOD) T[i].mr1 -= MOD; T[i].sum = (T[i].sum + (c << T[i].len)) % MOD;
    }
    
int _ = (l1 & -l1) >> 1, z = __builtin_ctz(_);
    
for (; l1<r0; _>>=1, z--if (l1 + _ <= r0) {
        i 
= l1 >> z;
        T[i].mr1 
+= c; if (T[i].mr1 >= MOD) T[i].mr1 -= MOD; T[i].sum = (T[i].sum + (c << T[i].len)) % MOD;
        l1 
+= _;
    }
    l0 
= l | n; r0 = r | n;
    
for (k=0; (i=l0>>k)^(j=r0>>k); k++) {
        
if ((i << k) ^ l0) {T[i].sum = T[i << 1].sum + T[(i << 1^ 1].sum; if (T[i].sum >= MOD) T[i].sum -= MOD;}
        
if (((j << k) | ((1 << k) - 1)) ^ r0) {T[j].sum = T[j << 1].sum + T[(j << 1^ 1].sum; if (T[j].sum >= MOD) T[j].sum -= MOD;}
    }
    
for (; k<s; k++) {
        i 
= l0 >> k;
        
if ((i << k) ^ l0 || ((j << k) | ((1 << k) - 1)) ^ r0) {T[i].sum = T[i << 1].sum + T[(i << 1^ 1].sum; if (T[i].sum >= MOD) T[i].sum -= MOD;}
    }
}
void opr2(int l, int r)
{
    res 
= 0;
    
int k, l0 = l | n, r0 = r | n, i, j, lch, rch; ll c0;
    
for (k=s-1; k&&(i=l0>>k)==r0>>k; k--) dm(i);
    
for (int k0=k; ((i=l0>>k0)<<k0)^l0; k0--) dm(i);
    
for (int k0=k; (((i=r0>>k0)<<k0)|((1<<k0)-1))^r0; k0--) dm(i);
    r0
++int l1, r1;
    
for (; l1=l0, (l0+=l0&-l0)<=r0; ) {
        i 
= l1 / (l1 & -l1); res += T[i].sum;
    }
    
int _ = (l1 & -l1) >> 1, z = __builtin_ctz(_);
    
for (; l1<r0; _>>=1, z--if (l1 + _ <= r0) {
        i 
= l1 >> z; res += T[i].sum;
        l1 
+= _;
    }
    res 
%= MOD;
}
int main()
{
    
int n0 = get_int(); MOD = get_int(); re(i, n0) A[i] = get_int(); for (n=1, s=0; n<n0; n<<=1, s++) ; s++;
    prepare(); 
int M, _, l, r, c; M = get_int();
    re(i, M) {
        _ 
= get_int(); l = get_int(); r = get_int(); l--; r--;
        
if (_ == 1) {
            c 
= get_int() % MOD; opr0(l, r, c);
        } 
else if (_ == 2) {
            c 
= get_int() % MOD; opr1(l, r, c);
        } 
else {
            opr2(l, r); printf(
"%d\n", (int) res);
        }
    }
    
return 0;
}

Feedback

# re: 统计的力量  回复  更多评论   

2013-09-15 17:26 by taorunz
树状数组的推广

# re: 统计的力量  回复  更多评论   

2013-09-15 17:27 by taorunz
不能区间修改区间查询怎么办

# re: 统计的力量  回复  更多评论   

2013-09-21 15:58 by Mato_No1
@taorunz
zkw线段树可以支持标记。

# re: 统计的力量  回复  更多评论   

2013-11-04 21:26 by ht
@Mato_No1
打标记测试速度和普通差不多?

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理