JCarlson:什么你想练练线段树?把这题A了冷静下

http://www.nflsoj.com/problems/1127/show

我:哦

这是一道模版题,我真的练了一发,AC了....

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100005];
long long val[1<<18];
long long tag1[1<<18];
long long tag2[1<<18];
const int inf=99999999;
void build_tree(int now,int l,int r)
{
    tag2[now]=inf;
    if (l==r-1)
    {
        val[now]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(now*2+1,l,mid);
    build_tree(now*2+2,mid,r);
    val[now]=val[now*2+1]+val[now*2+2];
}
void push_down(int now,int l,int r)
{
    int mid=(l+r)/2;
    if (tag2[now]!=inf)
    {
        tag2[now*2+1]=tag2[now];
        tag1[now*2+1]=0;
        val[now*2+1]=(long long)(mid-l)*tag2[now];
        tag2[now*2+2]=tag2[now];
        tag1[now*2+2]=0;
        val[now*2+2]=(long long)(r-mid)*tag2[now];
        tag2[now]=inf;
    }
    if (tag1[now]!=0)
    {
        tag1[now*2+1]+=tag1[now];
        val[now*2+1]+=(long long)tag1[now]*(mid-l);
        tag1[now*2+2]+=tag1[now];
        val[now*2+2]+=(long long)tag1[now]*(r-mid);
        tag1[now]=0;
    }
}
long long query(int now,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[now];
    }
    int mid=(l+r)/2;
    push_down(now,l,r);
    long long sum=0;
    if (l0<mid) sum+=query(now*2+1,l,mid,l0,r0);
    if (mid<r0) sum+=query(now*2+2,mid,r,l0,r0);
    return sum;
}
void change1(int now,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        tag1[now]+=k;
        val[now]+=(long long)k*(r-l);
        return;
    }
    int mid=(l+r)/2;
    push_down(now,l,r);
    if (l0<mid) change1(now*2+1,l,mid,l0,r0,k);
    if (mid<r0) change1(now*2+2,mid,r,l0,r0,k);
    val[now]=val[now*2+1]+val[now*2+2];
}
void change2(int now,int l,int r,int l0,int r0,int k)
{
    if ((l0<=l)&&(r<=r0))
    {
        tag2[now]=k;
        tag1[now]=0;
        val[now]=(long long)k*(r-l);
        return;
    }
    int mid=(l+r)/2;
    push_down(now,l,r);
    if (l0<mid) change2(now*2+1,l,mid,l0,r0,k);
    if (mid<r0) change2(now*2+2,mid,r,l0,r0,k);
    val[now]=val[now*2+1]+val[now*2+2];
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    ios::sync_with_stdio(false);
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    build_tree(0,0,n);
    for (i=0;i<m;i++)
    {
        int oper;
        int x,y;
        scanf("%d%d%d",&oper,&x,&y);
        x--;
        if (oper==1)
        {
            cout<<query(0,0,n,x,y)<<'\n';
        }
        else if (oper==2)
        {
            int z;
            scanf("%d",&z);
            change1(0,0,n,x,y,z);
        }
        else if (oper==3)
        {
            int z;
            scanf("%d",&z);
            change2(0,0,n,x,y,z);
        }
    }
    return 0;
}