dfs序

貌似忘写了直到要用才想起来

#include<bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)
using namespace std;
const int maxn=1e5+10;
int n;
struct node
{int l,r;long long sum;int lazy;
}tree[maxn<<2];
int a[maxn];
int in[maxn],out[maxn],tim,v[maxn];
void dfs_(long long x)
{in[x]=++tim;v[x]=true;for (int i=h[x];i;i=nxt[i]){if (v[to[i]]) continue;dfs_(to[i]);}out[x]=tim;
}
void pushdown(int rt)
{if (tree[rt].lazy){int lazy=tree[rt].lazy;tree[rt].lazy=0;tree[lson].lazy += lazy;tree[rson].lazy += lazy;tree[lson].sum += lazy*(tree[lson].r-tree[lson].l+1);tree[rson].sum += lazy*(tree[rson].r-tree[rson].l+1);}
}
void pushup(int rt)
{tree[rt].sum = tree[lson].sum+tree[rson].sum;
}
void build(int rt,int l,int r)
{tree[rt].l=l;tree[rt].r=r;if (l == r){tree[rt].sum=a[l];return;}int mid=(l+r) >> 1;build(lson,l,mid);build(rson,mid+1,r);pushup(rt);
}
void update(int rt,int l,int r,int val)
{if (l<=tree[rt].l && tree[rt].r<=r){tree[rt].lazy += val;tree[rt].sum += val*(tree[rt].r-tree[rt].l+1);return;}pushdown(rt);int mid = (tree[rt].l+tree[rt].r) >> 1;if (l <= mid) update(lson,l,r,val);if (r > mid) update(rson,l,r,val);pushup(rt);
}
long long query(int rt,int l,int r)
{if (l<=tree[rt].l && tree[rt].r<=r){return tree[rt].sum;}pushdown(rt);int mid = (tree[rt].l + tree[rt].r) >> 1;int ans=0x7f7f7f7f7f7f7f7f;if (r<=mid) ans=min(ans,query(lson,l,r));else if (l>mid) ans=min(ans,query(rson,l,r));else return ans;
}
int main()
{cin >> n >> m;return 0;
}