题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4348
给定一个长度为N的数组，要求对数组执行M次指定的区间修改、区间和查询、查询历史版本的区间和、回滚到历史版本。
因为输入数据并没有进行加密，所以完全可以读入所有的数据后进行离线操作（但这样就没意思了，手动滑稽），但如果数据需要前一个查询的结果进行解密，强制在线，那就只能用可持久化线段树，即主席树进行维护。
可持久化数据结构的核心思想就是最大限度地利用之前版本的信息，减少增加记录的空间消耗。对线段树而言，就是将所有未修改的节点指针指向上一个版本的节点。
这一题还有一个要注意的地方，如果更新节点时将节点的lazy_tag向下传递，新增节点，内存是肯定炸光的，因此需要对查询操作特殊处理。
以下是代码，因为使用了指针和struct，稍微改一改就是一个模板（当然也更加难调试）：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int MaxN = 200003;
typedef vector<int> vec;
typedef vec::iterator iter;
int n,m,q;
vec e[MaxN],g[MaxN];
int b[MaxN],blocks;
bool vis[MaxN];
void tarjan(int x,int fa) {
static int low[MaxN],dfn[MaxN],idx;
static bool instk[MaxN];
static stack<int> stk;
low[x]=dfn[x]=++idx;
vis[x]=true,stk.push(x),instk[x]=true;
bool flag=true;
for (iter i=e[x].begin();i!=e[x].end();++i) {
if (flag && *i==fa) {
flag=false;
continue;
}
if (!vis[*i]) {
tarjan(*i,x);
low[x]=min(low[x],low[*i]);
} else if (instk[*i]) {
low[x]=min(low[x],dfn[*i]);
}
}
if (low[x]==dfn[x]) {
int t;
blocks++;
do {
t=stk.top();stk.pop();
b[t]=blocks;instk[t]=false;
} while (t!=x);
}
}
int fa[MaxN],sz[MaxN],dep[MaxN],head[MaxN],id[MaxN],num[MaxN];
void build(int x) {
sz[x]=1;
for (iter i=g[x].begin();i!=g[x].end();++i) {
if (*i==fa[x]) continue;
fa[*i]=x,dep[*i]=dep[x]+1,num[*i]=num[x];
build(*i);
sz[x]+=sz[*i];
}
}
void part(int x) {
static int idx;
id[x]=++idx;
if (head[x]==0) head[x]=x;
int p=0;
for (iter i=g[x].begin();i!=g[x].end();++i) {
if (*i==fa[x]) continue;
if (p==0 || sz[*i]>sz[p]) p=*i;
}
if (p==0) return;
head[p]=head[x];
part(p);
for (iter i=g[x].begin();i!=g[x].end();++i) {
if (*i==fa[x] || *i==p) continue;
part(*i);
}
}
char up[MaxN<<2],down[MaxN<<2];
void cover(char* s ,int p,int l,int r,int ll,int rr) {
if (ll<=l && r<=rr) {
s[p]=2;
return;
}
if (s[p]==2) return;
s[p]=1;
int mid=(l+r)/2;
if (ll<=mid) cover(s,p*2,l,mid,ll,rr);
if (rr>mid) cover(s,p*2+1,mid+1,r,ll,rr);
if (s[p*2]==2 && s[p*2+1]==2) s[p]=2;
}
inline void cover(char* s,int l,int r) { if (l>r) return;cover(s,1,1,blocks,l,r); }
inline bool query(char* s,int x) {
int p=1,l=1,r=blocks,mid;
while (l<r) {
if (s[p]==2) return true;
if (s[p]==0) return false;
mid=(l+r)/2;
if (x<=mid) p=p*2,r=mid;
else p=p*2+1,l=mid+1;
}
return (s[p]!=0);
}
inline void deal(int u,int v) {
while (u!=v) {
if (head[u]==head[v]) {
if (dep[u]<dep[v])
cover(down,id[u]+1,id[v]);
else
cover(up,id[v]+1,id[u]);
break;
}
if (dep[head[u]]<dep[head[v]]) {
int t=head[v];
if (fa[t]==t) cover(down,id[t]+1,id[v]);
else cover(down,id[t],id[v]);
v=fa[t];
} else {
int t=head[u];
if (fa[t]==t) cover(up,id[t]+1,id[u]);
else cover(up,id[t],id[u]);
u=fa[t];
}
}
}
inline void fail() {
puts("No");
exit(0);
}
int main() {
scanf("%d%d%d",&n,&m,&q);
for (int i=1;i<=m;++i) {
int u,v;
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for (int i=1;i<=n;++i) if (!vis[i]) tarjan(i,-1);
for (int i=1;i<=n;++i)
for (iter j=e[i].begin();j!=e[i].end();++j)
if (b[i]!=b[*j]) {
g[b[i]].push_back(b[*j]);
g[b[*j]].push_back(b[i]);
}
for (int i=1;i<=blocks;++i) { sort(g[i].begin(),g[i].end());g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end()); }
int cnt;
for (int i=1;i<=blocks;++i) if (!num[i]) {
fa[i]=i,dep[i]=0,num[i]=++cnt;
build(i);
part(i);
}
for (int i=1;i<=q;++i) {
int u,v;
scanf("%d%d",&u,&v);
if (b[u]==b[v]) continue;
if (num[b[u]]!=num[b[v]]) fail();
deal(b[u],b[v]);
}
for (int i=1;i<=blocks;++i) if (fa[i]!=i) {
if (query(up,i) && query(down,i)) fail();
}
puts("Yes");
return 0;
}