做门票的网站,网站运营难做吗,易居销售系统,百度app优化洛谷传送门 文章目录题目描述解析代码题目描述 解析
利用倍增#xff0c;设计dp慢慢敲即可。。。 注意距离累加在一起会爆int#xff0c;需要ll 特判条件非常之复杂。。。 心力交瘁#xff0c;就酱了
代码
#include bits/stdc.h
using namespace std;
#define ll…洛谷传送门
文章目录题目描述解析代码题目描述 解析
利用倍增设计dp慢慢敲即可。。。 注意距离累加在一起会爆int需要ll 特判条件非常之复杂。。。 心力交瘁就酱了
代码
#include bits/stdc.h
using namespace std;
#define ll long long
typedef pairll,ll pr;
const int N 3e5 100;
int n,m;
struct node{int id,h;bool operator (const node y)const{return hy.h;}
}p[N];
int pos[N];
int l[N],r[N],h[N];
bool ok(int x){return x1xn;}
ll jl(int x,int y){return abs(p[x].h-p[y].h);}
struct node2{ll dist,id;bool operator (const node2 y)const{if(dist!y.dist) return disty.dist;else return h[id]h[y.id];}
};
node2 fir[N],sec[N];
void del(int x){r[l[x]]r[x];l[r[x]]l[x];return;
}
int pl[N][30];
ll dis[3][N][30];
int x0;
void solve(){sort(p1,p1n);for(int i1;in;i) pos[p[i].id]i;for(int i1;in;i){l[i]i-1;r[i]i1;}r[0]1;l[n1]n;for(int i1;in;i){int plpos[i];int l10,l20,r10,r20;int num0;node2 coi[5];if(ok(l[pl])) l1l[pl],coi[num](node2){jl(pl,l1),p[l1].id};if(l1ok(l[l1])) l2l[l1],coi[num](node2){jl(pl,l2),p[l2].id};if(ok(r[pl])) r1r[pl],coi[num](node2){jl(pl,r1),p[r1].id};if(r1ok(r[r1])) r2r[r1],coi[num](node2){jl(pl,r2),p[r2].id};sort(coi1,coi1num);if(num1) fir[i]coi[1];if(num2) sec[i]coi[2];del(pl);//printf(i%d fir%d sec%d\n,i,fir[i].id,sec[i].id);}for(int i1;in;i){if(sec[i].id) pl[i][0]sec[i].id;else pl[i][0]i;}for(int i1;in;i){if(pl[i][0]!ifir[pl[i][0]].id) pl[i][1]fir[pl[i][0]].id;else pl[i][1]pl[i][0];}for(int i1;in;i){if(sec[i].id) dis[1][i][0]sec[i].dist;else dis[1][i][0]0;dis[2][i][0]0;}for(int i1;in;i){dis[1][i][1]dis[1][i][0];if(pl[i][0]!ifir[pl[i][0]].id)dis[2][i][1]fir[pl[i][0]].dist;else dis[2][i][1]0;}for(int k2;(1k)n;k){for(int i1;in;i){pl[i][k]pl[pl[i][k-1]][k-1];dis[1][i][k]dis[1][i][k-1]dis[1][pl[i][k-1]][k-1];dis[2][i][k]dis[2][i][k-1]dis[2][pl[i][k-1]][k-1];}}
}
pairll,ll find(int st,int x){
// printf(ask: st%d x%d\n,st,x);ll disa0,disb0,tot0;int pplst;for(int k20;k0;k--){if((1k)n) continue;ll sumadis[1][ppl][k],sumbdis[2][ppl][k];if(sumasumbtotx) continue;totsumasumb;disasuma;disbsumb;pplpl[ppl][k];}
// printf( pl%d disa%d disb%d\n,ppl,disa,disb);return make_pair(disa,disb);
}
void test(){for(int k0;k3;k){for(int i1;in;i){printf(i%d k%d pl%d dis1%d dis2%d\n,i,k,pl[i][k],dis[1][i][k],dis[2][i][k]);}}return ;
}
int main() {scanf(%lld,n);for(int i1;in;i){scanf(%lld,p[i].h);h[i]p[i].h;p[i].idi;}solve();//test();scanf(%lld,x0);double mn2e16,temp;int anspl;for(int i1;in;i){pr ofind(i,x0);//printf(st%d disa%d disb%d\n,i,o.first,o.second);temp o.second0?2e15:1.0*o.first/o.second;if(tempmn){mntemp;anspli;}else if(tempmnp[pos[anspl]].hp[pos[i]].h) anspli;}printf(%lld\n,anspl);scanf(%lld,m);int s,x;for(int i1;im;i){scanf(%d%d,s,x);pr ofind(s,x);printf(%lld %lld\n,o.first,o.second);}return 0;
}
/*
10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7
*/
