首页 > 代码库 > spoj GSS线段树以及二维树状数组合集
spoj GSS线段树以及二维树状数组合集
T1 维护lmax 向左延伸的最大值，rmax同理，sum区间和，ans答案。
转移见operator +
#include<bits/stdc++.h>#define mid (l+(r-l)/2)#define ls (rt<<1)#define rs (rt<<1|1)#define int long longusing namespace std;const int N =(int)1e5+10;struct TREE { int lef,rig,sum,ans; int l,r; void clear() {lef=rig=sum=ans=0;} void debug() { printf("%d %d %d %d %d %d\n",l,r,lef,rig,sum,ans); } }tr[N<<2];int a[N];TREE operator + (TREE l,TREE r) { TREE rt;rt.clear(); rt.l=l.l;rt.r=r.r; rt.lef=max(l.sum+r.lef,l.lef); rt.rig=max(r.sum+l.rig,r.rig); rt.sum=l.sum+r.sum; rt.ans=max(l.ans,max(l.rig+r.lef,r.ans)); return rt;}void build(int l,int r,int rt) { tr[rt].l=l,tr[rt].r=r; if(l==r) { tr[rt].lef=tr[rt].rig=tr[rt].ans=tr[rt].sum=a[l]; return ; } build(l,mid,ls),build(mid+1,r,rs); tr[rt]=tr[ls]+tr[rs];}TREE query(int l,int r,int rt,int L,int R) { if(L==l&&r==R) { return tr[rt]; } if(R<=mid) return query(l,mid,ls,L,R); else if(L>mid) return query(mid+1,r,rs,L,R); else return query(l,mid,ls,L,mid)+query(mid+1,r,rs,mid+1,R);}int n,m;main() { cin>>n; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); cin>>m; for(int i=1;i<=m;i++) { int l,r; scanf("%lld%lld",&l,&r); printf("%lld\n",query(1,n,1,l,r).ans); } return 0;}T2.维护区间去重之后最大值。
同多校2017#404记录前一个状态，然后一个一个加入，维护一个后缀和
#include<bits/stdc++.h>#define int long long#define mid (l+(r-l)/2)#define ls (rt<<1)#define rs (rt<<1|1)#define hash H_shusing namespace std;const int N =(int)2e5+10;struct TREE { int max,lazy,pre_max,pre_lazy; int l,r; TREE() {max=lazy=pre_lazy=pre_max=0;}}tr[N<<2];int a[N];struct QUERY { int l,r,id; bool operator <(const QUERY &rhs) const { return r<rhs.r; }}p[N];int n,m,ans[N],pre[N];void pushup(int rt) { tr[rt].max=max(tr[ls].max,tr[rs].max); tr[rt].pre_max=max(tr[ls].pre_max,tr[rs].pre_max);}void pushdown(int rt) {//×¢ÒâÕâ¸öµÄpushdownµÄÕæÕýµÄÒâÒ壬ÊÇÏ´«±ê¼Ç£¬Ï´«¡£ if(!(tr[rt].lazy|tr[rt].pre_lazy)) return ; tr[ls].pre_lazy=max(tr[ls].pre_lazy,tr[ls].lazy+tr[rt].pre_lazy); tr[rs].pre_lazy=max(tr[rs].pre_lazy,tr[rs].lazy+tr[rt].pre_lazy); tr[ls].pre_max=max(tr[ls].pre_max,tr[ls].max+tr[rt].pre_lazy); tr[rs].pre_max=max(tr[rs].pre_max,tr[rs].max+tr[rt].pre_lazy); tr[ls].lazy+=tr[rt].lazy,tr[rs].lazy+=tr[rt].lazy; tr[ls].max+=tr[rt].lazy,tr[rs].max+=tr[rt].lazy; tr[rt].lazy=tr[rt].pre_lazy=0;}void update(int l,int r,int rt,int L,int R,int C) { tr[rt].l=l,tr[rt].r=r; if(L==l&&r==R) { tr[rt].max+=C;tr[rt].lazy+=C; tr[rt].pre_max=max(tr[rt].pre_max,tr[rt].max); tr[rt].pre_lazy=max(tr[rt].pre_lazy,tr[rt].lazy); return ; } pushdown(rt); if(R<=mid) update(l,mid,ls,L,R,C); else if(L>mid) update(mid+1,r,rs,L,R,C); else update(l,mid,ls,L,mid,C),update(mid+1,r,rs,mid+1,R,C); pushup(rt);}int query(int l,int r,int rt,int L,int R) { if(l==L&&R==r) return tr[rt].pre_max; pushdown(rt); if(R<=mid) return query(l,mid,ls,L,R); else if(L>mid) return query(mid+1,r,rs,L,R); else return max(query(l,mid,ls,L,mid),query(mid+1,r,rs,mid+1,R));}int hash(int a) {return a+(int)1e5;}main() { cin>>n; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); cin>>m; for(int i=1;i<=m;i++) scanf("%lld%lld",&p[i].l,&p[i].r),p[i].id=i; sort(p+1,p+m+1); for(int i=1,pos=1;i<=n;i++) { update(1,n,1,pre[hash(a[i])]+1,i,a[i]); pre[hash(a[i])]=i; while(pos<=m&&p[pos].r==i) ans[p[pos].id]=query(1,n,1,p[pos].l,p[pos].r),pos++; if(pos>m) break; } for(int i=1;i<=m;i++) printf("%lld\n",ans[i]); return 0;}T3.同t1多了一个修改
#include<bits/stdc++.h>#define mid (l+(r-l)/2)#define ls (rt<<1)#define rs (rt<<1|1)#define int long longusing namespace std;const int N =(int)1e5+10;struct TREE { int lef,rig,sum,ans; int l,r; void clear() {lef=rig=sum=ans=0;} void debug() { printf("%d %d %d %d %d %d\n",l,r,lef,rig,sum,ans); } }tr[N<<2];int a[N];TREE operator + (TREE l,TREE r) { TREE rt;rt.clear(); rt.l=l.l;rt.r=r.r; rt.lef=max(l.sum+r.lef,l.lef); rt.rig=max(r.sum+l.rig,r.rig); rt.sum=l.sum+r.sum; rt.ans=max(l.ans,max(l.rig+r.lef,r.ans)); return rt;}void build(int l,int r,int rt) { tr[rt].l=l,tr[rt].r=r; if(l==r) { tr[rt].lef=tr[rt].rig=tr[rt].ans=tr[rt].sum=a[l]; return ; } build(l,mid,ls),build(mid+1,r,rs); tr[rt]=tr[ls]+tr[rs];}TREE query(int l,int r,int rt,int L,int R) { if(L==l&&r==R) return tr[rt]; if(R<=mid) return query(l,mid,ls,L,R); else if(L>mid) return query(mid+1,r,rs,L,R); else return query(l,mid,ls,L,mid)+query(mid+1,r,rs,mid+1,R);}void update(int l,int r,int rt,int L,int C) { if(l==r) {tr[rt].lef=tr[rt].rig=tr[rt].ans=tr[rt].sum=C;return ;} if(L<=mid)update(l,mid,ls,L,C); else update(mid+1,r,rs,L,C); tr[rt]=tr[ls]+tr[rs];}int n,m;main() { cin>>n; for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1); cin>>m; for(int i=1;i<=m;i++) { int f,l,r; scanf("%lld%lld%lld",&f,&l,&r); if(f) printf("%lld\n",query(1,n,1,l,r).ans); else update(1,n,1,l,r); } return 0;}T4.区间开方求和，由于发现sqrt（1e18）嵌套6重向下取整为1，于是用线段树记录2一个区间还要不要暴力修改，需要的话暴力sqrt就行了。
#include<bits/stdc++.h>#define int long long#define cls(a) memset(a,0,sizeof(a))#define mid (l+(r-l)/2)#define ls (rt<<1)#define rs (rt<<1|1)using namespace std;const int N =(int)1e6+10;int sum[N],n,m,a[N],L[N],R[N];void build(int l,int r,int rt) { L[rt]=l,R[rt]=r; if(l==r) {sum[rt]=a[l];return;} build(l,mid,ls),build(mid+1,r,rs); sum[rt]=sum[ls]+sum[rs];}void update(int l,int r,int rt,int L,int R) {// cout<<l<<" "<<r<<" "<<L<<" "<<R<<"\n"; if(r-l+1==sum[rt]) return ; if(l==r) {sum[rt]=(int)sqrt(sum[rt]+0.0);return ;}//Ò»¶¨ÒªÊÇÒ¶×Ó½Úµã if(R<=mid) update(l,mid,ls,L,R); else if(L>mid) update(mid+1,r,rs,L,R); else update(l,mid,ls,L,mid),update(mid+1,r,rs,mid+1,R); sum[rt]=sum[ls]+sum[rs];}int query(int l,int r,int rt,int L,int R) { if(l==L&&r==R) return sum[rt]; if(R<=mid) return query(l,mid,ls,L,R); else if(L>mid) return query(mid+1,r,rs,L,R); else return query(l,mid,ls,L,mid)+query(mid+1,r,rs,mid+1,R);}void init() { cls(sum);}void debug(int l,int r,int rt) { if(l==r) {printf("%lld ",sum[rt]);return;} debug(l,mid,ls),debug(mid+1,r,rs);// sum[rt]=sum[ls]+sum[rs];}main() { int kase=0; while(cin>>n) { init(); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); build(1,n,1);// for(int i=1;i<=20;i++) // if(L[i])// printf("%d %d %d \n",L[i],R[i],sum[i]); cin>>m;printf("Case #%lld:\n",++kase); for(int i=1;i<=m;i++) { int f,l,r; scanf("%lld%lld%lld",&f,&l,&r); if(l>r) swap(l,r); if(!f) update(1,n,1,l,r); else printf("%lld\n",query(1,n,1,l,r));// debug(1,n,1); } puts(""); } return 0;}分块也是一样的道理。记录一个块要不要sqrt
#include<bits/stdc++.h>#define maxn 400000#define int long long#define cls(a) memset(a,0,sizeof(a))using namespace std;int read(){ int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c==‘-‘) f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();} return x*f;}int v[maxn],atag[maxn],bl[maxn],n,blo,sum[maxn],m,flag[maxn];void solve(int x){ if(flag[x]) return; flag[x]=1; sum[x]=0; for(int i=(x-1)*blo+1;i<=x*blo;i++) { v[i]=sqrt(v[i]),sum[x]+=v[i]; if(v[i]>1) flag[x]=0; }}void update(int a,int b){ for(int i=a;i<=min(bl[a]*blo,b);i++) sum[bl[a]]-=v[i],v[i]=sqrt(v[i]),sum[bl[a]]+=v[i]; if(bl[a]!=bl[b]) { for(int i=(bl[b]-1)*blo+1;i<=b;i++) sum[bl[b]]-=v[i],v[i]=sqrt(v[i]),sum[bl[b]]+=v[i]; } for(int i=bl[a]+1;i<=bl[b]-1;i++) solve(i);}int query(int a,int b){ int ans=0; for(int i=a;i<=min(bl[a]*blo,b);i++) ans+=v[i]; if(bl[a]!=bl[b]) { for(int i=(bl[b]-1)*blo+1;i<=b;i++) ans+=v[i]; } for(int i=bl[a]+1;i<=bl[b]-1;i++) ans+=sum[i]; return ans;}main(){// freopen("1012.out","r",stdin);// freopen("1.txt","w",stdout); int kase=0; while(~scanf("%lld",&n)&&n) { printf("Case #%lld:\n",++kase); cls(v),cls(sum),cls(flag);cls(atag);cls(bl); blo=sqrt(n); for(int i=1;i<=n;i++) v[i]=read(),bl[i]=(i-1)/blo+1, sum[bl[i]]+=v[i]; m=read(); for(int i=1;i<=m;i++) { int f=read(),a=read(),b=read(); if(a>b) swap(a,b); if(f==0) update(a,b); else printf("%lld\n",query(a,b)); } puts(""); } return 0;}小坑，由于题目说的是x~y所以可能x>y需要swap一下。
T5.给定l,r的取值范围，求l~r和最大
分类讨论，具体见main函数。
小细节注意
要保证点在区间中,这个区间的完整性很重要,要注意如果选lmax那么就是至少选一个元素。
#include<bits/stdc++.h>#define mid (l+(r-l)/2)#define ls (rt<<1)#define rs (rt<<1|1)//#define int long long#define root 1,n,1using namespace std;const int N =(int)1e5+10;struct TREE { int lef,rig,sum,ans; int l,r; void clear() {lef=rig=sum=ans=0;} void debug() { printf("%d %d %d %d %d %d\n",l,r,lef,rig,sum,ans); } }tr[N<<2],paste;int a[N],t;TREE operator + (TREE l,TREE r) { TREE rt;rt.clear(); rt.l=l.l;rt.r=r.r; rt.lef=max(l.sum+r.lef,l.lef); rt.rig=max(r.sum+l.rig,r.rig); rt.sum=l.sum+r.sum; rt.ans=max(l.ans,max(l.rig+r.lef,r.ans)); return rt;}void build(int l,int r,int rt) { tr[rt].l=l,tr[rt].r=r; if(l==r) { tr[rt].lef=tr[rt].rig=tr[rt].ans=tr[rt].sum=a[l]; return ; } build(l,mid,ls),build(mid+1,r,rs); tr[rt]=tr[ls]+tr[rs];}TREE query(int l,int r,int rt,int L,int R) { if(L>R) return paste; if(L==l&&r==R) return tr[rt]; if(R<=mid) return query(l,mid,ls,L,R); else if(L>mid) return query(mid+1,r,rs,L,R); else return query(l,mid,ls,L,mid)+query(mid+1,r,rs,mid+1,R);}void update(int l,int r,int rt,int L,int C) { if(l==r) {tr[rt].lef=tr[rt].rig=tr[rt].ans=tr[rt].sum=C;return ;} if(L<=mid)update(l,mid,ls,L,C); else update(mid+1,r,rs,L,C); tr[rt]=tr[ls]+tr[rs];}int n,m;main() { paste.clear();cin>>t; for(;t;t--) { cin>>n; memset(tr,0,sizeof(tr));memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(root); cin>>m; for(int i=1;i<=m;i++) { int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if(y1<x2) { printf("%d\n",query(root,x1,y1).rig+query(root,y1+1,x2-1).sum+query(root,x2,y2).lef); } else { int m1=query(root,x2,y1).ans; int m2=query(root,x2,y2).lef+query(root,x1,x2-1).rig; int m3=query(root,x1,y1).rig+query(root,y1+1,y2).lef;// cout<<query(root,x1,x2-1).rig<<" "<<query(root,y1+1,y2).lef<<"\n"; printf("%d\n",max(max(m1,m2),m3)); } } } return 0;}后面的3题好像是splay啊，还是不怎么会写，以后再说吧，先挖一个坑。
最后来一发二维树状数组poj2155具体可以看《浅谈信息学竞赛中的“0”和“1”》这篇论文很详细。
一个小小的下标搞了好久。。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cassert>#define lowbit(_x) (_x&(-_x))using namespace std;int n,m,x1,x2,y1,y2,t,fst=187415157;int sum[1100][1100]; void U(int x,int y,int val) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) sum[i][j]+=val;} int query(int x,int y) { int ans=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ans+=sum[i][j]; return ans;}char s[20];main() { cin>>t; for(;t;t--){ if(!fst)puts("");fst=0; memset(sum,0,sizeof(sum)); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%s",s); if(s[0]==‘C‘) scanf("%d%d%d%d",&x1,&y1,&x2,&y2),U(x1,y1,1),U(x1,y2+1,1),U(x2+1,y1,1),U(x2+1,y2+1,1); else scanf("%d%d",&x1,&y1),printf("%d\n",query(x1,y1)%2); } }}
spoj GSS线段树以及二维树状数组合集
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。