首页 > 代码库 > 暑假集训day7
暑假集训day7
从今天开始,进入数据结构专场。
今天讲线段树。
第一题就好丧,调了快一天。
LA 3938
好像没什么可说的,就是细节比较多罢了
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; const int maxn=500010; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } typedef long long LL;LL a[maxn]; typedef pair<int,int>PA; LL sum(int l,int r){return a[r]-a[l-1];} LL sum(PA p){return sum(p.first,p.second);} PA better(PA a,PA b){if(sum(a)!=sum(b))return sum(a)>sum(b)?a:b;return a<b?a:b;} int askl,askr,pre[maxn],suf[maxn];PA sub[maxn]; void build(int ro,int l,int r){ if(l==r){pre[ro]=suf[ro]=l;sub[ro]=PA(l,l);} else{ int mid=(l+r)/2,lc=ro*2,rc=ro*2+1; build(lc,l,mid);build(rc,mid+1,r); LL v1=sum(l,pre[lc]);LL v2=sum(l,pre[rc]); if(v1==v2)pre[ro]=min(pre[lc],pre[rc]); else pre[ro]=v1>v2?pre[lc]:pre[rc]; v1=sum(suf[lc],r);v2=sum(suf[rc],r); if(v1==v2)suf[ro]=min(suf[lc],suf[rc]); else suf[ro]=v1>v2?suf[lc]:suf[rc]; sub[ro]=better(sub[lc],sub[rc]); sub[ro]=better(sub[ro],PA(suf[lc],pre[rc])); } } PA preq(int ro,int l,int r){ if(pre[ro]<=askr)return PA(l,pre[ro]); int mid=(l+r)/2,lc=ro*2,rc=ro*2+1; if(askr<=mid)return preq(lc,l,mid); PA i=preq(rc,mid+1,r);i.first=l; return better(i,PA(l,pre[lc])); } PA sufq(int ro,int l,int r) { if(suf[ro]>=askl) return PA(suf[ro],r); int mid=(l+r)/2,lc=ro*2,rc=ro*2+1; if(askl>mid)return sufq(rc,mid+1,r); PA i=sufq(lc,l,mid);i.second=r; return better(i,PA(suf[rc],r)); } PA ask(int ro,int l,int r) { if(askl<=l&&r<=askr)return sub[ro]; int mid=(l+r)/2,lc=ro*2,rc=ro*2+1; if(askr<=mid)return ask(lc,l,mid); if(askl>mid)return ask(rc,mid+1,r); PA i1=preq(rc,mid+1,r); PA i2=sufq(lc,l,mid); PA i3=better(ask(lc,l,mid),ask(rc,mid+1,r)); return better(PA(i2.first,i1.second),i3); } int main(){ int cnt=0,n,q; while(scanf("%d%d",&n,&q)==2) { a[0]=0;for(int i=1;i<=n;i++)a[i]=a[i-1]+read(); build(1,1,n);printf("Case %d:\n",++cnt); while(q--){ askl=read();askr=read(); PA ans=ask(1,1,n); printf("%d %d\n",ans.first,ans.second); } } return 0; }
RMQ with shift(UVa 12299)
线段树挺简单的、关键就是读入
我用一个快读,直接把字符忽略掉了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=100010; const int INF=947483647; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;if(c==‘\n‘)return INF;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } int n,q,a[maxn],t[3*maxn]; void build(int ro,int l,int r){ if(l==r)t[ro]=a[l]; else{ int mid=(l+r)/2; build(ro*2,l,mid);build(ro*2+1,mid+1,r); t[ro]=min(t[ro*2],t[ro*2+1]); } } int ask(int ro,int l,int r,int x,int y){ if(x>r||y<l) return INF; if(x<=l&&r<=y) return t[ro]; int mid=(l+r)/2; return min(ask(ro*2,l,mid,x,y),ask(ro*2+1,mid+1,r,x,y)); } void change(int ro,int l,int r,int x,int add){ if(l==r){if(x==l){t[ro]=add;}return;} int mid=(l+r)/2; if(x<=mid)change(ro*2,l,mid,x,add); else change(ro*2+1,mid+1,r,x,add); t[ro]=min(t[ro*2],t[ro*2+1]); } int main() { n=read();q=read(); for(int i=1;i<=n;i++)a[i]=read(); build(1,1,n); for(int i=1;i<=q;i++){ char c=getchar();while(c!=‘s‘&&c!=‘q‘)c=getchar(); if(c==‘q‘){ int x=read(),y=read(); printf("%d\n",ask(1,1,n,x,y)); } else{ int x=read(),y=read(); int f=a[x]; while(y!=INF){ change(1,1,n,x,a[y]);a[x]=a[y]; x=y;y=read(); }change(1,1,n,x,f);a[x]=f; } } return 0; }
本文由Yzyet编写,网址为www.cnblogs.com/Yzyet。非Yzyet同意,禁止转载,侵权者必究。
暑假集训day7
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。