利用树的dfs序解决问题：
就是dfs的时候记录每个节点的进入时间和离开时间，这样一个完整的区间就是一颗完整的树，就转化成了区间维护的问题。
比如hdu3887 本质上是一个求子树和的问题
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
#define MAXN (200000+10)
#define lowbit(i) (i&(-i))
int n,m;
struct BIT{
int t[MAXN];
BIT(){memset(t,,sizeof(t));}
void init(){memset(t,,sizeof(t));}
int _query(int a){
int ans=;
for (int i=a;i>=;i-=lowbit(i)) ans+=t[i];
return ans;
}
void modify(int a,int x){
for (int i=a;i<=n;i+=lowbit(i)) t[i]+=x;
} int query(int a,int b){
return _query(b)-_query(a-);
}
}T;
int timemark;
int intime[MAXN],outime[MAXN];
int data[MAXN];
int f[MAXN];
int head[MAXN],next[MAXN],e[MAXN],countside;
void buildside(int a,int b){
e[countside]=b;
next[countside]=head[a];
head[a]=countside++;
}
/*
void dfs(int x,int fa){
intime[x]=timemark++;
for (int i=head[x];i>0;i=next[i]){
if (e[i]!=fa){
dfs(e[i],x);
}
}
outime[x]=timemark++;
}
*/ stack<int> s;
bool instack[MAXN];
void dfs(int root){
memset(instack,false,sizeof instack);
s.push(root);
intime[root]=timemark++;
instack[root]=true;
while (!s.empty()){
bool loop=false;
int now=s.top();
for (int i=head[now];i>;i=next[i]){
if (!instack[e[i]]){
s.push(e[i]);
instack[e[i]]=true;
intime[e[i]]=timemark++;
loop=true;
break;
}
}
if (loop) continue;
s.pop();
outime[now]=timemark++;
}
} int main (int argc, char *argv[])
{
int p;
int a,b;
char cmd[]; while (){
scanf("%d%d",&n,&p); if (n== && p==) break; memset(head,,sizeof head);
memset(next,,sizeof next);
memset(e,,sizeof e); countside=;
for (int i=;i<=n-;i++){
scanf("%d%d",&a,&b);
buildside(a,b);
buildside(b,a);
} timemark=;
dfs(p); /*for (int i=1;i<=n;i++) cout<<intime[i]<<" "<<outime[i]<<endl;*/ int N=n;
n=n*;
T.init();
for (int i=;i<=n;i++){
data[i]=;
T.modify(i,);
} for (int i=N;i>=;i--){
f[i]=(T.query(intime[i],outime[i])-)/;
T.modify(intime[i],-);
T.modify(outime[i],-);
} for (int i=;i<=N-;i++) printf("%d ",f[i]);
printf("%d\n",f[N]);
}
return ;
}
直接dfs爆栈了，所以我写了一个手工栈。结果后来发现这样就行了QAQ
#pragma comment(linker,"/STACK:100000000,100000000")
WTF。。。涨姿势了
再就是对于那种复杂的序列操作问题，比如文本编辑器，我发现了C++ 里还有rope这个东西。当然这不是标准STL的，这是SGI STL的一部分。但是如果比赛的时候能用就爽了。。。不管怎么说先记录一下，平时也是蛮实用的。
rope就是一个能支持各种操作的序列，crope就是rope的字符串版本。rope自带各种炫酷的功能，时间各种logn，就连空间也超小。据说内部实现的是一个可持久化的平衡数并且加上共享节点。Orz
NOI 的那道文本编辑器
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <ext/rope>
using namespace std;
using namespace __gnu_cxx;
crope List;
int n,now,k;
char s[];
int main()
{
char cmd[];
int i;
for (scanf("%d",&n);n--;)
{
scanf("%s",cmd);
if (cmd[]=='M') scanf("%d",&now);
else if (cmd[]=='I')
{
scanf("%d%*c",&k);
for (i=;i<k;i++) do
{
scanf("%c",&s[i]);
}while(s[i]=='\n');
s[k]=;
List.insert(now,s);
}
else if (cmd[]=='D')
{
scanf("%d",&k);
List.erase(now,k);
}
else if (cmd[]=='G')
{
scanf("%d",&k);
List.copy(now,k,s);
s[k]=;
puts(s);
}
else if (cmd[]=='P') now--;
else now++;
}
return ;
}