线段树做题总结
发布时间:2020-12-14 04:25:52 所属栏目:大数据 来源:网络整理
导读:A.敌兵布阵 HDU-1166 B.I HATE IT HDU-1754 C.Mayor‘s posters D.Billboard(单点修改,区间最大) ? #includecstring #include cstdlib #include cmath #include cstdio #include iostream #include algorithm #define maxn 200010 #define lson l,m,rt1 #
A.敌兵布阵 HDU-1166 B.I HATE IT HDU-1754 C.Mayor‘s posters D.Billboard(单点修改,区间最大) ? #include<cstring> #include<cstdlib> #include<cmath> #include<cstdio> #include<iostream> #include<algorithm> #define maxn 200010 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; int sgt[maxn<<2],h,w,n,ww; void build(int l,int r,int rt) { sgt[rt]=w; if(r==l) return; int m=(l+r)>>1; build(lson); build(rson); } void update(int l,int rt,int x) { if(l==r) {printf("%dn",l);sgt[rt]-=x;return;} int m=(l+r)>>1; if(x<=sgt[rt<<1]) update(lson,x); else update(rson,x); sgt[rt]=max(sgt[rt<<1],sgt[rt<<1|1]); } int main() { while(~scanf("%d%d%d",&h,&w,&n)) { h=min(h,n); build(1,1); for(int i=1;i<=n;i++) { scanf("%d",&ww); if(sgt[1]>=ww) update(1,1,ww); else printf("-1n"); } } } ? E. Tunnel Warfare(单点修改,区间连续数字个数)? #include<cstring> #include<cstdlib> #include<cmath> #include<cstdio> #include<iostream> #include<algorithm> #define maxn 50010 #define lson l,rt<<1|1 using namespace std; int sgt[maxn<<2],pre[maxn<<2],suf[maxn<<2],a[maxn<<2]; int n,x,tot; char op[10]; void push_up(int rt,int len) { pre[rt]=pre[rt<<1]; suf[rt]=suf[rt<<1|1]; if(pre[rt<<1]==(len+1)>>1) pre[rt]=pre[rt<<1]+pre[rt<<1|1]; if(suf[rt<<1|1]==len>>1) suf[rt]=suf[rt<<1]+suf[rt<<1|1]; } void build(int l,int rt) { if(l==r) {sgt[rt]=pre[rt]=suf[rt]=1;return;} int m=(l+r)>>1; build(lson);build(rson);push_up(rt,r-l+1); } void update(int l,int pos,int x) { if(l==r) {sgt[rt]=pre[rt]=suf[rt]=x;return;} int m=(l+r)>>1; if(pos<=m) update(lson,pos,x); push_up(rt,r-l+1); } int query(int l,int pos) { //printf("%d %d %d %dn",l,suf[rt<<1],pre[rt<<1|1]); if(l==r) return sgt[rt]; int m=(l+r)>>1; if(pos<=m) { if(pos+suf[rt<<1]>m) return suf[rt<<1]+pre[rt<<1|1]; else return query(lson,pos); } else{ if(m+pre[rt<<1|1]>=pos) return suf[rt<<1]+pre[rt<<1|1]; else return query(rson,pos); } } int main() { while(~scanf("%d%d",&n,&m)) { build(1,1); tot=0; while(m--) { scanf("%s",op); if(op[0]==‘Q‘) { scanf("%d",&x); printf("%dn",query(1,x)); } if(op[0]==‘D‘) { scanf("%d",&x); a[++tot]=x; update(1,1,0); } if(op[0]==‘R‘) { x=a[tot--]; update(1,1); } } } } ? F. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |