1 条题解
-
1
前言
都说线段树分治空间复杂度是 的,我们不妨把它优化到线性!
请确保你会基础的线段树分治。
思路
似乎是个经典的 trick?
考虑线段树分治的过程。
- 往时间序列里加边的信息。
- dfs 一遍线段树。
我们发现第一步很浪费空间。
怎么办?
注意到每条边『插入』的信息可以保存在根结点,在 dfs 时把信息下放并不在本地留副本,然后把边信息回给父亲。
时间复杂度保持不变,空间线性,不过时间常数应该巨大。
理论上也可以解决某些半在线的题目。
Code
使用前向星维护,也不见得慢了多少(这还是在使用 Heap-DSU 的基础上)。
空间低于 10MB。
#include <algorithm> #include <stdio.h> #include <vector> typedef long long llt; typedef unsigned uint;typedef unsigned long long ullt; typedef bool bol;typedef char chr;typedef void voi; typedef double dbl; template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;} template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;} template<typename T>T lowbit(T n){return n&-n;} template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;} template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;} template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;} template<typename T>T power(T base,T index,T mod) { T ans=1%mod; while(index) { if(index&1)ans=ans*base%mod; base=base*base%mod,index>>=1; } return ans; } uint Ra=1,Rb=10007,Rc=114513; struct Rand{uint operator()(){return Ra=Ra*Rb+Rc;}}; namespace Heap_DSU //人类智慧势能并查集 { uint Fath[200005],H[200005]; uint Used[200005],tp; voi bzr(uint n){for(uint i=0;i<n;i++)Fath[i]=i,H[i]=Rand()();} uint find(uint p){return Fath[p]==p?p:find(Fath[p]);} bol connected(uint a,uint b){return find(a)==find(b);} bol merge(uint a,uint b) { a=find(a),b=find(b); if(a==b)return Used[tp++]=a,false; if(H[a]<H[b])std::swap(a,b); Fath[b]=a,Used[tp++]=b; return true; } bol revoke() { if(!tp)return false; uint p=Used[--tp]; if(p==Fath[p])return false; Fath[p]=p;return true; } }; typedef std::pair<uint,uint>Pair; typedef std::pair<Pair,Pair>Pair2; Pair2 P[200005]; uint Last[200005],End[25]; // 使用前向星卡常。 voi insert_edge(uint dep,uint p){Last[p]=End[dep],End[dep]=p;} voi dfs(uint l,uint r,uint dep) { uint cnt=0; for(uint i=End[dep];~i;i=Last[i])if(P[i].second.first<=l&&P[i].second.second>=r) { cnt+=2; Heap_DSU::merge(P[i].first.first<<1,P[i].first.second<<1|1); Heap_DSU::merge(P[i].first.first<<1|1,P[i].first.second<<1); if(Heap_DSU::connected(P[i].first.first<<1,P[i].first.first<<1|1)) { for(uint i=l;i<r;i++)puts("No"); while(cnt--)Heap_DSU::revoke(); return; } } if(r-l==1)puts("Yes"); else{ uint mid=(l+r)>>1; End[dep+1]=-1; for(uint i=End[dep],last=-1,nxt;~i;i=nxt) { nxt=Last[i]; if(!(P[i].second.first<=l&&P[i].second.second>=r)&&P[i].second.first<mid) { ((~last)?Last[last]:End[dep])=nxt; insert_edge(dep+1,i); } else last=i; } dfs(l,mid,dep+1); for(uint i=End[dep+1],nxt;~i;i=nxt)nxt=Last[i],insert_edge(dep,i); End[dep+1]=-1; for(uint i=End[dep],last=-1,nxt;~i;i=nxt) { nxt=Last[i]; if(!(P[i].second.first<=l&&P[i].second.second>=r)&&P[i].second.second>mid) { ((~last)?Last[last]:End[dep])=nxt; insert_edge(dep+1,i); } else last=i; } dfs(mid,r,dep+1); for(uint i=End[dep+1],nxt;~i;i=nxt)nxt=Last[i],insert_edge(dep,i); } while(cnt--)Heap_DSU::revoke(); } int main() { #ifdef MYEE freopen("QAQ.in","r",stdin); #endif uint n,m,k;scanf("%u%u%u",&n,&m,&k),Heap_DSU::bzr(n<<1); End[0]=-1; for(uint i=0;i<m;i++) { scanf("%u%u%u%u",&P[i].first.first,&P[i].first.second,&P[i].second.first,&P[i].second.second); P[i].first.first--,P[i].first.second--; insert_edge(0,i); } dfs(0,k,0); return 0; }
- 1
信息
- ID
- 4025
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 155
- 已通过
- 47
- 上传者