站点公告
用户登陆
站点日历
<<  < 2013 - 8 >  >>
日 一 二 三 四 五 六
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
我的相册
最新日志
最新评论
日志搜索
最新留言
我的好友
我的圈子
友情链接
站点统计




[ 2013-8-19 15:24:00 | By: acm_letgo ]
HDU4348（离线线段树）
多校比赛的题目质量的确听高的，今天做的这个线段树我有事受益匪浅啊！

题目描述如下：

Description

Background
To The Moon is a independent game released in November 2011, it is a role-playing adventure game powered by RPG Maker.
The premise of To The Moon is based around a technology that allows us to permanently reconstruct the memory on dying man. In this problem, we'll give you a chance, to implement the logic behind the scene.

You‘ve been given N integers A[1], A[2],..., A[N]. On these integers, you need to implement the following operations:
1. C l r d: Adding a constant d for every {Ai | l <= i <= r}, and increase the time stamp by 1, this is the only operation that will cause the time stamp increase. 
2. Q l r: Querying the current sum of {Ai | l <= i <= r}.
3. H l r t: Querying a history sum of {Ai | l <= i <= r} in time t.
4. B t: Back to time t. And once you decide return to a past, you can never be access to a forward edition anymore.
.. N, M ≤ 105, |A[i]| ≤ 109, 1 ≤ l ≤ r ≤ N, |d| ≤ 104 .. the system start from time 0, and the first modification is in time 1, t ≥ 0, and won't introduce you to a future state.
 

Input

n m
A1 A2 ... An
... (here following the m operations. )
 

Output

... (for each query, simply print the result. )
 

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1
 

Sample Output

4
55
9
15

0
1
 

题目的意思是给你n个整数ai，要你完成若干项操作。操作包括：求和，区间更新（当且仅当每次更新后现时间+1），查询时间为t是某一段区间的和，退回到时间为t时刻的那个状态。
显然前面两个就不用说了，典型的lazy标记成段更新。
后面两个就有点头痛呢。
对于查询过去某个时刻的区间和，我们可以离线操作，什么意思呢，就是把所有要求得时间先全部读入，在把相应的区间按照时间排序，这样的话，到了这个时间就直接记录答案好了。
对于退回到过去某个时刻的状态，我们可以一次记录每次操作的具体值，然后一次回退就可以了，那这样会超时吗？会不会导致操作过多？不会！因为细想一下就会发现，对于每次C操作，我们最多操作两次，一次使时间增加，一次使时间减少。这样整个时间复杂度在数量级上是基本没有太大变化的，故不会超时呢。
到这里，题目就差不多了，很高心，这个题是我独自思考出来的。^_^
下面上代码：

＃i nclude <iostream>
＃i nclude <cstdio>
＃i nclude <cstring>
＃i nclude <algorithm>
#define maxn 100100
#define Cur ll rt,ll l,ll r
#define getmid ll mid=(l+r)/2
#define lson 2*rt,l,mid
#define rson 2*rt+1,mid+1,r
#define ll long long
using namespace std;

struct node{
    ll Lh,Rh,T,p,ANS;
}H[maxn];

char c[maxn],s[10];
ll sum[3*maxn],col[3*maxn],A[maxn],L[maxn],R[maxn],d[maxn];
ll t[maxn],h[maxn],C[maxn],n,m,NH,NC,nowH,time;
//全部用long long ，虽然慢点，但是省事许多，一开始就是因为写int爆了，于是贡献了若干次wa。
bool cmp(node h1,node h2)
{
    return h1.T<h2.T;
}

void pushup(ll rt)
{
    sum[rt]=sum[2*rt]+sum[2*rt+1];
}

void pushdown(Cur)
{
    if (col[rt]==0) return;
    getmid;
    col[2*rt]+=col[rt];
    col[2*rt+1]+=col[rt];
    sum[2*rt]+=col[rt]*(mid-l+1);
    sum[2*rt+1]+=col[rt]*(r-mid);
    col[rt]=0;
}

void build(Cur)
{
    col[rt]=0;
    if (l==r)
    {
        sum[rt]=A[l];
        return ;
    }
    getmid;
    build(lson);
    build(rson);
    pushup(rt);
}

void ***(Cur,ll L,ll R,ll id)
{
    if (L<=l && R>=r)
    {
        col[rt]+=id;
        sum[rt]+=id*(r-l+1);
        return;
    }
    pushdown(rt,l,r);
    getmid;
    if (L<=mid) ***(lson,L,R,id);
    if (R> mid) ***(rson,L,R,id);
    pushup(rt);
}

ll query(Cur,ll L,ll R)
{
    if (L<=l && R>=r) return sum[rt];
    pushdown(rt,l,r);
    getmid;
    ll tot=0;
    if (L<=mid) tot=query(lson,L,R);
    if (R> mid) tot+=query(rson,L,R);
    return tot;
}

int main()
{
    bool flag=false;
    while (scanf("%I64d%I64d",&n,&m)!=EOF)
    {
        if (flag) printf("\n");
            else flag=true;//很有特点的控制格式输出的技巧，我也不记得我是从哪个神牛的博客哪里学过来的呢。
        time=0,NH=0,NC=0;
        nowH=1;
        for (ll i=1; i<=n; i++) scanf("%I64d",&A[i]);
        for (ll i=1; i<=m; i++)
        {
            scanf("%s",s);
            c[i]=s[0];
            if (c[i]=='B') scanf("%I64d",&t[i]);
            else
            {
                scanf("%I64d%I64d",&L[i],&R[i]);
                if (c[i]=='H')
                {
                    scanf("%I64d",&t[i]);
                    NH++;
                    H[NH].Lh=L[i];
                    H[NH].Rh=R[i];
                    H[NH].T=t[i];
                    H[NH].p=i;
                }
                else if (c[i]=='C') scanf("%I64d",&d[i]);
            }
        }
        sort(H+1,H+1+NH,cmp);
        for(ll i=1; i<=NH; i++) h[H[i].p]=i;//双向映射
        build(1,1,n);
        while (H[nowH].T==time && nowH<=NH)
        {
            H[nowH].ANS=query(1,1,n,H[nowH].Lh,H[nowH].Rh);
            nowH++;
        }
        for (ll i=1; i<=m; i++)
        {
            if (c[i]=='C')
            {
                C[++NC]=i;//操作对应的标号存于一个数组中，便于回退。
                time++;
                ***(1,1,n,L[i],R[i],d[i]);
                while (H[nowH].T==time && nowH<=NH)//存在当前时刻的历史查询，可以先查询结果保存下来。
                {
                    H[nowH].ANS=query(1,1,n,H[nowH].Lh,H[nowH].Rh);
                    nowH++;
                }
            }
            else if (c[i]=='Q')
            {
                printf("%I64d\n",query(1,1,n,L[i],R[i]));
            }
            else if (c[i]=='H')
            {
                printf("%I64d\n",H[h[i]].ANS);//当前结果肯定已经被查询了，直接输入。
            }
            else if (c[i]=='B')
            {
                while (time>t[i])
                {
                    ll tep=C[NC];
                    ***(1,1,n,L[tep],R[tep],-d[tep]);//回退等于删掉原来的线段，即加上相反数即可。
                    NC--;
                    time--;
                }
                while (H[nowH-1].T>time) nowH--;
            }
        }
    }
    return 0;
}


  • 标签：线段树 
    • 发表评论：
    天涯博客欢迎您！