第二次被vector卡空间。。。但凡用到了vector，空间复杂度就别想算对了。。。以后少用vector，多用链式前向星。（特别是空间比较紧的时候）
还有一些实现上的失误，
a=max(1,i-R[i]); b=max(1,i-L[i]); 改成 a=i-R[i]; b=i-L[i]; 就对了，因为前面的代码会导致不一样的结果。对于这种问题，我只能说对于那些比较关键的代码，应该仔细思考这样写会不会导致一些意料之外的后果。（这是属于实现的问题）
可能一开始没仔细想，就随便实现了，然后到后面就会自然地认为这么写是对的，在一开始写代码的时候就应该写对它，检查的时候也应该关注这方面的问题。
其实自己线段树优化连边好像一开始就没学会，简直乱搞。
应该是父节点向两个儿子节点各连一条距离为0的边，所有叶子节点向对应节点连一条距离为0的边就好了，而不是直接区间内所有点都暴力连。。。
参考博客：http://blog.csdn.net/gengmingrui/article/details/50729968
看了下网上的做法，大多数是改造Dijkstra。
正常的Dijkstra是每次找一个还未使用过的距离最小的节点，然后用它去更新所有和它相邻的节点。
算法保证使用过的节点距离一定最优了，如果一个节点还没被使用而且距离最小，那么这个节点一定也是一个距离最优的节点，我们就可以放心地用它去更新其他节点，然后将之抛弃了。任何时刻可以用于更新其他节点的节点只有一个，那就是距离最小的节点，因为Dijkstra只适用于非负的图，因此距离最小的节点不可能再被别人更新，所以才可以去更新别人。同时这个节点也算是物尽其用了，所以我们可以将之抛弃。我们必须按照某种顺序使用点和边来实现算法，而边又依附于点，因此按照点距离大小的顺序是很好的选择。
当然，最短路算法的思想有很多，具体实现也有很多，Dijkstra只是一种按拓扑序动态规划的思想，具体实现也只是针对最一般的情况。事实上如果情况不那么一般，Dijkstra算法的具体实现当然也可以有针对性地千变万化。
比如在本题中，图是线性的，关系是连续的，点与点之间的关系不再那么拓扑，而常规的Dijkstra又无法在规定的时间内得到答案，我们就可以尝试用其思想创造一个算法。
思想还是一样的，拓扑序的动态规划，其实动态规划方面基本上不会有什么变化，状态定义无非就是和距离相关，状态转移无非就是用一个点的所有边去更新其他附属的节点。
在本题中，每个点有且只有一个传送门，这个传送门可以往两边传送一段特定范围的距离，而且无论距离多远，花费固定。
常规算法之所以无法解决，是因为点不少，而且边太多。但是点的排布（在一条线上）和边的排布（一段连续的区间）实在太有规律了，因此对算法进行改造的可能性和必要性都是很足的。一般来讲这类单点连到区间的问题都可以用线段树优化连边来解决，本题也是可以这样解决的，只不过时间会久一些，空间比较吃紧。
1<=n<=2e5，那么边的个数最多可以是O（n^2）级别的，光是枚举一遍就超时了，而且这种数据题目一定是会给的（太容易出了）。
我们必须要把重点放在点上，尝试用枚举点的时间复杂度来完成这个问题。
这就要求我们每个点只能枚举常数次。点刚好是连成一条线的，边也是连续的，如果可以把枚举后的点都缩掉或删掉，使得枚举边的时候能够跳过那些已经枚举过的点，时间复杂度就满足了。
但是主要问题有两个。
1、如何缩掉或删掉。
2、如何保证枚举一次后就可以抛弃（要求最优）。
还是按照拓扑序的动态规划，但是顺序有所不同。
我们这次要求更新的顺序是，更新后保证最优，然后就可以将其抛弃。而不是常规算法的要求了。
显然我们直接用优先队列去维护更新后保证最优的节点就好了。（就是更新后距离最小的节点，因为边非负，所以除此之外没有别人能更新它了）但是这样做的后果是很糟糕的，因为优先队列中的节点个数最差会有O（n^2）个，时间复杂度达到O（n^2logn），无法接受。
所幸的是一个传送门的出口虽然有很多，但是入口只有一个，一个入口也只有一个传送门，而且花费固定。我们就可以用入口来代表所有出口。
这样第2个问题就解决了。
关于第1个问题的话，如果删掉，很不现实，因为删除就涉及了很多合并，维护的操作，（点，边的数据都要大量修改）这本身也是需要时间复杂度的，而且不好实现。
因此缩掉或略过是一个好主意。
如果一个点已经被抛弃，我们就将其标记，并且记录其右边（或左边）第一个没被抛弃的节点。
这会涉及大量点或集合的合并，并查集是一个好的解决办法。
参考博客：
http://blog.csdn.net/u013007900/article/details/47338385
http://www.cnblogs.com/oneshot/p/4709207.html
看了别人的代码，以为自己懂了，然后WA了一下午不知所以。
我只能说，以后最好还是要看懂别人的文字说明以后，再去看代码什么的，否则你可能只是以为自己懂了，然后浪费很多时间。
线段树优化连边代码
#include<stdio.h> #include<limits.h> #include<queue> #define ls (now<<1) #define rs (ls|1) #define m ((l+r)>>1) using namespace std; typedef long long ll; const int maxn = 200010; const int maxm = maxn*50; const ll inf = LONG_LONG_MAX>>2; struct Edge { int v,n,w; }edges[maxm]; int head[maxn<<3],tot; void Init(int n) { tot=0; for(int i=0;i<=n;i++) head[i]=-1; } void add(int u,int v,int w) { edges[tot].v=v; edges[tot].w=w; edges[tot].n=head[u]; head[u]=tot++; } struct HeapNode { ll d; int u; bool operator < (const HeapNode& rhs) const { return d>rhs.d; } }; struct Dijkstra { int n; ll d[maxn<<3]; bool done[maxn<<3]; void init(int n) { this->n=n; Init(n); } void dijkstra(int s) { for(int i=0;i<=n;i++) { done[i]=0; d[i]=inf; } d[s]=0; priority_queue<HeapNode>Q; Q.push((HeapNode){0,s}); while(!Q.empty()) { HeapNode now = Q.top(); Q.pop(); int u = now.u; if(done[u]) continue; done[u]=true; for(int e = head[u];~e;e=edges[e].n) { int v = edges[e].v; if(d[v]>d[u]+edges[e].w) { d[v]=d[u]+edges[e].w; Q.push((HeapNode){d[v],v}); } } } } }DIJ; int n; int L[maxn],R[maxn],C[maxn]; void build(int l,int r,int now) { if(l==r) { add(now+n,l,0); return; } add(now+n,ls+n,0); add(now+n,rs+n,0); build(l,m,ls); build(m+1,r,rs); } void qry(int l,int r,int now,int pos,int ql,int qr) { if(r<ql||l>qr) return; if(ql<=l&&r<=qr) { add(pos,now+n,C[pos]); return; } qry(l,m,ls,pos,ql,qr); qry(m+1,r,rs,pos,ql,qr); } void solve() { scanf("%d",&n); DIJ.init(n<<3); build(1,n,1); for(int i=1;i<=n;i++) scanf("%d",L+i); for(int i=1;i<=n;i++) scanf("%d",R+i); for(int i=1;i<=n;i++) { scanf("%d",C+i); int a,b; a=i-R[i]; b=i-L[i]; qry(1,n,1,i,a,b); a=i+L[i]; b=i+R[i]; qry(1,n,1,i,a,b); } DIJ.dijkstra(1); for(int i=1;i<=n;i++) printf("%lld%c",DIJ.d[i]==inf?-1:DIJ.d[i],i==n?'\n':' '); } int main() { int T; scanf("%d",&T); while(T--) solve(); return 0; }改造Dijkstra代码
