absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] BZOJ 1503 郁闷的出纳员
[破碎的状态] 575B

[破碎的状态] NFLS OJ 1127 解题报告

absi2011 posted @ Apr 13, 2016 10:24:52 AM in 刷题记录 with tags 线段树 小高考 NFLS OJ , 292 阅读

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;
}
Avatar_small
ジミ=カルソン 说:
Apr 14, 2016 12:13:52 AM

什么鬼你居然真去把这题写了= =

Avatar_small
absi2011 说:
Apr 14, 2016 08:03:40 AM

而且已加入了恢复状态计划..


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter