BZOJ3631 松鼠的新家
目录
- BZOJ3631 松鼠的新家
- 题解
- ｃｏｄｅ
BZOJ3631 松鼠的新家
题目传送门
题解
又是一道树剖题，对于这个访问顺序，我们用树剖把路径\(a[i],a[i+1]\)上的每个点都加1，但是这样会重复计算，所以我们每次路径修改的时候，不修改起点，最后把\(a[1]\)的贡献加上，并且把\(a[n]\)的贡献减掉就行了。
ｃｏｄｅ
#include
using namespace std;
typedef long long ll;
bool Finish_read;
templateinline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
templateinline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
templateinline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
templateinline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=3e5+500;
int n,tot;
int a[maxn];
struct edge {int to,nxt;
}E[maxn<<1];
int head[maxn],pos[maxn],idx[maxn],heav[maxn],res[maxn],sz[maxn],fa[maxn],dep[maxn],top[maxn];
/*==================Define Area================*/
void addedge(int u,int v) {E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;E[++tot].to=u;E[tot].nxt=head[v];head[v]=tot;
}namespace SegmentTree {struct node {int l,r,sz,v;int lazy;}t[maxn<<2];#define ls(o) o<<1#define rs(o) o<<1|1void Update(int o) {t[o].v=t[ls(o)].v+t[rs(o)].v;}void Pushdown(int o) {if(!t[o].lazy) return ;t[ls(o)].v+=t[ls(o)].sz*t[o].lazy;t[rs(o)].v+=t[rs(o)].sz*t[o].lazy;t[ls(o)].lazy+=t[o].lazy;t[rs(o)].lazy+=t[o].lazy;t[o].lazy=0;}void Build(int o,int l,int r) {t[o].l=l;t[o].r=r;t[o].sz=r-l+1;if(l==r) return ;int mid=(l+r)>>1;if(mid>=l) Build(ls(o),l,mid);if(mid=l&&t[o].r<=r) {t[o].v+=t[o].sz*v;t[o].lazy+=v;return ;}Pushdown(o);int mid=(t[o].l+t[o].r)>>1;if(mid>=l) Modify(ls(o),l,r,v);if(midmxson) mxson=sz[to],heav[o]=to;}}int cnt=0;void Dfs2(int o,int topp) {idx[o]=++cnt;top[o]=topp;pos[cnt]=o;if(!heav[o]) return ;Dfs2(heav[o],topp);for(int i=head[o];~i;i=E[i].nxt) {int to=E[i].to;if(!idx[to]) Dfs2(to,to);} }void TreeAdd(int x,int y) {Modify(1,idx[x],idx[x],-1);while(top[x]!=top[y]) {if(dep[top[x]]dep[y]) swap(x,y);Modify(1,idx[x],idx[y],1);return ;}
}
using namespace poufen;int main() {memset(head,-1,sizeof head);read(n);for(int i=1;i<=n;i++) {read(a[i]);}for(int i=1,u,v;i 转载于:https://www.cnblogs.com/Apocrypha/p/9453661.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！