您的位置: 首页 > IT文章 > 线段树专题

线段树专题

分类: IT文章 • 2022-03-26 23:57:31

线段树专题

搞完了线段树专题

拿几道还比较有意义的题来写一下博客吧

还是先%棒神为好

① 小白逛公园 bzoj 1756

题目大意：

一个序列支持单点修改和区间内连续子段最大值

思路：

对于线段树上每一段维护四个东西

每一段从左起的最大值从右起的最大值这一段的sum 这一段的答案

然后合并的时候可以很容易的合并此时在query的时候return 一个节点比较方便

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 500100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
19     return x*f;
20 }
21 struct data 
22 {
23     int mx,lm,rm,sum,l,r;
24     //void PRINT() {cout<<l<<" "<<r<<" "<<mx<<" "<<lm<<" "<<rm<<" "<<sum<<endl;}
25 }tr[MAXN<<2];
26 int n,T,a[MAXN];
27 void upd(int k)
28 {
29     tr[k].sum=tr[k<<1].sum+tr[k<<1|1].sum;
30     tr[k].lm=max(tr[k<<1].lm,tr[k<<1|1].lm+tr[k<<1].sum);
31     tr[k].rm=max(tr[k<<1|1].rm,tr[k<<1].rm+tr[k<<1|1].sum);
32     tr[k].mx=max(tr[k<<1].rm+tr[k<<1|1].lm,max(tr[k<<1|1].mx,tr[k<<1].mx));
33     //tr[k].PRINT();
34 }
35 void build(int k,int l,int r)
36 {
37     tr[k].l=l,tr[k].r=r;
38     if(l==r) {tr[k].mx=tr[k].lm=tr[k].rm=tr[k].sum=a[l];return ;}
39     int mid=(l+r)>>1;
40     build(k<<1,l,mid);build(k<<1|1,mid+1,r);
41     upd(k);
42 }
43 void mdf(int k,int x,int w)
44 {
45     int l=tr[k].l,r=tr[k].r;
46     if(l==r) {tr[k].mx=tr[k].lm=tr[k].rm=tr[k].sum=w;return ;}
47     int mid=(l+r)>>1;
48     if(mid>=x) mdf(k<<1,x,w);
49     else mdf(k<<1|1,x,w);
50     //cout<<"MODIFY: "<<k<<" "<<x<<" "<<w<<endl;
51     upd(k);
52 }
53 data query(int k,int a,int b)
54 {
55     int l=tr[k].l,r=tr[k].r;
56     if(l==a&&r==b) return tr[k];
57     int mid=(l+r)>>1;
58     if(mid>=b) return query(k<<1,a,b);
59     else if(mid<a) return query(k<<1|1,a,b);
60     else
61     {
62         //cout<<"Q: "<<k<<" "<<a<<" "<<b<<endl;
63         data x=query(k<<1,a,mid),y=query(k<<1|1,mid+1,b),res;
64         //x.PRINT();y.PRINT();
65         res.lm=max(x.lm,y.lm+x.sum);
66         res.rm=max(y.rm,x.rm+y.sum);
67         res.mx=max(x.rm+y.lm,max(y.mx,x.mx));
68         //res.PRINT();
69         return res;
70     }
71 }
72 int main()
73 {
74     n=read(),T=read();int x,y,z;data res;
75     for(int i=1;i<=n;i++) a[i]=read();
76     build(1,1,n);
77     while(T--)
78     {
79         x=read(),y=read(),z=read();
80         if(x==1) printf("%d
",query(1,min(y,z),max(y,z)).mx);
81         else mdf(1,y,z);
82     }
83 }

View Code

② MooFest poj 1990

题目大意：

现在有n头奶牛，第i头奶牛的听力阈值为v(i),即如果其他奶牛想让这只奶牛听到它的声音，那么至少得发出v(i)乘上它们之间距离这么大的音量

所以如果第i头奶牛和第j头奶牛交谈，那么发出的音量大小至少是它们之间的距离乘上它们两个阈值中的最大值，即max(v(i),v(j))

现在这n头奶牛站在了一条直线上，每头奶牛都站在唯一的坐标上

并且每对奶牛交谈都尽可能降低音量。那么请你计算出这n*(n-1)/2对奶牛交谈产生的最小总音量大小

思路：

使用树状数组就可以很方便的维护

先将奶牛按照v值排序这样它与排序后前面的奶牛说话使用的是它的v值

然后我们需要求出它前面所有奶牛与它的距离之和

可以分成两种情况位置在左边或者右边

然后我们开两个树状数组分别维护哪个位置有奶牛来求出它左边和右边各有多少个奶牛

另一个维护距离之和这样就可以分别知道它左边和右边奶牛的距离之和然后推一个小学数学公式即可

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 20100
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
18     while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
19     return x*f;
20 }
21 int n;
22 ll ans;
23 struct data {int pos,val;}g[MAXN];
24 bool cmp(data x,data y) {return x.val<y.val;}
25 struct array
26 {
27     ll c[MAXN];
28     inline int lowbit(int x) {return x&(-x);}
29     void add(int x,int val) {for(int i=x;i<=MAXN;i+=lowbit(i)) c[i]+=val;}
30     ll sum(int x) {ll res=0;for(int i=x;i;i-=lowbit(i)) res+=c[i];return res;}
31 }a,b;
32 int main()
33 {
34     n=read();ll tot=0,x,y;
35     for(int i=1;i<=n;i++) g[i].val=read(),g[i].pos=read();
36     sort(g+1,g+n+1,cmp);
37     for(int i=1;i<=n;i++)
38     {
39         x=a.sum(g[i].pos-1),y=b.sum(g[i].pos-1);
40         ans+=g[i].val*(x*g[i].pos-y-(i-x-1)*g[i].pos+(tot-b.sum(g[i].pos-1)));
41         //cout<<g[i].val<<"*("<<x<<"*"<<g[i].pos<<"-"<<y<<"-"<<(i-x-1)<<"*"<<g[i].pos<<"+("<<tot<<"-"<<b.sum(g[i].pos-1)<<"))"<<endl<<ans<<endl;
42         tot+=g[i].pos;
43         a.add(g[i].pos,1);b.add(g[i].pos,g[i].pos);
44     }
45     printf("%lld",ans);
46 }

View Code

③ 遭遇战 vijos 1404

题目大意：

一个大区间1-n

有一些区间l-r可以覆盖并有一些代价

求出最小代价覆盖s-t区间

思路：

可以建图来跑最短路

对于每个l r 从l向r+1连一条边然后每个i向i-1连一条边

最后跑s-t+1的最短路即可（dij比spfa快到不知道哪里去了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<map>
10 #define inf 2139062143
11 #define ll long long
12 #define MAXN 90101
13 #define P pair<int,int>
14 #define mp(a,b) make_pair(a,b)
15 using namespace std;
16 inline int read()
17 {
18     int x=0,f=1;char ch=getchar();
19     while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
20     while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
21     return x*f;
22 }
23 int s,t,dis[MAXN],n;
24 int fst[MAXN],nxt[MAXN<<1],to[MAXN<<1],val[MAXN<<1],cnt;
25 void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}
26 int dij()
27 {
28     priority_queue<P,vector<P>,greater<P> > q;
29     memset(dis,127,sizeof(dis));
30     dis[s]=0;q.push(mp(0,s));
31     while(!q.empty())
32     {
33         int k=q.top().second;q.pop();
34         for(int i=fst[k];i;i=nxt[i])
35             if(dis[to[i]]>dis[k]+val[i]) {dis[to[i]]=dis[k]+val[i];q.push(mp(dis[to[i]],to[i]));}
36     }
37     return dis[t+1]==inf?-1:dis[t+1];
38 }
39 int main()
40 {
41     int a,b,c;
42     n=read(),s=read(),t=read();
43     while(n--) {a=max(read(),s),b=min(read()+1,t+1),c=read();add(a,b,c);add(b,a,c);}
44     for(int i=s+1;i<=t+1;i++) add(i,i-1,0);
45     printf("%d",dij());
46 }

View Code

线段树专题

相关推荐