题解 P3372 【【模板】线段树 1】

发一篇不需要O2就能过的分块。

基本思路：

分块的思路，大段维护，小段朴素。

维护几个数组：

区块\(block[maxn]\)
懒标记\(tag[maxn]\)
真实数据\(data[maxn]\)。

更新时

假设我们涉及到的区块的编号区间是\([lb,rb]\)，真实数据范围为\([l,r]\)。

那么，我们在区块的\([lb+1,rb-1]\)区间，给\(block[i]\)加上\(\Delta k\) 并且打上懒标记 \(=\Delta k\)。在真实数据的\([l,lb\times N]\)和\([rb\times N-N+1,r]\)区间的每个\(data[i]\)加上\(\Delta k\)。

查询时

同样的，对于区块区间\([lb+1,rb-1]\)直接累加就好，对于\(l b\)区间和\(rb\)区间单独处理即可。

上丑陋无比的代码。注意特判\(l\)和\(r\)在一个区块区间的情况。

#include<bits/stdc++.h>

using namespace std;

template< class ccf >inline ccf qr(ccf a) {

    char c=getchar();

    ccf x=0;

    int q=1;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    return q==-1?-x:x;

}

const int maxn=100055;

typedef long long ll;

ll data[maxn];

ll tag[maxn];

ll blk[maxn];

int n;

int m;

int N;

int adj;

#define RP(t,a,b) for(register int t=(a),edd=(b);t<=edd;t++)

int t1,t2;

ll t3;

int temp;

void add(int l,int r,ll k) {

    int lb=(l+N-1)/N;

    int rb=(r+N-1)/N;

    if(lb!=rb) {

	RP(t,l,N*lb)

	    data[t]+=k,blk[lb]+=k;

	RP(t,N*rb-N+1,r)

	    data[t]+=k,blk[rb]+=k;

	RP(t,lb+1,rb-1)

	    tag[t]+=k,blk[t]+=N*k;

    } else

	RP(t,l,r)

	    data[t]+=k,blk[t]+=k;

}

ll sum(int l,int r) {

    ll ret=0;

    int lb=(l+N-1)/N;

    int rb=(r+N-1)/N;

    RP(t,lb+1,rb-1)

	ret+=blk[t];

    if(tag[lb])

	RP(t,N*lb-N+1,N*lb)

	    data[t]+=tag[lb];

    tag[lb]=0;

    if(tag[rb])

	RP(t,N*rb-N+1,min(N*rb,n))

	    data[t]+=tag[rb];

    tag[rb]=0;

    if(lb!=rb) {

	RP(t,l,N*lb)

	    ret+=data[t];

	RP(t,N*rb-N+1,r)

	    ret+=data[t];

    } else

	RP(t,l,r)

	    ret+=data[t];

    return ret;

}

int main() {

#ifndef ONLINE_JUDGE

    freopen("in.in","r",stdin);

    freopen("out.out","w",stdout);

#endif

    n=qr(1);

    m=qr(1);

    RP(t,1,n)

	data[t]=qr(1ll);

    N=sqrt(n);

    RP(t,1,n/N)

	RP(i,1,N)

	blk[t]+=data[(t-1)*N+i];

    RP(t,1,n%N)

	blk[n/N+1]+=data[(n/N)*N+t];

    RP(t,1,m) {

	temp=qr(1);

	if(temp==1) {

	    t1=qr(1);

	    t2=qr(1);

	    t3=qr(1ll);

	    add(t1,t2,t3);

	} else {

	    t1=qr(1);

	    t2=qr(1);

	    printf("%ld\n",sum(t1,t2));

	}

    }

    return 0;

}

巴特西

题解 P3372 【【模板】线段树 1】

发一篇不需要O2就能过的分块。

更新时

查询时

最新文章

热门文章