首页 > 代码库 > HDU4348 To the moon

HDU4348 To the moon

2024-08-22 17:55:53   219人阅读

Time Limit: 2000MS Memory Limit: 65536KB 64bit IO Format: %I64d & %I64u

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 {A i | 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 {A i | l <= i <= r}. 
3. H l r t: Querying a history sum of {A i | 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 ≤ 10 5, |A [i]| ≤ 10 9, 1 ≤ l ≤ r ≤ N, |d| ≤ 10 4 .. 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 
A 1 A 2 ... A n 
... (here following the m operations. )

Output

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

Sample Input

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 42 40 0C 1 1 1C 2 2 -1Q 1 2H 1 2 1

Sample Output

45591501

Source

2012 Multi-University Training Contest 5

 

可持久化线段树模板题。

对于不同的时间建立不同的新结点，新结点按照线段树的规则连接各个被修改的结点的新址（修改时不在原结点修改，而是新建一个结点（类似于分层图什么的）），没有修改的区域就直接链接到旧树的结点（因此不能用root*2 root*2+1的方式算结点，而要用数组模拟指针记录子结点标号）。

由于新层和旧层修改的值不一样，所以lazy标记是不能持久化的，一层的lazy只能在一层用。具体的解决方法见代码。

↑看到有大神说lazy标记持久化的方法是，对每个lazy记录时间戳，只有其标记时间与当前所要求的状态的时间相同时，才计算。然而看上去好麻烦。

 

代码基本靠抄。

 

看到有人说这题卡内存，就特意把数组开小了，结果依旧MLE。折腾一个多小时无果，怒把数组开到300w，居然A了。

↑想了想，大概MLE是因为动态申请新节点时，因为t数组越界，申请到了超大的节点值，直接炸掉内存，所以MLE而不是RE。

感到内存学问博大精深。

 

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 #define mid (l+r)/210 using namespace std;11 const int mxn=100010;12 int read(){13     int x=0,f=1;char ch=getchar();14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}16     return x*f;17 }18 int n,m;19 int data[mxn];20 struct node{21     int lc,rc;22     LL sum,mk;23 }t[3000010];24 int root[mxn];25 int nct=0;26 int ntime=0;27 void Build(int l,int r,int &rt){28     t[++nct]=t[rt];29     rt=nct;30     if(l==r){31         t[rt].sum=data[l];32         return;33     }34     Build(l,mid,t[rt].lc);35     Build(mid+1,r,t[rt].rc);36     t[rt].sum=t[t[rt].lc].sum+t[t[rt].rc].sum;37     return;38 }39 void add(int L,int R,int v,int l,int r,int &rt){40     t[++nct]=t[rt];41     rt=nct;42     t[rt].sum+=(LL)v*(min(R,r)-max(l,L)+1);43     if(L<=l && r<=R){44         t[rt].mk+=v;45         return;46     }47     if(L<=mid)add(L,R,v,l,mid,t[rt].lc);48     if(R>mid)add(L,R,v,mid+1,r,t[rt].rc);49     return;50 }51 LL query(int L,int R,int l,int r,int rt){52     if(L<=l && r<=R)return t[rt].sum;53     LL res=t[rt].mk*1LL*(min(R,r)-(max(L,l))+1);54     if(L<=mid)res+=query(L,R,l,mid,t[rt].lc);55     if(R>mid)res+=query(L,R,mid+1,r,t[rt].rc);56     return res;57 }58 int main(){59     char op[3];60     int i,j,x,y,a;61     while(~scanf("%d%d",&n,&m)){62         ntime=0;nct=0;63         for(i=1;i<=n;i++)64             data[i]=read();65         Build(1,n,root[0]);66         for(i=1;i<=m;i++){67             scanf("%s",op);68             switch(op[0]){69                 case ‘Q‘:{70                     x=read();y=read();71                     printf("%lld\n",query(x,y,1,n,root[ntime]));72                     break;73                 }74                 case ‘C‘:{75                     x=read();y=read();a=read();76                     ++ntime;77                     root[ntime]=root[ntime-1];78                     add(x,y,a,1,n,root[ntime]);79                     break;80                 }81                 case ‘H‘:{82                     x=read();y=read();a=read();83                     printf("%lld\n",query(x,y,1,n,root[a]));84                     break;85                 }86                 case ‘B‘:{87                     ntime=read();88                     break;89                 }90             }91         }92     }93     return 0;94 }

 

HDU4348 To the moon


联系
我们