在线推广网站的方法有哪些,wordpress自定义页面编码,苏州品牌网站设计企业,wordpress外贸LOJBZOJ洛谷 又是一个三OJ rank1#xff01;w \(Description\) #xff08;还是感觉#xff0c;为啥非要出那种题目背景啊-直接说不好么#xff09; 给定一棵树和一个路径集合#xff08;每条路径有一个权值#xff09;。\(Q\)次询问#xff0c;每次询问给定一条路径w \(Description\) 还是感觉为啥非要出那种题目背景啊-直接说不好么 给定一棵树和一个路径集合每条路径有一个权值。\(Q\)次询问每次询问给定一条路径求路径集合中完全被这条路径包含的路径中权值第\(k\)大的是多少。\(n,m,Q\leq40000\)。 \(Solution\) 首先考虑一条路径\((a,b)\)完全包含路径\((u,v)\)需要满足什么条件。 记\(L[x]\)为\(x\ DFS\)序的编号\(R[x]L[x]size[x]-1\)为\(x\)子树\(DFS\)序编号的最后一个。 若\(LCA(u,v)\neq u\)那么\(L[u]\leq L[a]\leq R[u],\ L[v]\leq L[b]\leq R[v]\)。也即点\((L[a],L[b])\)在矩形\([L[u]\sim R[u],\ L[v]\sim R[v]]\)中。 若\(LCA(u,v)u\)记\(w\)为\(u\to v\)路径上的第二个点\(u\)在\(v\)子树方向上的儿子则\(a\)在\(w\)子树外\(b\)在\(v\)子树内即\(L[a]\)在区间\([1,L[w]-1]\bigcup[R[w]1,n]\)中\(L[b]\)在\([L[v],R[v]]\)中。 那么每个盘子就是一个矩形每个水果是一个点我们要对每个点求包含它的矩形中第\(k\)大的是多少。 整体二分扫描线。 具体先把矩形拆成扫描线再对扫描线按权值排序。每次加入权值\(\leq mid\)的扫描线同时处理每个询问。 若对于一个询问包含它的矩形个数\(\geq k\)则它的答案\(\leq mid\)否则\(k\)减掉对应个数它的答案\(\gt mid\)。 细节判\(LCA(u,v)\)是否\(u\)可以直接判\(v\)在\(u\)的子树里。 要让修改和询问的\(x\)都小于等于\(y\)。 最好对权值离散化一下下。 树状数组是区间修改单点查询。。差分一下。 变量名写的有点恶心- //15268kb 1128ms
#include cstdio
#include cctype
#include algorithm
#define gc() getchar()
#define MAXIN 300000
//#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N40005,MN2;int Enum,H[N],nxt[N1],ho[N1],val[N],L[N],R[N],Ans[N],fa[N],dep[N],sz[N],son[N],top[N];
char IN[MAXIN],*SSIN,*TTIN;
struct Quries
{int x,y,k,id;bool operator (const Quries a)const{return xa.x;}
}q[N],tmpq1[N],tmpq2[N];
struct OPT
{int p,l,r,v;bool operator (const OPT a)const{return pa.p;}
}opt[N2],tmpo1[M],tmpo2[M];
struct BIT
{int n,t[N];#define lb(x) (x-x)inline void Modify(int l,int r,int v){for(int pl; pn; plb(p)) t[p]v;for(int pr1; pn; plb(p)) t[p]-v;}inline int Query(int p){int res0;for(; p; p^lb(p)) rest[p];return res;}
}T;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-48,cgc());return now;
}
inline void AE(int u,int v)
{ho[Enum]v, nxt[Enum]H[u], H[u]Enum;ho[Enum]u, nxt[Enum]H[v], H[v]Enum;
}
inline int Jump(int u,int v)
{int lasv;while(top[u]!top[v]) vfa[lastop[v]];return uv?las:son[u];
}
void DFS1(int x)
{int mx0; sz[x]1;for(int iH[x],v; i; inxt[i])if((vho[i])!fa[x]) fa[v]x, dep[v]dep[x]1, DFS1(v), sz[x]sz[v], sz[v]mx(mxsz[v],son[x]v);
}
void DFS2(int x,int tp)
{static int Index0;top[x]tp, L[x]Index;if(son[x]){DFS2(son[x],tp);for(int iH[x],v; i; inxt[i])if((vho[i])!fa[x]v!son[x]) DFS2(v,v);}R[x]Index;
}
void Solve(int l,int r,int ho,int to,int hq,int tq)
{if(lr||hoto||hqtq){for(int ihq,vval[l]; itq; i) Ans[q[i].id]v;return;}int mlr1,vval[m],nowho,to10,to20,tq10,tq20;for(int ihq; itq; i){while(nowto opt[now].pq[i].x)if(std::abs(opt[now].v)v) T.Modify(opt[now].l,opt[now].r,opt[now].v0?1:-1), tmpo1[to1]opt[now];else tmpo2[to2]opt[now];int tT.Query(q[i].y);if(q[i].kt) q[i].k-t, tmpq2[tq2]q[i];else tmpq1[tq1]q[i];}while(nowto)if(std::abs(opt[now].v)v) T.Modify(opt[now].l,opt[now].r,opt[now].v0?1:-1), tmpo1[to1]opt[now];else tmpo2[to2]opt[now];for(int iho,p0; pto1; opt[i]tmpo1[p]);for(int ihoto1,p0; pto2; opt[i]tmpo2[p]);for(int ihq,p0; ptq1; q[i]tmpq1[p]);for(int ihqtq1,p0; ptq2; q[i]tmpq2[p]);Solve(l,m,ho,hoto1-1,hq,hqtq1-1), Solve(m1,r,hoto1,to,hqtq1,tq);
}int main()
{int nread(),mread(),Qread();for(int i1; in; i) AE(read(),read());DFS1(1), DFS2(1,1);int tot0;for(int i1; im; i){int uread(),vread(); val[i]read();if(L[u]L[v]) std::swap(u,v);if(L[v]L[u]||L[v]R[u]){opt[tot](OPT){L[u],L[v],R[v],val[i]};if(R[u]n) opt[tot](OPT){R[u]1,L[v],R[v],-val[i]};}else{int wJump(u,v);//if(L[w]1) 这个显然不用判啊- 但是下面那个要判啊 opt[tot](OPT){1,L[v],R[v],val[i]}, opt[tot](OPT){L[w],L[v],R[v],-val[i]};if(R[w]n) opt[tot](OPT){L[v],R[w]1,n,val[i]}, opt[tot](OPT){R[v]1,R[w]1,n,-val[i]};//加上可能的pn1的操作好惹以便清空树状数组。}}for(int i1,u,v; iQ; i)uread(),vread(),q[i](Quries){std::min(L[u],L[v]),std::max(L[u],L[v]),read(),i};std::sort(opt1,opt1tot), std::sort(q1,q1Q), std::sort(val1,val1m);int cnt1;for(int i2; im; i) if(val[i]!val[i-1]) val[cnt]val[i];T.nn, Solve(1,cnt,1,tot,1,Q);for(int i1; iQ; printf(%d\n,Ans[i]));return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/10699072.html
