CSU 2151 集训难度【多标记线段树】

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2151

Input

第一行三个数n,m,v0 表示有n名萌新和m次调整，初始时全部萌新的集训难度都为v0

第2~m+1行每行三个数或四个数

0 x y v 表示把 [x,y]区间内的萌新的集训难度都增加v

1 x y v 表示把 [x,y]区间内的萌新的集训难度都变为v

2 x y表示询问[x,y]区间内萌新的集训难度之和

0<n,m<=10^5， |v|<=10^5

Output

每个询问一行，输出答案

Sample Input

Sample Output

多标记线段树处理法(洛谷3373,codevs4927)

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define mdzz int mid=(l+r)>>1;

#define lowbit(x) -x&x

#define all 1,n,1

#define rep(i,x,n) for(int i=(x); i<(n); i++)

#define in freopen("in.in","r",stdin)

#define out freopen("out.out","w",stdout)

using namespace std;

typedef long long ll;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const ll LNF = 1e18;

const int maxn =  + ;

const int maxm = 1e6 + ;

const double PI = acos(-1.0);

const double eps = 1e-;

const int dx[] = {-,,,,,,-,-};

const int dy[] = {,,,-,,-,,-};

int dir[][] = {{,},{,-},{-,},{,}};

const int mon[] = {, , , , , , , , , , , , };

const int monn[] = {, , , , , , , , , , , , };

int n,m;

int x,y,op;

ll a[maxn];

ll sum[maxn<<],add[maxn<<],cover[maxn<<],z,v;

void pushup(int rt)

{

    sum[rt]=sum[rt<<]+sum[rt<<|]; //区间查询和

}

void pushdown(int rt,int m)

{

    if(cover[rt])

    {

        //区间覆盖

        cover[rt<<] = cover[rt<<|] = cover[rt];

        sum[rt<<] = cover[rt]*(m-(m>>));

        sum[rt<<|] = cover[rt]*(m>>);

        add[rt<<] = add[rt<<|] =  ;     //set操作中取消add

        cover[rt] = ;

    }

    if(add[rt])

    {

        //区间求和

        add[rt<<]   += add[rt];

        add[rt<<|] += add[rt];

        sum[rt<<] += add[rt]*(m-(m>>));

        sum[rt<<|] += add[rt]*(m>>);

        add[rt]=;

    }

}

void build(int l,int r,int rt)

{

    add[rt]=cover[rt]=;

    if(l==r)

    {

        sum[rt]=v;

        return;

    }

    mdzz

    build(lson);

    build(rson);

    pushup(rt);

}

void update(int op,int L,int R,int c,int l,int r,int rt)

{

    if(L<=l && R>=r)

    {

        if(op==) //add

        {

            add[rt] += c;

            sum[rt] += (ll)c*(r-l+);

        }

        else

        {

            cover[rt] = c;

            add[rt] = ; //

            sum[rt] = (ll)c*(r-l+);

        }

        return ;

    }

    pushdown(rt,r-l+);

    mdzz

    if(L<=mid) update(op,L,R,c,lson);

    if(R>mid)  update(op,L,R,c,rson);

    pushup(rt);

}

ll query(int L,int R,int l,int r,int rt)

{

    if(L<=l&&R>=r) return sum[rt];

    pushdown(rt,r-l+);

    mdzz

    ll res=;

    if(L<=mid) res += query(L,R,lson);

    if(R>mid) res += query(L,R,rson);

    return res;

}

int main()

{

    while(~scanf("%d%d%lld",&n,&m,&v))

    {

        build(,n,);

        while(m--)

        {

            scanf("%d",&op);

            if(op==)

            {

                scanf("%d%d",&x,&y);

                printf("%lld\n",query(x,y,,n,));

            }

            else

            {

                scanf("%d%d%lld",&x,&y,&z);

                update(op,x,y,z,,n,);

            }

        }

    }

}

多次区间更新操作——>多个lazy