V
主页
【算法强化】【综合性杂题选讲-2】Kruskal重构树+可持久化线段树 P7834[ONTAK2010]Peaks加强版-信息学竞赛
发布人
代码不太贴得下，删了一部分 #include<bits/stdc++.h> using namespace std;// struct edge{ int x,y,w; bool operator <(const edge b){return w<b.w;} }e[N];int n,m,Q,a[N],fx,fy,cnt,b[N],tot,l[N],rt[N],T,S; int f[N],val[N],lastans,u,x,k,L[N],R[N],up[N][22],node; vector<int> v[N];struct Node{int ls,rs,num;}tr[M];char c; inline int find(int x){return (f[x]==x?x:f[x]=find(f[x]));} inline int read(){ // } inline void write(int x){ // } inline void add(int& i,int j,int l,int r,int k){ i=++node,tr[i]=tr[j],tr[i].num++; if(l==r)return; int mid=(l+r)>>1; if(k<=mid)add(tr[i].ls,tr[j].ls,l,mid,k); else add(tr[i].rs,tr[j].rs,mid+1,r,k); } inline int query(int i,int j,int l,int r,int k){ if(l==r)return l; int mid=(l+r)>>1,s=tr[tr[j].ls].num-tr[tr[i].ls].num; if(s>=k)return query(tr[i].ls,tr[j].ls,l,mid,k); else return query(tr[i].rs,tr[j].rs,mid+1,r,k-s); } inline void dfs(int x,int fa){ if(x<=n)L[x]=R[x]=++T,add(rt[T],rt[T-1],1,tot,l[x]); L[x]=(x>n?1e9:T),up[x][0]=fa; for(int i=1;i<=20;i++)up[x][i]=up[up[x][i-1]][i-1]; for(int t:v[x])dfs(t,x), L[x]=min(L[x],L[t]),R[x]=max(R[x],R[t]); } int main(){ n=read(),m=read(),Q=read(),cnt=n,val[0]=(1LL<<31)-1; for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i]; sort(b+1,b+n+1),tot=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++) l[i]=lower_bound(b+1,b+tot+1,a[i])-b; for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].w=read(); sort(e+1,e+m+1); for(int i=1;i<=2*n-1;i++)f[i]=i; for(int i=1;i<=m&&cnt<2*n-1;i++){ fx=find(e[i].x),fy=find(e[i].y); if(fx!=fy)f[fx]=f[fy]=++cnt,val[cnt]=e[i].w, v[cnt].push_back(fx),v[cnt].push_back(fy); } for(int i=cnt;i>=1;i--)if(!L[i]&&!R[i])dfs(i,0); while(Q--){ u=read(),x=read(),k=read(), u=(u^lastans)%n+1,k=(k^lastans)%n+1,x^=lastans; for(int i=20;i>=0;i--)if(val[up[u][i]]<=x)u=up[u][i]; if(k>R[u]-L[u]+1) {write(-1),putchar('\n'),lastans=0;continue;} write(lastans=b[query(rt[L[u]-1],rt[R[u]],1,tot, (R[u]-L[u]+1-k+1))]),putchar('\n'); } return 0; } 这题上难度了
打开封面
下载高清视频
观看高清视频
视频下载器
【算法强化】【综合性杂题选讲-3】[NOI2018]归程 Kruskal重构树+Dijkstra最短路
【算法进阶】【严格次小生成树】Kruskal最小生成树+树上倍增详解-信息学竞赛
【算法进阶】【虚树】虚树的建立与简单应用-信息学竞赛
【算法进阶】【动态规划进阶技巧（一）】动态规划较难技巧讲解-信息学竞赛
河北科技学院录取通知书一塌糊涂！学校回应，网友劝退！
⚡竞赛，我有四不学⚡这4种人不适合学竞赛！
【算法进阶】【codeforces杂题选讲（一）】codeforces经典题目讲解-信息学竞赛
【算法进阶】【树分治进阶】点分树的基本概念及应用-信息学竞赛
【算法强化】【动态规划-6动态动态规划】ddp动态动态规划，树形动态规划，树链剖分，广义矩阵乘法-信息学竞赛
【算法强化】【综合性杂题选讲-1】一道题多倍经验，值得一刷！P2831 [NOIP2016 提高组] 愤怒的小鸟 P3311 [SDOI2014] 数数
【算法进阶】【树上技巧】一些比较常见的树上trick-信息学竞赛
【算法强化】【线段树与矩阵乘法（一）】数据结构与线性代数的结合-信息学竞赛
【算法进阶】【线段树的合并与分裂】合并与分裂：均摊复杂度之美-信息学竞赛
【算法强化】【AC自动机的应用】AC自动机与动态规划题目详解-信息学竞赛
【算法强化】【省选根号数据结构】分块、莫队、根号分治讲解与经典例题-信息学竞赛
【算法进阶】【扫描线进阶】扫描线的应用，数据结构维护扫描线-信息学竞赛
【算法进阶】【前后缀优化建图】前后缀建图技巧-信息学竞赛
【算法进阶】【简单线段树题目】线段树简单练习题P2787 语文1（chin1）- 理理思维-信息学竞赛
【算法强化】【平衡树进阶（一）】fhq treap解决复杂区间操作类问题-信息学竞赛
【算法进阶】【杂题选讲】简单网络流建模P2071座位安排-信息学竞赛
【算法进阶】【字符串-哈希算法】哈希算法、哈希加密算法及哈希例题讲解-信息学竞赛
【算法进阶】【动态规划百练】思维与线段树优化动态规划[ARC159D] LIS 2-信息学竞赛
【算法进阶】【动态规划百练】简单状压dp与滚动数组优化 P5005 中国象棋 - 摆上马 -信息学竞赛
【算法强化】【省选根号数据结构（三）】分块、莫队、根号分治的技巧-信息学竞赛
【算法进阶】【Boruvka最小生成树】稠密图的最小生成树算法-信息学竞赛
【算法进阶】【动态规划百练-IOI1998 Polygon】上古IOI动态规划题目讲解-信息学竞赛
听说竞赛生都是时间管理大师？学科竞赛该如何做好时间管理？
【算法进阶】【可持久化线段树的应用】可持久化线段树的构建与应用，静态区间mex问题-信息学竞赛
会算法的猩猩-合肥市信息学竞赛-小学生-2019年-成绩统计(score)
【算法进阶】【树链剖分】树链剖分（重链剖分）精讲-信息学竞赛
【算法进阶】【高斯消元】高斯消元解决n元一次方程组-信息学竞赛
【算法强化】【codeforces杂题选讲（二）】codeforces3000难度好题选讲-信息学竞赛
【算法进阶】【简单博弈论-Nim游戏】博弈论简介及Nim游戏必胜策略推导过程-信息学竞赛
【算法进阶】【反悔贪心】反悔贪心及例题CF865D Buy Low Sell High讲解-信息学竞赛
兴趣狭窄有多窄？带你了解孤独症儿童的超离谱兴趣爱好
【算法入门】普及组算法复习与提高（一）-信息学竞赛
【算法进阶】【优先队列】优先队列 ST表 NOI2010真题 P2048 [NOI2010] 超级钢琴精讲-信息学竞赛
【算法进阶】【线段树的应用】线段树维护动态区间最大子段和P4513 小白逛公园-信息学竞赛
【算法进阶】【拉格朗日插值】拉格朗日插值，解决多点确定函数问题-信息学竞赛
【复赛冲刺训练】普及组满分训练（一）动态规划总结与练习-信息学竞赛
