网站开发好后版权归谁,用eclipse做jsp网站,甘肃建设厅网站执业注册中心,深圳东门步行街在哪个区题目链接#xff1a;洛谷BZOJ 分析#xff1a; 好像没有什么好说的就是一个平衡树的板子……唯一要注意的就是这里要找的并不是严格的前驱和后继#xff0c;因为如果找到之前某一天的营业额和它相等那么差就是0#xff0c;所以我们仍然在结构体中开一个域cnt来存储同一个元…题目链接洛谷BZOJ 分析 好像没有什么好说的就是一个平衡树的板子……唯一要注意的就是这里要找的并不是严格的前驱和后继因为如果找到之前某一天的营业额和它相等那么差就是0所以我们仍然在结构体中开一个域cnt来存储同一个元素存储了多少次如果a[p].cnt1说明这个元素已经出现了不止一次了那么直接跳出循环返回a[p].val即可。 这一段代码贴在这里 if(vala[p].val){if(a[p].cnt1){ansp;break;}...
} 然后说一下我的沙雕错误……建树的时候手一抽在左子树上压了个INF在右子树上压了个-INF然后敲敲打打找了两个小时的bug…… 对于这件事我只想说妈的智障 全部代码如下 #includebits/stdc.h
#define maxn 40000
using namespace std;
struct treap{int val;int l,r;int dat;int size;int cnt;
}a[maxn];
int tot,root,n,inf0x7fffffff,ans0;inline int read(){int cn0,f1;char c;cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){cncn*10c-0;cgetchar();}return cn*f;
}inline int New(int val){a[tot].valval;a[tot].datrand();a[tot].cnta[tot].size1;return tot;
}inline void update(int p){a[p].sizea[a[p].l].sizea[a[p].r].sizea[p].cnt;
}inline void build_tree(){New(-inf),New(inf);root1;a[1].r2;update(root);
}void zig(int p){int qa[p].l;a[p].la[q].r,a[q].rp,pq;update(a[p].r),update(p);
}void zag(int p){int qa[p].r;a[p].ra[q].l,a[q].lp,pq;update(a[p].l),update(p);
}void insert(int p,int val){if(p0){pNew(val);return;}if(vala[p].val){a[p].cnt,update(p);return;}if(vala[p].val){insert(a[p].l,val);if(a[p].data[a[p].l].dat)zig(p);}else{insert(a[p].r,val);if(a[p].data[a[p].r].dat)zag(p);}update(p);
}int get_pre(int val){int ans1;//a[1].val-infint proot;while(p){if(vala[p].val){if(a[p].cnt1){ansp;break;}if(a[p].l0){pa[p].l;while(a[p].r0)pa[p].r;ansp;}break;}if(a[p].valvala[p].vala[ans].val) ansp;pvala[p].val?a[p].l:a[p].r;}return a[ans].val;
}int get_next(int val){int ans2;// a[2].valinfint proot;while(p){if(vala[p].val){if(a[p].cnt1){ansp;break;}if(a[p].r0){pa[p].r;while(a[p].l0)pa[p].l;ansp;}break;}if(a[p].valvala[p].vala[ans].val) ansp;pvala[p].val?a[p].l:a[p].r;}return a[ans].val;
}int main(){
// freopen(turnover.in,r,stdin);
// freopen(turnover.out,w,stdout);nread();build_tree();srand(19260817);for(register int i1;in;i){int x;xread();insert(root,x);if(i1)ansx;else{if(get_pre(x)-inf){ansget_next(x)-x;continue;}if(get_next(x)inf){ansx-get_pre(x);continue;}ansmin(x-get_pre(x),get_next(x)-x);}
// coutansendl;}printf(%d,ans);return 0;
} 转载于:https://www.cnblogs.com/kma093/p/9744022.html
