首页 > 代码库 > [用CDQ分治解决区间加&区间求和]【习作】
[用CDQ分治解决区间加&区间求和]【习作】
【前言】
作为一个什么数据结构都不会只会CDQ分治和分块的蒟蒻，面对区间加&区间求和这么难的问题，怎么可能会写线段树呢
于是，用CDQ分治解决区间加&区间求和这篇习作应运而生
【Part.I】区间加&区间求和的数据结构做法
【一】线段树
裸题...
1141ms
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;#define lc x<<1#define rc x<<1|1#define mid ((l+r)>>1)#define lson lc, l, mid#define rson rc, mid+1, rtypedef long long ll;const int N=1e5+5;inline ll read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,Q,op,x,y;struct SegmentTree{ struct meow{ ll sum, tag; } t[N<<2]; inline void paint(int x,int l,int r,ll v){ t[x].tag+= v; t[x].sum+= (r-l+1)*v; } inline void pushDown(int x,int l,int r){ if(t[x].tag){ paint(lson, t[x].tag); paint(rson, t[x].tag); t[x].tag=0; } } void build(int x,int l,int r){ if(l==r) t[x].sum=read(); else{ build(lson); build(rson); t[x].sum=t[lc].sum+t[rc].sum; } } void Add(int x,int l,int r,int ql,int qr,ll v){ if(ql<=l && r<=qr) paint(x,l,r,v); else{ pushDown(x,l,r); if(ql<=mid) Add(lson, ql, qr, v); if(mid<qr) Add(rson, ql, qr, v); t[x].sum=t[lc].sum+t[rc].sum; } } ll Que(int x,int l,int r,int ql,int qr){ if(ql<=l && r<=qr) return t[x].sum; else{ pushDown(x,l,r); ll ans=0; if(ql<=mid) ans+=Que(lson, ql, qr); if(mid<qr) ans+=Que(rson, ql, qr); return ans; } }}S;int main(){ //freopen("in","r",stdin); n=read(); Q=read(); S.build(1,1,n); while(Q--){ op=read();x=read();y=read(); if(op==1) S.Add(1,1,n,x,y,read() ); else printf("%lld\n", S.Que(1,1,n,x,y) ); }}
【二】树状数组
考虑每个位置的贡献，维护$a[i]$和$i*a[i]$
477ms
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline ll read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,Q,op,x,y;struct meow{ ll c[N]; inline void add(int p,ll v) {for(;p<=n;p+=p&-p) c[p]+=v;} inline ll sum(int p) {ll re=0; for(;p;p-=p&-p) re+=c[p]; return re;} inline ll sum(int l,int r) {return sum(r)-sum(l-1);}}C1,C2;struct BinaryIndexTree{ inline void Add(int l,int r,ll v){ C1.add(l,v); C1.add(r+1,-v); C2.add(l,l*v); C2.add(r+1,-(r+1)*v); } inline ll Que(int l,int r){ return (r-l+1)*C1.sum(1,l) + (r+1)*C1.sum(l+1,r) - C2.sum(l+1,r); }}A;int main(){// freopen("in","r",stdin); n=read(); Q=read(); for(int i=1;i<=n;i++) A.Add(i,i,read() ); while(Q--){ op=read();x=read();y=read(); if(op==1) A.Add(x,y,read() ); else printf("%lld\n", A.Que(x,y) ); }}
【Part.II】区间加&区间求和的CDQ分治做法
首先我们明确CDQ分治是什么 参见[偏序关系与CDQ分治]【学习笔记】
用CDQ分治解决单点加&区间求和 区间加&单点求值 是很容易的，但要两个都是区间就不太方便了
但经过两个多小时的研究，终于做出来啦
区间加&区间求和可以算是二维偏序问题，可以只用排序和CDQ分治不借助任何数据结构解决
首先把修改和询问都拆成两个
我们对时间排序，对位置进行CDQ分治
问题在于对于$[l,r]$这样一个加操作，$r<p$的当然很方便了，但对$l \le p \le r$的每个$p$贡献都是不一样的
一开始困扰了我好久
突然想到可以维护一个$val$表示当前每在位置上移动一个距离总体的贡献应该改变多少，再维护一个$last$表示上一个位置
然后更新当前的贡献时用$val$乘移动的距离就可以了
问题解决！撒花
1251ms 时间垫底了.....
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline ll read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,Q,m,op,l,r; ll a[N],v,ans[N];struct meow{ int x,type,qid; ll v; meow(){} meow(int b,int c,int d,ll e):x(b),type(c),qid(d),v(e){} bool operator <(const meow &r) const {return x==r.x ? type<r.type : x<r.x;}}q[N<<2],t[N<<2];void CDQ(int l,int r){ if(l==r) return ; int mid=(l+r)>>1; CDQ(l, mid); CDQ(mid+1, r); int i=l, j=mid+1, p=l; ll now=0, val=0; int last=0; while(i<=mid || j<=r){ if(j>r || (i<=mid && q[i]<q[j]) ){ now+=(q[i].x-last)*val; last=q[i].x; if(q[i].type!=0) val+=q[i].v; t[p++]=q[i++]; }else{ now+=(q[j].x-last)*val; last=q[j].x; if(!q[j].type) ans[ q[j].qid ]+= now*q[j].v ; t[p++]=q[j++]; } } for(int i=l;i<=r;i++) q[i]=t[i];}int main(){ freopen("in","r",stdin); n=read(); Q=read(); int p=0; for(int i=1;i<=n;i++) v=read(), q[++m]=meow(i-1,-1,0,v), q[++m]=meow(i,1,0,-v); for(int i=1;i<=Q;i++){ op=read(); l=read(); r=read(); if(op==1) v=read(), q[++m]=meow(l-1,-1,0,v), q[++m]=meow(r,1,0,-v); else p++, q[++m]=meow(l-1,0,p,-1), q[++m]=meow(r,0,p,1); } CDQ(1,m); for(int i=1;i<=p;i++) printf("%lld\n",ans[i]);}
【Part.III】应用
这玩意常数又大又需要离线有什么用啊
我们可以出题坐标特别大强制线段树来离线离散化
[用CDQ分治解决区间加&区间求和]【习作】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。